Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSuper-high-efficiency approximate calculation of series sum and discrete Fourier transform
113
0
0.0
(
0
)
Authors
Xin-Zhong Yan
Ask ChatGPT about the research
No Arabic abstract
We present a super-high-efficiency approximate computing scheme for series sum and discrete Fourier transform. The summation of a series sum or a discrete Fourier transform is approximated by summing over part of the terms multiplied by corresponding weights. The calculation is valid for the function under the transform being piecewise smooth in the continuum variable. The scheme reduces significantly the requirement for computer memory storage and enhances the numerical computation efficiency without losing accuracy. By comparing with the known results of examples, we show the accuracy and the efficiency of the scheme. The efficiency can be higher than $10^6$ for the examples.
rate research
Read More
In this work, we introduce a definition of the Discrete Fourier Transform (DFT) on Euclidean lattices in $R^n$, that generalizes the $n$-th fold DFT of the integer lattice $Z^n$ to arbitrary lattices. This definition is not applicable for every lattice, but can be defined on lattices known as Systematic Normal Form (SysNF) introduced in cite{ES16}. Systematic Normal Form lattices are sets of integer vectors that satisfy a single homogeneous modular equation, which itself satisfies a certain number-theoretic property. Such lattices form a dense set in the space of $n$-dimensional lattices, and can be used to approximate efficiently any lattice. This implies that for every lattice $L$ a DFT can be computed efficiently on a lattice near $L$. Our proof of the statement above uses arguments from quantum computing, and as an application of our definition we show a quantum algorithm for sampling from discrete distributions on lattices, that extends our ability to sample efficiently from the discrete Gaussian distribution cite{GPV08} to any distribution that is sufficiently smooth. We conjecture that studying the eigenvectors of the newly-defined lattice DFT may provide new insights into the structure of lattices, especially regarding hard computational problems, like the shortest vector problem.
Primitive inflation tilings of the real line with finitely many tiles of natural length and a Pisot--Vijayaraghavan unit as inflation factor are considered. We present an approach to the pure point part of their diffraction spectrum on the basis of a Fourier matrix cocycle in internal space. This cocycle leads to a transfer matrix equation and thus to a closed expression of matrix Riesz product type for the Fourier transforms of the windows for the covering model sets. In general, these windows are complicated Rauzy fractals and thus difficult to handle. Equivalently, this approach permits a construction of the (always continuously representable) eigenfunctions for the translation dynamical system induced by the inflation rule. We review and further develop the underlying theory, and illustrate it with the family of Pisa substitutions, with special emphasis on the Tribonacci case.
In this paper, we present a numerical technique for performing Lie advection of arbitrary differential forms. Leveraging advances in high-resolution finite volume methods for scalar hyperbolic conservation laws, we first discretize the interior product (also called contraction) through integrals over Eulerian approximations of extrusions. This, along with Cartans homotopy formula and a discrete exterior derivative, can then be used to derive a discrete Lie derivative. The usefulness of this operator is demonstrated through the numerical advection of scalar fields and 1-forms on regular grids.
In this work, we present two parallel algorithms for the large-scale discrete Fourier transform (DFT) on Tensor Processing Unit (TPU) clusters. The two parallel algorithms are associated with two formulations of DFT: one is based on the Kronecker product, to be specific, dense matrix multiplications between the input data and the Vandermonde matrix, denoted as KDFT in this work; the other is based on the famous Cooley-Tukey algorithm and phase adjustment, denoted as FFT in this work. Both KDFT and FFT formulations take full advantage of TPUs strength in matrix multiplications. The KDFT formulation allows direct use of nonuniform inputs without additional step. In the two parallel algorithms, the same strategy of data decomposition is applied to the input data. Through the data decomposition, the dense matrix multiplications in KDFT and FFT are kept local within TPU cores, which can be performed completely in parallel. The communication among TPU cores is achieved through the one-shuffle scheme in both parallel algorithms, with which sending and receiving data takes place simultaneously between two neighboring cores and along the same direction on the interconnect network. The one-shuffle scheme is designed for the interconnect topology of TPU clusters, minimizing the time required by the communication among TPU cores. Both KDFT and FFT are implemented in TensorFlow. The three-dimensional complex DFT is performed on an example of dimension $8192 times 8192 times 8192$ with a full TPU Pod: the run time of KDFT is 12.66 seconds and that of FFT is 8.3 seconds. Scaling analysis is provided to demonstrate the high parallel efficiency of the two DFT implementations on TPUs.
The discrete Fourier transform (DFT) is an important operator which acts on the Hilbert space of complex valued functions on the ring Z/NZ. In the case where N=p is an odd prime number, we exhibit a canonical basis of eigenvectors for the DFT. The transition matrix from the standard basis to the canonical basis defines a novel transform which we call the discrete oscillator transform (DOT for short). Finally, we describe a fast algorithm for computing the discrete oscillator transform in certain cases.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
