Fast Fourier transforms of piecewise polynomials

被引：3
作者：
Strain, John [1 ]
机构：
[1] Univ Calif Berkeley, Dept Math, 970 Evans Hall, Berkeley, CA 94720 USA
来源：
JOURNAL OF COMPUTATIONAL PHYSICS | 2018年 / 373卷
关键词：
Fourier transform; Butterfly algorithm; Spectral methods; ALGORITHM;
D O I：
10.1016/j.jcp.2018.06.076
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
We introduce an efficient algorithm for evaluating the Fourier transform of piecewise-polynomial data on d-dimensional simplices in D-dimensional Euclidean space R-D. It generalizes butterfly algorithms for pointwise (d = 0) nonuniform fast Fourier transforms, with new dimensional recurrences for exponential-polynomial moments. Error analysis and numerical comparisons with direct evaluation validate the efficiency and accuracy of the algorithm. (C) 2018 Elsevier Inc. All rights reserved.
引用
收藏
页码：346 / 369
页数：24
相关论文
共 45 条
[1]   The change-of-variables formula using matrix volume [J].
Ben-Israel, A .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1999, 21 (01) :300-312
[2]   ON THE FAST FOURIER-TRANSFORM OF FUNCTIONS WITH SINGULARITIES [J].
BEYLKIN, G .
APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS, 1995, 2 (04) :363-381
[3]   An analysis of a butterfly algorithm [J].
Boerm, S. ;
Boerst, C. ;
Melenk, J. M. .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2017, 74 (09) :2125-2143
[4]   A fast Fourier-Galerkin method for solving singular boundary integral equations [J].
Cai, Haotao ;
Xu, Yuesheng .
SIAM JOURNAL ON NUMERICAL ANALYSIS, 2008, 46 (04) :1965-1984
[5]  
Candes E. J., 2008, SIAM J MULTISCALE MO, V7, P1727
[6]   AN ALGORITHM FOR MACHINE CALCULATION OF COMPLEX FOURIER SERIES [J].
COOLEY, JW ;
TUKEY, JW .
MATHEMATICS OF COMPUTATION, 1965, 19 (90) :297-&
[7]   An encyclopaedia of cubature formulas [J].
Cools, R .
JOURNAL OF COMPLEXITY, 2003, 19 (03) :445-453
[8]  
Davis P.J., 1984, Methods of Numerical Integration, Vsecond
[9]   A Butterfly Algorithm for Synthetic Aperture Radar Imaging [J].
Demanet, Laurent ;
Ferrara, Matthew ;
Maxwell, Nicholas ;
Poulson, Jack ;
Ying, Lexing .
SIAM JOURNAL ON IMAGING SCIENCES, 2012, 5 (01) :203-243
[10]   FAST FOURIER-TRANSFORMS FOR NONEQUISPACED DATA [J].
DUTT, A ;
ROKHLIN, V .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 1993, 14 (06) :1368-1393
12345