稀疏网格是一种具有特殊分层插值性质的非均匀网格形式,稀疏网格上的离散傅立叶变换算法称为Hyperbolic Cross FFT算法.这一算法能够有效降低采样点数量,并将指数时间复杂度的d维DFT算法降低到O(NlogdN).六边形网格是另一种具有特殊性质的网格,具有在采样点数量较少和采样效率较高等优势.本文的研究工作主要集中在将六边形网格和稀疏网格相结合,构造六边形稀疏网格上的FFT算法.通过定义六边形和方形网格下标之间的转换,实现了六边形稀疏网格上的FFT算法,并通过数值实验证明了这一算法的有效性.
Sparse grid is one of Non-uniform grid forms with special properties of hierarchical interpolation. These is an algorithm of discrete Fourier transform on sparse grid, which is called Hyperbolic Cross FFT. This algorithm effectively reduce the number of sampling points, andminimize exponential time complexity of d-dimensions DFT algorithms to O(NlogdN). Hexagonal lattice is another kind of grid which has some special propertys such as number of sampling points less and higher sampling efficiency etc. This research focus on combining hexagonal lattice with sparse grid to design FFT algorithm on hexagonal sparse grid. We successfully achieve FFT algorithm on hexagonal sparse grid by defining ahexagon and square lattice conversion between subccript. And the new algorithm is proved to be effective by numerical experiments.