清華新聞網(wǎng)6月5日電 近日，清華大學(xué)丘成桐數(shù)學(xué)科學(xué)中心助理教授王珺與美國紐約大學(xué)以及弗萊替?zhèn)悾‵latiron）研究所合作者在快速算法研究領(lǐng)域取得新進展。研究團隊融合了快速算法領(lǐng)域的多種思想方法和新近成果，設(shè)計出快速高斯變換的新型算法，同時首次實現(xiàn)了在快速算法內(nèi)部進行自適應(yīng)網(wǎng)格的選取。
圖1.本期《美國工業(yè)和應(yīng)用數(shù)學(xué)會評論》（SIAM Review）封面
高斯變換或其離散形式是應(yīng)用與計算數(shù)學(xué)中常見的計算任務(wù)，在微分方程數(shù)值解、統(tǒng)計學(xué)、圖像處理等諸多領(lǐng)域中均有廣泛的應(yīng)用。自上世紀(jì)九十年代以來，快速高斯變換作為快速算法領(lǐng)域的一個重要問題得到廣泛研究。該研究旨在將高斯變換的時間復(fù)雜度從O（MN）（假設(shè)在N個格點上計算M個高斯程序的和）降至O（M+N），并在此基礎(chǔ)上盡可能地提高實際計算效率。快速高斯變換的早期算法包括基于埃爾米特（Hermite）展開的單層算法、基于傅立葉方法的“掃描”算法等。但實際應(yīng)用中，上述算法在實際計算效率、自適應(yīng)性、對參數(shù)的依賴性、魯棒性等方面仍具有一定的瓶頸，限制了算法的使用范圍。
研究團隊融合了快速算法領(lǐng)域的多種思想方法和最新研究成果，如單層算法中的平面波展開（plane wave expansion）、快速多極子算法的多層樹結(jié)構(gòu)與“近場”和“遠(yuǎn)場”的分治與轉(zhuǎn)換、“近場”計算的非均勻傅立葉變換（NUFFT）方法等，設(shè)計出快速高斯變換的新型算法，最終達到了大于等于快速傅立葉變換（FFT）的平均計算效率。不同于FFT，新型快速高斯變換天然支持自適應(yīng)網(wǎng)格，這在需要非均勻計算網(wǎng)格的實際問題中至關(guān)重要。
該算法還首次實現(xiàn)了在快速算法內(nèi)部進行自適應(yīng)網(wǎng)格的選取，即：用戶僅需要輸入給定網(wǎng)格上被精確表示的分布f（x），算法（以可忽略的時間）自動調(diào)整網(wǎng)格，并返回其上精確表示的積分變換，這極大地增強了算法的魯棒性。正如期刊編輯在推薦語中所說，該算法除了精巧的算法結(jié)構(gòu)和多種數(shù)學(xué)工具的綜合應(yīng)用之外，還為多項后續(xù)研究奠定了基礎(chǔ)。清華大學(xué)丘成桐數(shù)學(xué)科學(xué)中心的王珺研究小組正在開展基于該項研究成果的擴散問題、流體力學(xué)問題的相關(guān)研究。算法對應(yīng)的科學(xué)計算軟件包（實現(xiàn)了基于OpenMP的并行）將在近期發(fā)布。
圖2.連續(xù)型快速高斯變換的算例（格點數(shù)：4*10^6，容差：10^{-12}。）用戶輸入：分布函數(shù)f（左上），初始網(wǎng)格（左下）；算法返回：積分變換（右上），自適應(yīng)網(wǎng)格（右下）
相關(guān)研究成果以“離散與連續(xù)型高斯變換的新型自適應(yīng)快速算法”（A New Version of the Adaptive Fast Gauss Transform for Discrete and Continuous Sources）為題發(fā)表于《美國工業(yè)和應(yīng)用數(shù)學(xué)會評論》（SIAM Review）的“熱點研究（Research Spotlight）”版面。
本論文由紐約大學(xué)教授、弗萊替?zhèn)悾‵latiron）研究所計算數(shù)學(xué)中心主任萊斯利·格林加德（Leslie Greengard），弗萊替?zhèn)愌芯克呒壯芯繂T蔣世東，弗萊替?zhèn)愌芯克芯繂T馬納斯·拉奇（Manas Rachh），清華大學(xué)丘成桐數(shù)學(xué)科學(xué)中心助理教授王珺合作完成。
論文鏈接：
https://epubs.siam.org/doi/10.1137/23M1572453
供稿：數(shù)學(xué)科學(xué)中心
編輯：李華山
審核：郭玲
