Summary
An algorithm for the trigonometric interpolation of functions ofn variables on a sparse grid is described. This discrete Fourier transform based on FFT has a greatly reduced complexity in comparison to the fourier transform on a regular grid whereas the approximation quality is only slightly reduced if the function belongs to a Korobov space. The transformation is easily invertible.
Zusammenfassung
Es wird ein auf der schnellen Fouriertransformation beruhender Algorithmus zur trigonometrischen Interpolation von multivariaten Funktionen auf einem dünnen Gitter beschrieben. Bei nur geringfügig schlechterer Approximationsgenauigkeit für Funktionen aus Korobovräumen hat dieser Algorithmus eine viel kleinere Komplexität als die Algorithmen, die auf gewöhnlichen Gittern arbeiten. Die Transformation ist auf einfache Weise umkehrbar.
Similar content being viewed by others
Literatur
Baszenski, G., Delvos, F.-J. (1989): A Discrete Fourier Transform Scheme for Boolean Sums of Trigonometric Operators. In: C.K. Chui, W. Schempp, K. Zeller, Hrsg., Multivariate Approximation Theory IV, Birkhäuser, Basel
Cooley, J.W., Tukey, J.W. (1965): An algorithm for the machine calculation of complex Fourier series. Math. Comput.19, 297–301
Hlawka, E., Firneis, F., Zinterhofer, P. (1981): Zahlentheoretische Methoden in der numerischen Mathematik. Oldenburg, Wien
Yserentant, H. (1986): On the multi-level splitting of finite element spaces. Numer. Math.49, 379–412
Zenger, C. (1991): Sparse Grids. In: W. Hackbusch, Hrsg., Notes on Numerical Fluid Mechanics, Bd. 31, S. 241–251. Vieweg, Braunschweig
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hallatschek, K. Fouriertransformation auf dünnen Gittern mit hierarchischen Basen. Numer. Math. 63, 83–97 (1992). https://doi.org/10.1007/BF01385849
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01385849