《基於自適應結構格線的NUFFT並行算法研究》是依託北京套用物理與計算數學研究所，由郭紅擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：基於自適應結構格線的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核。
