近日，清华大学丘成桐数学科学中心助理教授王珺与美国纽约大学以及弗莱替伦（Flatiron）研究所合作者在快速算法研究领域取得新进展。研究团队融合了快速算法领域的多种思想方法和新近成果，设计出快速高斯变换的新型算法，同时首次实现了在快速算法内部进行自适应网格的选取。

图1.本期《美国工业和应用数学会评论》（SIAM Review）封面

高斯变换或其离散形式是应用与计算数学中常见的计算任务，在微分方程数值解、统计学、图像处理等诸多领域中均有广泛的应用。自上世纪九十年代以来，快速高斯变换作为快速算法领域的一个重要问题得到广泛研究。该研究旨在将高斯变换的时间复杂度从O（MN）（假设在N个格点上计算M个高斯程序的和）降至O（M+N），并在此基础上尽可能地提高实际计算效率。快速高斯变换的早期算法包括基于埃尔米特（Hermite）展开的单层算法、基于傅立叶方法的“扫描”算法等。但实际应用中，上述算法在实际计算效率、自适应性、对参数的依赖性、鲁棒性等方面仍具有一定的瓶颈，限制了算法的使用范围。

研究团队融合了快速算法领域的多种思想方法和最新研究成果，如单层算法中的平面波展开（plane wave expansion）、快速多极子算法的多层树结构与“近场”和“远场”的分治与转换、“近场”计算的非均匀傅立叶变换（NUFFT）方法等，设计出快速高斯变换的新型算法，最终达到了大于等于快速傅立叶变换（FFT）的平均计算效率。不同于FFT，新型快速高斯变换天然支持自适应网格，这在需要非均匀计算网格的实际问题中至关重要。

该算法还首次实现了在快速算法内部进行自适应网格的选取，即：用户仅需要输入给定网格上被精确表示的分布f（x），算法（以可忽略的时间）自动调整网格，并返回其上精确表示的积分变换，这极大地增强了算法的鲁棒性。正如期刊编辑在推荐语中所说，该算法除了精巧的算法结构和多种数学工具的综合应用之外，还为多项后续研究奠定了基础。清华大学丘成桐数学科学中心的王珺研究小组正在开展基于该项研究成果的扩散问题、流体力学问题的相关研究。算法对应的科学计算软件包（实现了基于OpenMP的并行）将在近期发布。

图2.连续型快速高斯变换的算例（格点数：4*10^6，容差：10^{-12}。）用户输入：分布函数f（左上），初始网格（左下）；算法返回：积分变换（右上），自适应网格（右下）

相关研究成果以“离散与连续型高斯变换的新型自适应快速算法”（A New Version of the Adaptive Fast Gauss Transform for Discrete and Continuous Sources）为题发表于《美国工业和应用数学会评论》（SIAM Review）的“热点研究（Research Spotlight）”版面。

本论文由纽约大学教授、弗莱替伦（Flatiron）研究所计算数学中心主任莱斯利·格林加德（Leslie Greengard），弗莱替伦研究所高级研究员蒋世东，弗莱替伦研究所研究员马纳斯·拉奇（Manas Rachh），清华大学丘成桐数学科学中心助理教授王珺合作完成。