Back to Search
Start Over
The Chebyshev fast Gauss and nonuniform fast Fourier transforms and their application to the evaluation of distributed heat potentials
- Source :
-
Journal of Computational Physics . Aug2008, Vol. 227 Issue 16, p7768-7790. 23p. - Publication Year :
- 2008
-
Abstract
- Abstract: We present a method for the fast and accurate computation of distributed heat potentials in two dimensions. The distributed source is assumed to be given in terms of piecewise space–time Chebyshev polynomials. We discretize uniformly in time, whereas in space the polynomials are defined on the leaf nodes of a quadtree. The quadtree can vary at each time step. We combine a product integration rule with fast algorithms (fast heat potentials, nonuniform FFT, fast Gauss transform) to obtain a high-order accurate method with optimal complexity. If N is the number of time steps, M is the maximum number of leaf nodes over all the time steps and the input contains a qth-order polynomial representation of f, then, our method requires work to evaluate the heat potential at arbitrary space–time target locations. The overall convergence rate of the method is of order q. We present numerical experiments for q =4, 8, and 16, and we verify the theoretical convergence rate of the method. When the solution is sufficiently smooth, the 16th-order variant results in significant computational savings, even in the case in which we require only a few digits of accuracy. [Copyright &y& Elsevier]
- Subjects :
- *CHEBYSHEV series
*FOURIER transforms
*POLYNOMIALS
*NUMERICAL analysis
Subjects
Details
- Language :
- English
- ISSN :
- 00219991
- Volume :
- 227
- Issue :
- 16
- Database :
- Academic Search Index
- Journal :
- Journal of Computational Physics
- Publication Type :
- Academic Journal
- Accession number :
- 32988177
- Full Text :
- https://doi.org/10.1016/j.jcp.2008.05.003