基于自适应结构网格的NUFFT并行算法研究

FFT可在降低数值模拟计算复杂度的同时保证计算高精度，但其只能用于均匀采样生成的网格。在众多需要捕捉局部关键区域信息的应用FFT的数值模拟中，因受限于均匀采样而对网格全局加密，势必会因计算资源的有限性而影响关键区域网格密度，无法有效捕捉局部信息。为解决这一问题，申请者尝试将自适应结构网格加密方法(SAMR)与FFT结合，这面临两个挑战。一是在非均匀采样网格上计算FFT。尽管有学者提出了非一致FFT(NUFFT)来解决，但现有NUFFT大多网格针对性很强，对于由SAMR生成的具有明显局部特性的表层网格不具普适性，必须开发新的NUFFT算法。二是NUFFT的并行算法,这在国内外仍属空白。本项目主要研究：适用于SAMR的NUFFT串行算法；适用于SAMR的NUFFT并行算法；面向上千个处理器的适用于SAMR的NUFFT可扩展并行软件。旨在降低程序研制难度、缩短程序研制周期，为相关需求者提供支撑。

FFT只能用于均匀采样生成的网格，然而在众多需要捕捉局部关键区域信息的应用FFT的数值模拟中，因受限于均匀采样而对网格全局加密，势必会因计算资源的限制而影响关键区域网格密度，无法有效捕捉局部信息。为解决这一问题，我们将自适应结构网格加密方法(SAMR)与FFT结合。这面临两个挑战。一是现有的用于非均匀采样的FFT算法，即NUFFT算法，不适应由SAMR生成的具有明显局部特征的表层网格，必须开发新的NUFFT算法。二是国内外尚不存在NUFFT并行算法。对于挑战一，我们首先将NUFFT算法分解为三部分，即非均匀采样网格到均匀采样网格的插值、均匀采样网格中的FFT计算、均匀采样网格到非均匀采样网格的插值；其次，采用了适应于SAMR网格的线性插值算法代替传统NUFFT算法中选取窗口函数利用卷积插值的算法，构造了针对SAMR网格的NUFFT算法。对于挑战二，我们针对NUFFT算法的三个部分分别构造了可扩展的并行算法：构造了可以扩展至数千核的FFT并行算法用于NUFFT算法中的FFT计算，构造了可以扩展至上万核的不同分辨率网格间的并行插值算法用于网格间的插值计算。测试结果表明，上述两种并行算法解决了国际同类并行算法难以扩展的瓶颈问题。在成功构造算法的基础上，分离算法共性与个性，集成研究成果，研制NUFFT并行解法器，并将该解法器初步应用到激光等离子体成丝不稳定性自适应数值模拟中。应用结果表明，NUFFT并行解法器可以支撑该数值模拟扩展至8192核。