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)更新数值分析本科课程的标准课程，以反映有关数值算法的新思维模式（特别是在经典意义上不“收敛”的方法的发展，但可以解决指定的任务，以任何预设的精度）。这项工作将与纽约大学的莱斯利·格林加德和耶鲁大学的弗拉基米尔·罗克林密切合作进行。