Fast Direct Solvers for Boundary Integral Equations

University Of Colorado At Boulder, Boulder CO

Investigators

Abstract

The proposed research seeks to develop fast, accurate, and robust computational techniques for solving a class of mathematical equations known as "linear boundary-value problems". Such equations are ubiquitous in engineering and science, and the task of finding approximate solutions to them is frequently the most expensive component of numerical simulations. There currently exists a multitude of computational techniques for solving linear boundary-value problems, including some that are both highly accurate and very fast. The emergence of such methods over the last two decades has vastly increased our ability to simulate complex phenomena in science, engineering, medicine, and many other fields. However, existing high-performance computational techniques tend to be limited in their applicability, and somewhat fickle, in the sense that software needs problem-specific tuning to perform well. The principal goal of the proposed research is to eliminate these drawbacks for a particular class of high-performance techniques, thus making such algorithms accessible to a wide range of important computational problems. Technically speaking, the proposed research is concerned with a class of computational techniques based on formulating the problem as an equation on the boundary of the computational domain. It is known that the resulting equations can in some environments be solved extraordinarily rapidly. Existing techniques for this task are based on so-called "iterative solvers", which construct a sequence of approximate solutions that gradually approach the exact solution. The proposed research seeks to develop "direct solvers" for solving the boundary equations. Loosely speaking, a "direct solver" manipulates the mathematical equation to produce an algorithm that determines the unknown variables from the given data in one shot. Direct solvers are generally preferred to iterative ones, but they have in many environments appeared to be prohibitively expensive. However, recent developments indicate that it is possible to construct direct methods that are as fast as, and sometimes even faster than, existing iterative ones. Many benefits would accrue from the development of direct methods for solving the boundary equations associated with linear boundary-value problems; these include: (1) The ability to solve certain problems that are beyond the reach of existing fast algorithms. An example is the accurate solution of electromagnetic and acoustic scattering problems involving large objects at wave frequencies close to resonant frequencies of the scatterer. (2) An increase in computational speed in environments where the same equation needs to be solved multiple times for different data. Preliminary experiments involving the modeling of biochemical processes and large scattering problems indicate that a speed-up of one or two orders of magnitude is to be expected. (3) The availability of high-performance computational techniques that are sufficiently robust to be incorporated into general purpose software packages.