六边形稀疏网格上的FFT算法

摘要

稀疏网格是一种具有特殊分层插值性质的非均匀网格形式,稀疏网格上的离散傅立叶变换算法称为Hyperbolic Cross FFT算法.这一算法能够有效降低采样点数量,并将指数时间复杂度的d维DFT算法降低到O(Nlogd N) [10].六边形网格是另一种具有特殊性质的网格,具有在采样点数量较少和采样效率较高等优势.本文的研究工作主要集中在将六边形网格和稀疏网格相结合,构造六边形稀疏网格上的FFT算法.通过定义六边形和方形网格下标之间的转换,实现了六边形稀疏网格上的FFT算法,并通过数值实验证明了这一算法的有效性.