CAREER: Fast Direct Solvers for Differential and Integral Equations

职业：微分方程和积分方程的快速直接求解器

• 批准号: 0748488
• 负责人: Per-Gunnar Martinsson
• 金额: $ 40万
• 依托单位: University of Colorado at Boulder
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0748488&HistoricalAwards=false
• 关键词: CAREER; Fast; Direct; Solvers; Differential

Over the last several decades, the development of powerful computers and fast algorithms has dramatically increased our capability to computationally model a broad range of phenomena in science and engineering. Our newfound ability to design complex systems (cars, new materials, city infrastructures, etc.) via computer simulations rather than physical experiments has in many fields led to both cost savings and profound improvements in performance. Intense efforts are currently being made to extend these advances to biochemistry, physiology, and several other areas in the biological and medical sciences. The goal of the proposed research is to develop faster and more accurate algorithms for computing approximate solutions to a class of mathematical equations called "partial differential equations" (PDEs) that lie at the core of models of physical phenomena such as heat transport, deformation of elastic bodies, scattering of electro-magnetic waves, and many others. The task of solving such equations is frequently the most time-consuming part of computational simulations, and is the part that determines which problems can be modeled computationally, and which cannot. Technically speaking, most existing numerical algorithms for solving large PDE problems use "iterative methods," which construct a sequence of approximate solutions that gradually approach the exact solution. The proposed research seeks to develop "direct methods" for solving many PDEs. Loosely speaking, a direct method computes the unknown data from the given data in one shot. Direct methods are generally preferred to iterative ones since they are more robust, are more suitable for incorporation in general-purpose software, and work for important problems that cannot be solved with known iterative methods. The reason that they are typically not used today is that they are often prohibitively expensive. However, recent results by the PI and other researchers indicate that it is possible to construct direct methods that are competitive in terms of speed with the very fastest known iterative solvers. In fact, in several important applications, the direct methods appear to be one or two orders of magnitude faster than existing iterative methods. In addition to constructing faster algorithms, a core goal of the proposed research is to demonstrate the capabilities of the new methods by applying them to a number of technologically important problems that are not amenable to existing techniques. These problems include scattering problems at frequencies close to a resonance frequency of the scatterer, modeling of crack propagation in composite materials, and the modeling of large bio-molecules in ionic solutions. An integral part of the proposed work is the development of new educational material on computational techniques. Specific goals include: (1) The development of a textbook on so called "Fast Multipole Methods." (2) The development of a new graduate-level class on fast algorithms for solving PDEs. (3) The updating of the standard curriculum of undergraduate classes in numerical analysis to reflect new modes of thinking about numerical algorithms (specifically the development of methods that are not "convergent" in the classical sense, but that can solve specified tasks to any preset accuracy). This work is to be undertaken in close collaboration with Leslie Greengard at NYU and Vladimir Rokhlin at Yale University.

在过去的几十年里，强大的计算机和快速算法的发展极大地提高了我们对科学和工程中广泛现象进行计算建模的能力。我们通过计算机模拟而不是物理实验来设计复杂系统（汽车、新材料、城市基础设施等）的新能力，在许多领域既节省了成本，又大大提高了性能。目前正在加紧努力将这些进展扩展到生物化学、生理学以及生物和医学科学的其他几个领域。这项研究的目标是开发更快、更精确的算法，用于计算一类被称为“偏微分方程”（PDEs）的数学方程的近似解，这些方程是热传输、弹性体变形、电磁波散射等物理现象模型的核心。求解这类方程的任务通常是计算模拟中最耗时的部分，它决定了哪些问题可以通过计算建模，哪些问题不能。从技术上讲，大多数用于解决大型PDE问题的现有数值算法都使用“迭代方法”，即构造一个逐渐接近精确解的近似解序列。拟议的研究旨在开发解决许多偏微分方程的“直接方法”。粗略地说，直接方法是一次性从给定数据中计算未知数据。直接方法通常比迭代方法更受欢迎，因为它们更健壮，更适合合并到通用软件中，并且适用于无法用已知迭代方法解决的重要问题。它们现在不常用的原因是它们通常太贵了。然而，PI和其他研究人员最近的结果表明，有可能构建在速度方面与已知最快的迭代求解器竞争的直接方法。事实上，在一些重要的应用中，直接方法似乎比现有的迭代方法快一到两个数量级。除了构建更快的算法之外，拟议研究的一个核心目标是通过将新方法应用于一些现有技术无法解决的技术重要问题来证明新方法的能力。这些问题包括在接近散射体共振频率的频率上的散射问题，复合材料中裂纹扩展的建模，以及离子溶液中大型生物分子的建模。拟议工作的一个组成部分是开发关于计算技术的新教材。具体目标包括：(1)编写一本关于所谓“快速多极方法”的教科书。(2)开设一个新的研究生水平课程，学习快速求解偏微分方程的算法。(3)更新数值分析本科课程的标准课程，以反映关于数值算法的新思维模式（具体来说，不是经典意义上的“收敛”，而是能够以任何预设精度解决特定任务的方法的发展）。这项工作将与纽约大学的莱斯利·格林加德和耶鲁大学的弗拉基米尔·罗克林密切合作。