A PARALLEL NONUNIFORM FAST FOURIER TRANSFORM LIBRARY BASED ON AN "EXPONENTIAL OF SEMICIRCLE" KERNEL
A PARALLEL NONUNIFORM FAST FOURIER TRANSFORM LIBRARY BASED ON AN "EXPONENTIAL OF SEMICIRCLE" KERNEL
复制标题
DOI：
10.1137/18m120885x
复制
发表时间：
2019-01-01
影响因子：
3.1
通讯作者：
Klinteberg, Ludvig A. F.
中科院分区：
文献类型：
--
作者：
Barnett, Alexander H.;Magland, Jeremy;Klinteberg, Ludvig A. F.
非均匀快速傅里叶变换（NUFFT）将FFT推广到离网数据。它的许多应用包括图像重建、数据分析和微分方程的数值解。我们提出了FINUFFT，一个有效的并行库类型1（非均匀的均匀），类型2（均匀的非均匀），或类型3（非均匀的非均匀）变换，在尺寸1，2，或3。它使用最少的RAM，不需要预先计算或计划步骤，并且具有与多种语言的简单接口。我们通过一个简单的新内核-在一个高速缓存感知的负载平衡多线程实现中，在非均匀点和精细网格之间执行昂贵的扩展/插值-x中的“指数”e（beta root 1-x2）是[-1，1]的元素。反卷积步骤需要的内核，我们提出了有效的数值积分的傅里叶变换。对于类型1和2，严格的误差界渐近的内核宽度接近最快的已知指数率，即凯撒-贝塞尔内核。我们对几个流行的基于CPU的库进行了基准测试，显示出良好的速度和内存占用，特别是在需要高精度和/或聚类点分布的三维空间中。
The nonuniform fast Fourier transform (NUFFT) generalizes the FFT to off-grid data. Its many applications include image reconstruction, data analysis, and the numerical solution of differential equations. We present FINUFFT, an efficient parallel library for type 1 (nonuniform to uniform), type 2 (uniform to nonuniform), or type 3 (nonuniform to nonuniform) transforms, in dimensions 1, 2, or 3. It uses minimal RAM, requires no precomputation or plan steps, and has a simple interface to several languages. We perform the expensive spreading/interpolation between nonuniform points and the fine grid via a simple new kernel-the "exponential of semicircle" e(beta root 1-x2) in x is an element of [-1, 1]-in a cache-aware load-balanced multithreaded implementation. The deconvolution step requires the Fourier transform of the kernel, for which we propose efficient numerical quadrature. For types 1 and 2, rigorous error bounds asymptotic in the kernel width approach the fastest known exponential rate, namely that of the Kaiser-Bessel kernel. We benchmark against several popular CPU-based libraries, showing favorable speed and memory footprint, especially in three dimensions when high accuracy and/or clustered point distributions are desired.