CAREER: Fast Direct Solvers for Differential and Integral Equations

University Of Colorado At Boulder, Boulder CO

Investigators

Abstract

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.