清华大学 数学中心王珺合作发现新型自适应高斯变换算法
2024/06/17
近日,清华大学丘成桐数学科学中心助理教授王珺与美国纽约大学以及弗莱替伦(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),清华大学丘成桐数学科学中心助理教授王珺合作完成。
文章来源清华大学新闻,分享只为学术交流,如涉及侵权问题请联系我们,我们将及时修改或删除。
-
2026年1月高含金量国际学术会议合 12-12
-
第四届金融科技与商业分析国际学术会议 686
-
2026年第十一届复合材料与材料工程 1453
-
2025年机器视觉、智能成像与模式识 2126
-
2025年智能光子学与应用技术国际学 3284
-
2026年机械工程,新能源与电气技术 3476
-
2025年计算机科学、图像分析与信号 3917
-
2025年材料化学与燃料电池技术国际 3633
-
2026年交通数字化、人工智能与韧性 12-19
-
2026年社会文化与公共管理国际会议 12-19
-
2026年人文地理与语言研究国际会议 12-19
-
2026年社会发展与经济发展国际会议 12-19
-
2026年光伏材料、光电转换与可再生 12-19
-
2026年可持续发展与数字化社会国际 12-19
-
2026年管理科学、语言与教育国际会 12-19
-
2025年两院院士增选有效候选人2672
-
2025最新JCR分区及影响因子7552
-
好学术:科研网址导航|学术头条分3540
-
2025年国际期刊预警名单发布!3510
-
2025年中科院期刊分区表重磅发13412
-
中国科协《重要学术会议目录(207866
-
吉林大学校长张希:学术会议中的提4517
-
中国科大提出电化学一体化驱动策12-19
-
中国科大实现电泵浦片上集成高亮度12-19
-
西北农林科技大学【陕西新闻联播】12-19
-
中国科大实现片上非相干泵浦高品质12-19
-
中国科大中性原子量子计算研究成果12-19
-
炔烃远端C-O键的不对称活化转化12-19
-
研究揭示叶片内生真菌分子功能多样12-19
-
科研人员提出柑橘黄龙病防控新策略12-19
-
沈阳博思有限公司 18139

-
北京晟勋炎国际会议服务中心 18122

-
闽江学院 23154

-
北京电子科技学院 2083

-
北京凤凰假期国际旅行社有限公司 2040

-
北京国际温泉酒店体育健身中心 21390

-
香港中文大学 24120

-
上海信谊药厂有限公司 18365

-
北京外国语大学 21168

-
辽宁石油化工大学 8204

-
中国国际科技会展中心 23156

-
International As 2185

-
中国石油大学(华东) 2168

-
中华医学会急诊医学分会 21977

-
中国土壤学会土壤化学专业委员会 21192

-
天津市硅酸盐学会 8123

-
北京中外联企业文化交流中心 2026

-
百奥泰国际会议(大连)有限公司 8075

-
广东省眼健康协会 2235

-
河南理工大学经济管理学院 18149

















689









































