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