Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Fast computation of the multidimensional discrete Fourier transform and discrete backward Fourier transform on sparse grids

Authors: Ying Jiang and Yuesheng Xu
Journal: Math. Comp. 83 (2014), 2347-2384
MSC (2010): Primary 65T50
Published electronically: February 11, 2014
MathSciNet review: 3223335
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We propose a fast discrete Fourier transform for a given data set which may be generated from sampling a function of $ d$-variables on a sparse grid and a fast discrete backward Fourier transform on a hyperbolic cross index set. Computation of these transforms can be formulated as evaluation of dimension-reducible sums on sparse grids. We introduce a fast algorithm for evaluating such sums and prove that the total number of operations needed in the algorithm is $ \mathcal {O}(n\log ^{d}n)$, where $ n$ is the number of components along each coordinate direction of the data set. We then use it to develop fast algorithms for computing the discrete Fourier transform on the sparse grid and the discrete backward Fourier transform on the hyperbolic cross index set. We also show that if the given data set is sampled from a function having regularity of order $ s$, then its discrete Fourier transform has the optimal approximation order $ \mathcal {O}(n^{-s})$. Numerical examples are presented to demonstrate the approximation accuracy and computational efficiency of the proposed algorithms.

References [Enhancements On Off] (What's this?)

  • [1] Robert Balder and Christoph Zenger, The solution of multidimensional real Helmholtz equations on sparse grids, SIAM J. Sci. Comput. 17 (1996), no. 3, 631-646. MR 1384255 (97h:65132),
  • [2] Kai Bittner, Fast algorithms for periodic spline wavelets on sparse grids, SIAM J. Sci. Comput. 20 (1999), no. 4, 1192-1213 (electronic). MR 1675469 (2000b:65018),
  • [3] Hans-Joachim Bungartz, A multigrid algorithm for higher order finite elements on sparse grids, Electron. Trans. Numer. Anal. 6 (1997), no. Dec., 63-77 (electronic). Special issue on multilevel methods (Copper Mountain, CO, 1997). MR 1615156 (99a:65174)
  • [4] Hans-Joachim Bungartz and Michael Griebel, Sparse grids, Acta Numer. 13 (2004), 147-269. MR 2249147 (2007e:65102),
  • [5] Haotao Cai and Yuesheng Xu, A fast Fourier-Galerkin method for solving singular boundary integral equations, SIAM J. Numer. Anal. 46 (2008), no. 4, 1965-1984. MR 2399403 (2009c:65356),
  • [6] Zhongying Chen, Charles A. Micchelli, and Yuesheng Xu, A construction of interpolating wavelets on invariant sets, Math. Comp. 68 (1999), no. 228, 1569-1587. MR 1651746 (99m:65017),
  • [7] James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297-301. MR 0178586 (31 #2843)
  • [8] R. A. Devor, P. P. Petrushev, and V. N. Temlyakov, Multidimensional approximations by trigonometric polynomials with harmonics of a hyperbolic cross, Mat. Zametki 56 (1994), no. 3, 36-63, 158 (Russian, with Russian summary); English transl., Math. Notes 56 (1994), no. 3-4, 900-918 (1995). MR 1309839 (96b:42001)
  • [9] Michael Döhler, Stefan Kunis, and Daniel Potts, Nonequispaced hyperbolic cross fast Fourier transform, SIAM J. Numer. Anal. 47 (2010), no. 6, 4415-4428. MR 2585193 (2011a:65466),
  • [10] Karin Frank, Stefan Heinrich, and Sergei Pereverzev, Information complexity of multivariate Fredholm integral equations in Sobolev classes, J. Complexity 12 (1996), no. 1, 17-34. MR 1386591 (97h:65167),
  • [11] V. Gradinaru, Fourier transform on sparse grids: code design and the time dependent Schrödinger equation, Computing 80 (2007), no. 1, 1-22. MR 2308834 (2008k:65212),
  • [12] V. Gradinaru, Strang splitting for the time-dependent Schrödinger equation on sparse grids, SIAM J. Numer. Anal. 46 (2007/08), no. 1, 103-123. MR 2377257 (2009c:65249),
  • [13] M. Griebel and S. Knapek, Optimized general sparse grid approximation spaces for operator equations, Math. Comp. 78 (2009), no. 268, 2223-2257. MR 2521287 (2010f:65255),
  • [14] Klaus Hallatschek, Fouriertransformation auf dünnen Gittern mit hierarchischen Basen, Numer. Math. 63 (1992), no. 1, 83-97 (German, with English and German summaries). MR 1182513 (93f:65014),
  • [15] Ying Jiang and Yuesheng Xu, Fast discrete algorithms for sparse Fourier expansions of high dimensional functions, J. Complexity 26 (2010), no. 1, 51-81. MR 2574572 (2011a:65467),
  • [16] Ying Jiang and Yuesheng Xu, Fast Fourier-Galerkin methods for solving singular boundary integral equations: numerical integration and precondition, J. Comput. Appl. Math. 234 (2010), no. 9, 2792-2807. MR 2652126 (2011f:65309),
  • [17] Ying Jiang and Yuesheng Xu, B-spline quasi-interpolation on sparse grids, J. Complexity 27 (2011), no. 5, 466-488. MR 2805532 (2012i:65014),
  • [18] S. Knapek, Hyperbolic cross approximation of integral operators with smooth kernel, Technical Report 665, SFB 256, Univ. Bonn, 2000.
  • [19] N. S. Nikolskaja, Approximation of differentiable functions of several variables by Fourier sums in the $ L_{p}$ metric, Sibirsk. Mat. Ž. 15 (1974), 395-412, 461 (Russian). MR 0336221 (49 #997)
  • [20] S. V. Pereverzev, Hyperbolic cross and complexity of an approximate solution of Fredholm integral equations of the second kind with differentiable kernels, Sibirsk. Mat. Zh. 32 (1991), no. 1, 107-115, 221 (Russian); English transl., Siberian Math. J. 32 (1991), no. 1, 85-92. MR 1112086 (92g:45014),
  • [21] Jie Shen and Haijun Yu, Efficient spectral sparse grid methods and applications to high-dimensional elliptic problems, SIAM J. Sci. Comput. 32 (2010), no. 6, 3228-3250. MR 2746619 (2012a:65354),
  • [22] V. Temlyakov, Approximation of functions with bounded mixed derivative, Trudy Mat. Inst. Steklov., 178 (1986), 1-112. MR 0847439 (87j:42006)
  • [23] V. N. Temlyakov, Approximation of periodic functions, Computational Mathematics and Analysis Series, Nova Science Publishers Inc., Commack, NY, 1993. MR 1373654 (96j:41001)
  • [24] Bo Wang, Rui Wang, and Yuesheng Xu, Fast Fourier-Galerkin methods for first-kind logarithmic-kernel integral equations on open arcs, Sci. China Math. 53 (2010), no. 1, 1-22. MR 2594743 (2011d:65424),
  • [25] Yuesheng Xu and Aihui Zhou, Fast Boolean approximation methods for solving integral equations in high dimensions, J. Integral Equations Appl. 16 (2004), no. 1, 83-110. MR 2093500 (2005e:65219),
  • [26] Andreas Zeiser, Fast matrix-vector multiplication in the sparse-grid Galerkin method, J. Sci. Comput. 47 (2011), no. 3, 328-346. MR 2793587 (2012j:65435),

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65T50

Retrieve articles in all journals with MSC (2010): 65T50

Additional Information

Ying Jiang
Affiliation: Guangdong Province Key Lab of Computational Science, School of Mathematics and Computational Science, Sun Yat-sen University, Guangzhou 510275, P. R. China

Yuesheng Xu
Affiliation: Guangdong Province Key Lab of Computational Science, School of Mathematics and Computational Science, Sun Yat-sen University, Guangzhou 510275, P. R. China
Address at time of publication: Department of Mathematics, Syracuse University, Syracuse, New York 13244

Keywords: Multidimensional Fourier transform, multidimensional backward Fourier transform
Received by editor(s): May 9, 2012
Received by editor(s) in revised form: January 6, 2013
Published electronically: February 11, 2014
Additional Notes: This work was supported in part by the Guangdong Provincial Government of China through the “Computational Science Innovative Research Team” program.
The authors were supported in part by the Young Scientist Fund of the National Natural Science Foundation of China under grant 11101439 and the Doctor Program Foundation of Ministry of Education of China under grant 20100171120038.
The second author (corresponding author) was supported in part by the US Air Force Office of Scientific Research under grant FA9550-09-1-0511, by the US National Science Foundation under grant DMS-1115523, and by the Natural Science Foundation of China under grants 11071286 and 91130009.
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society