论文部分内容阅读
快速傅里叶变换（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计算的速度。