论文部分内容阅读
快速傅里叶变换(Fast Fourier Transform,FFT)是一种应用十分广泛的数值算法。在对高维离散傅立叶变换的研究过程中,人们发现,随着维数的升高,快速傅里叶变换算法的时间复杂度与维数呈指数关系。在传统的均匀节点网格上,这一问题难以得到有效解决。此外,均匀网格对网格点分布要求严格,导致其不能应用在一些采样点不均匀分布的计算中。近年来,非均匀网格上的快速傅里叶变换因为能够有效解决上述问题,逐渐引起了人们的重视。 在大气湍流模拟谱反演法中,需要对倍增频率的采样点进行离散傅里叶变换,传统FFT算法难以应用到此计算中。本文的研究工作通过引入非均匀节点的离散傅里叶变换,将问题抽象化为非均匀节点上的FFT计算模型,并移植NFFT3.0非均匀节点快速傅里叶算法程序包进行计算。我们成功地将算法时间复杂度从O(N2)降低到O(N log N),N为节点总数。在N=1024×1024时,优化后的算法经测试,速度提升了5000倍以上。 稀疏网格作为一种非均匀网格形式,是降低高维问题时间复杂度的有效工具。已有在稀疏网格上进行快速傅里叶变换的Hyperbolic Cross FFT算法。这一算法能够有效降低采样点数量,并将关于维数d呈指数时间复杂度的d维DFT算法的时间复杂度降低到O(N logd N)[22],有效地解决了高维网格上传统FFT算法因为时间复杂度过高导致难以计算的问题。 六边形网格是另一种具有特殊性质的网格。除了矩形之外,六边形也是自然界普遍存在的一种基本图形,具有良好的对称性和自镶嵌性以及其他独特的性质。在信号处理等领域,当对各向同性的函数进行采样时,六边形网格比正方形网格更为高效[36]。因此,六边形网格往往能够处理一些矩形网格不擅长的问题。 本文的研究工作主要集中在将六边形网格和稀疏网格相结合,构造六边形稀疏网格上的FFT算法。我们首先通过对六边形进行区域分解,并通过分类讨论的方式推导DFT计算式。推导过程中利用了六边形下标运算时具有的模3同余特性,将计算式转换到2维方形网格。在此基础上,我们在六边形上定义稀疏网格及与之对应的Hyperbolic Cross频域空间,设计并实现了六边形稀疏网格上的FFT算法。 经过理论研究和数值实验,证明这一六边形稀疏网格上的FFT算法具有较低的时间复杂度。相比均匀六边形网格上的FFT算法,六边形稀疏网格上的FFT算法能够适应更大规模的数据并加快了DFT计算的速度。