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.

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