Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 

 

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?)


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
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
Email: yxu06@syr.edu

DOI: https://doi.org/10.1090/S0025-5718-2014-02785-3
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