ubc
High Dimensional Fast Fourier Transform Based on Rank-1 Lattice Sampling
2015-02-24
[Electronic ed.]
prv
Universitätsbibliothek Chemnitz
Universitätsbibliothek Chemnitz, Chemnitz
Fakultät für Mathematik
Professur Angewandte Funktionalanalysis
male
Apolda
We consider multivariate trigonometric polynomials with frequencies supported on a fixed but arbitrary frequency index set I, which is a finite set of integer vectors of length d. Naturally, one is interested in spatial
discretizations in the d-dimensional torus such that
- the sampling values of the trigonometric polynomial at the nodes of this spatial discretization uniquely determines the trigonometric polynomial,
- the corresponding discrete Fourier transform is fast realizable, and
- the corresponding fast Fourier transform is stable.
An algorithm that computes the discrete Fourier transform and that needs a computational complexity that is bounded from above by terms that are linear in the maximum of the number of input and output data up to some logarithmic factors is called fast Fourier transform. We call the fast Fourier transform stable if the Fourier matrix of the discrete Fourier transform has a condition number near one and the fast algorithm does not corrupt this theoretical stability.
We suggest to use rank-1 lattices and a generalization as spatial discretizations in order to sample multivariate trigonometric polynomials and we develop construction methods in order to determine reconstructing sampling sets, i.e., sets of sampling nodes that allow for the unique, fast, and stable reconstruction of trigonometric polynomials. The methods for determining reconstructing rank-1 lattices are component{by{component constructions, similar to the seminal methods that are developed in the field of numerical integration. During this thesis we identify a component{by{component construction of reconstructing rank-1 lattices that allows for an estimate of the number of sampling nodes M
|I|\le M\le \max\left(\frac{2}{3}|I|^2,\max\{3\|\mathbf{k}\|_\infty\colon\mathbf{k}\in I\}\right)
that is sufficient in order to uniquely reconstruct each multivariate trigonometric polynomial with frequencies supported on the frequency index set I. We observe that the bounds on the number M only depends on the number of frequency indices contained in I and the expansion of I, but not on the spatial dimension d. Hence, rank-1 lattices are suitable spatial discretizations in arbitrarily high dimensional problems.
Furthermore, we consider a generalization of the concept of rank-1 lattices, which we call generated sets. We use a quite different approach in order to determine suitable reconstructing generated sets. The corresponding construction method is based on a continuous optimization method.
Besides the theoretical considerations, we focus on the practicability of the presented algorithms and illustrate the theoretical findings by means of several examples.
In addition, we investigate the approximation properties of the considered sampling schemes. We apply the results to the most important structures of frequency indices in higher dimensions, so-called hyperbolic crosses and demonstrate the approximation properties by the means of several examples that include the solution of Poisson's equation as one representative of partial differential equations.
518
Approximation, Periodisierung
Rang-1 Gitter, komponentenweise Konstruktion, hochdimensionale diskrete Fourier Transformation, hochdimensionale schnelle Fourier Transformation, multivariate trigonometrische Polynome, Frequenzindexmenge, Differenzmenge der Frequenzindexmenge, Rang-1 Abtastmenge, hyperbolisches Kreuz, Energienorm basiertes hyperbolisches Kreuz
rank-1 lattice, component-by-component, lattice rule, high dimensional discrete Fourier transform , high dimensional fast Fourier transform, multivariate trigonometric polynomials, frequency index set, difference set of a frequency index set, generated set, approximation, periodization, hyperbolic cross, energy-norm based hyperbolic cross
urn:nbn:de:bsz:ch1-qucosa-157673
978-3-944640-41-9
Technische Universität Chemnitz
dgg
Technische Universität Chemnitz, Chemnitz
Universitätsverlag der Technischen Universität Chemnitz
pbl
Universitätsverlag der Technischen Universität Chemnitz, Chemnitz
Lutz
Kämmerer
Dipl.-Math.
1982-05-13
aut
Daniel
Potts
Prof. Dr.
dgs
rev
Peter.
Oswald
Prof. Dr.
rev
Winfried
Sickel
Prof. Dr.
rev
eng
2014-06-30
2014-11-21
born digital
Hochdimensionale schnelle Fourier-Transformation basierend auf Rang-1 Gittern als Ortsdiskretisierungen
coe
uni-verlag@bibliothek.tu-chemnitz.de
doctoral_thesis
Interimsdaten!