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

HTML articles powered by AMS MathViewer

- by Ying Jiang and Yuesheng Xu PDF
- Math. Comp.
**83**(2014), 2347-2384 Request permission

## 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

- 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**, DOI 10.1137/S1064827593247035 - Kai Bittner,
*Fast algorithms for periodic spline wavelets on sparse grids*, SIAM J. Sci. Comput.**20**(1999), no. 4, 1192–1213. MR**1675469**, DOI 10.1137/S1064827596309098 - Hans-Joachim Bungartz,
*A multigrid algorithm for higher order finite elements on sparse grids*, Electron. Trans. Numer. Anal.**6**(1997), no. Dec., 63–77. Special issue on multilevel methods (Copper Mountain, CO, 1997). MR**1615156** - Hans-Joachim Bungartz and Michael Griebel,
*Sparse grids*, Acta Numer.**13**(2004), 147–269. MR**2249147**, DOI 10.1017/S0962492904000182 - 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**, DOI 10.1137/070703478 - 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**, DOI 10.1090/S0025-5718-99-01110-2 - James W. Cooley and John W. Tukey,
*An algorithm for the machine calculation of complex Fourier series*, Math. Comp.**19**(1965), 297–301. MR**178586**, DOI 10.1090/S0025-5718-1965-0178586-1 - 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** - 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**, DOI 10.1137/090754947 - 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**, DOI 10.1006/jcom.1996.0004 - 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**, DOI 10.1007/s00607-007-0225-3 - 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**, DOI 10.1137/050629823 - M. Griebel and S. Knapek,
*Optimized general sparse grid approximation spaces for operator equations*, Math. Comp.**78**(2009), no. 268, 2223–2257. MR**2521287**, DOI 10.1090/S0025-5718-09-02248-0 - 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**, DOI 10.1007/BF01385849 - 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**, DOI 10.1016/j.jco.2009.10.001 - 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**, DOI 10.1016/j.cam.2010.01.022 - Ying Jiang and Yuesheng Xu,
*B-spline quasi-interpolation on sparse grids*, J. Complexity**27**(2011), no. 5, 466–488. MR**2805532**, DOI 10.1016/j.jco.2011.03.003 - S. Knapek,
*Hyperbolic cross approximation of integral operators with smooth kernel*, Technical Report 665, SFB 256, Univ. Bonn, 2000. - N. S. Nikol′skaja,
*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** - 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**, DOI 10.1007/BF00970164 - 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**, DOI 10.1137/100787842 - V. N. Temlyakov,
*Approximations of functions with bounded mixed derivative*, Trudy Mat. Inst. Steklov.**178**(1986), 113 (Russian). MR**847439** - V. N. Temlyakov,
*Approximation of periodic functions*, Computational Mathematics and Analysis Series, Nova Science Publishers, Inc., Commack, NY, 1993. MR**1373654** - 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**, DOI 10.1007/s11425-010-0014-x - 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**, DOI 10.1216/jiea/1181075260 - Andreas Zeiser,
*Fast matrix-vector multiplication in the sparse-grid Galerkin method*, J. Sci. Comput.**47**(2011), no. 3, 328–346. MR**2793587**, DOI 10.1007/s10915-010-9438-2

## 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
- Email: yjiang80@gmail.com
**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
- MR Author ID: 214352
- Email: yxu06@syr.edu
- 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. - © Copyright 2014 American Mathematical Society
- Journal: Math. Comp.
**83**(2014), 2347-2384 - MSC (2010): Primary 65T50
- DOI: https://doi.org/10.1090/S0025-5718-2014-02785-3
- MathSciNet review: 3223335