Fast Direct Solvers for Elliptic PDEs

This book offers an introduction to the efficient computational solution of elliptic partial differential equations (PDEs) using fast multipole methods and techniques that employ integral equation formulations. 

 

Elliptic PDEs are particularly challenging because they model interactions that are global and not local. Applications include a variety of equilibrium situations including structural mechanics, electrostatics, and steady fluid flow. Laplace’s, Helmholtz’s and Poisson’s equations are examples of elliptic PDEs.

 

The first half of the text concentrates on integral equation formulations and fast summation methods. The remainder deals with what are called fast direct solvers. With fast direct solvers the key idea is to use very efficient methods for computing an inverse or LU factorization of the matrix that arises from discretization of a PDE or its associated integral equation. Such discretizations arise when applying finite difference or finite element numerical methods.

 

The author devotes a good deal of attention to linear algebra early in the book. Topics here include iterated decomposition of matrices, randomized techniques for matrix factorization, and fast algorithms for rank-structured matrices. All of these techniques are applicable to the solution methods for elliptic PDEs and integral equations described later. Fast algorithms for integral equations with associated dense matrices are possible because off-diagonal blocks typically have low numerical rank.

 

It is advantageous in many situations to use integral equation formulations of PDEs.  The author shows how many problems with elliptic equations can be formulated as integral equations in ways that are especially desirable for promoting stable and accurate numerical solutions.

 

The last half of the book concentrates specifically fast direct solvers. First a general approach is described for discretized integral equations. Then the author focuses on fast direct solvers for linear elliptic PDEs where the discretization leads to a sparse coefficient matrix. Much of the material of the last six chapters describes areas of active research.

 

The author organized the book to make the sections relatively independent, and thereby more accessible to a variety of readers. Essential prior background includes a good deal of numerical linear algebra, familiarity with elliptic PDEs and their properties, and knowledge of the basics of potential theory. An extensive bibliography is provided, but there are no exercises. For the most part, this is a book more suitable for advanced graduate students or researchers. 

---

 

Bill Satzer (bsatzer@gmail.com), now retired from 3M Company, spent most of his career as a mathematician working in industry on a variety of applications. He did his PhD work in dynamical systems and celestial mechanics.