CBMS/NSF Conference on Fast Direct Solvers, June 2014
Dartmouth College, June 23 - 27, 2014
The Fast Multipole Method
Early descriptions of the FMM include a
by Vladimir Rokhlin, and
the seminal 1987 JCP paper
Leslie Greengard and VR.
The description of the FMM in Lecture 2 follows this encyclopedia entry
Detailed descriptions of the FMM are given in, e.g, the
of Leslie Greengard, a
on FMMs by Rick Beatson and Leslie Greengard,
by Liu and Nishimura,
and a variety of books, including
by Chew, Jin, Michielssen, and Son, and
by Yijun Liu.
Adaptivity is described in a
1988 SISC paper
Carrier, Greengard, and Rokhlin.
An essential improvement to the FMM that allows high speed for Laplace problems in 3D is described
The profoundly remarkable fact that FMMs can be constructed for high-frequency Helmholtz problems (where, recall,
the rank considerations used for Laplace no longer work) was discovered by Rokhlin and is published
. For a more comprehensive description of these algorithms, see
An FMM based on the interpolative decomposition (ID) is described
A general collection of references on the FMM is to be found at fastmultipole.org
Randomized methods for low-rank approximation
provides an accessible introduction. It is 72 pages long,
but the introduction (Section 1) can be read on its own and provides a brief
Another, briefer, introduction is given in this
2011 PNAS paper.
The original paper we published on these methods is
2006 tech report.
The report was (after two rejections...) eventually published
For a full description of the intellectual pedigree of these methods, please see the
mentioned earlier, and also
survey by Michael Mahoney.
The interpolative decomposition (ID)
For a technical paper, see this
Randomized techniques for building the ID are described in Section 5.2 of this
1996 SISC paper
by Gu and Eisenstat provides much of the mathematical underpinnings. Earlier work on
the related Rank-Revealing QR (RRQR)
factorization includes a
by Tony Chan.
Applications to functions of a continuum variable are described
Boundary integral equations and Nyström discretization
Standard references include "Linear Integral Equations"
by Rainer Kress
(oddly, the full pdf seems to be available here
"The Numerical Solution of Integral Equations of the Second Kind"
by Kendall Atkinson. For a more mathematical treatment, see
"Strongly elliptic systems and boundary integral equations"
by William McLean.
An introduction intended to be highly accessible can be found
. This intro is still a little rough, but should
provide a quick access point.
Methods for high-order discretization of BIEs in 2D with singular kernels are described
A brief introduction to methods for handling corners can be found
Original work in this area by
Direct solvers for sparse matrices from FEM/FD discretization
A slightly outdated, but (I think!) accessible description of the ideas can be found in this
.) This is pursued further in the
of Adrianna Gillman. A journal publication on this work is
Work on so called H-LU methods which use H-matrix algebra to accelerate the nested
dissection method by Lars Grasedyck, Sabine Le Borne, and Ronald Kriemann can be found
in this 2007 paper
A 2009 SIMAX paper
J. Xia, S. Chandrasekaran, M. Gu, and X.S. Li introduced many ideas, and was later followed up
by a long sequence of papers by Jianlin Xia and co-workers, which can be found on his
Related work by Philip Schmitz and Lexing Ying is
and by Ken Ho and Lexing Ying
For a rough introduction to matrix algebra for rank-structured matrices, see
from the monograph manuscript.
Original references for H-matrix algebra include a
by Wolfgang Hackbusch. The H2
was introduced to reduce complexity from O(N (log N)k)
and is described in this
by W. Hackbusch, B. Khoromskij, and S. A. Sauter. A
by Mario Bebendorf provides a full reference to H-matrix techniques, and a
by Steffen Börm describes H2
Resources on H-matrices, including codes and an extensive bibliography, can be found
So called hierarchically off-diagonal low-rank (HODLR) matrices
are used in this
A. Aminfar, S. Ambikasaran, and E. Darve. This manuscript also contains a very informative
Direct solvers for integral equations
The original paper describing "hierarchical skeletonization" is this
which in turn builds off of a single-level scheme described
describes essentially the same method, but now applied in 3D (local copy
A cleaner description of the same algorithm, which makes the connection to HBS matrix algebra explicit, can be found in this
A variation of the same scheme, which uses a general purpose sparse structured
solver (UMFPACK) by Greengard and Ho can be found
A variation that appears to attain O(N) complexity by Ho and Ying can be found
An extension to 3D based on hierarchical merging of scattering matrices can be found
(to appear in BIT).
Acceleration to optimal O(N)
complexity for 2D volume integral equations (e.g. Lippman-Schwinger)
is described in this
2014 ACHA paper
Optimal complexity is attained by using HBS matrix algebra for the scattering matrices.
Direct solvers for integral equations based on H-matrix methods are described in the following two books:
Efficient Numerical Methods for Non-local Operators
H2-Matrix Compression, Algorithms and Analysis
, by Steffen Borm, and
, by Mario Bebendorf.
Exciting very recent work in Eric Michielssen's group seems to show that so called "butterfly" algorithms (see, e.g., this
2010 ACHA paper
by M. O'Neil,
F. Woolfe, and V. Rokhlin) can be used to build linear complexity algorithms for high frequency scattering problems.
The Hierarchical Poincaré-Steklov scheme
Original paper describing the method is
Acceleration to O(N) complexity is described
(to appear in SISC).
Coupling with a BIE for the external domain to solve free space scattering
Miscellaneous references (unsorted):
- A fast direct solver for a class of elliptic partial differential equations
(J. Sci. Comp., pp. 316-330, 38(3), 2009.)
The method described here is already somewhat outdated, but the paper is easy to read (relatively speaking...) and
should provide a good introduction to the general concepts.
- A Fast Block Low-Rank Dense Solver with Applications to Finite-Element Matrices
This recent manuscript contains a nice literature survey.
- Numerical homogenization via approximation of the solution operator
This paper focusses on model reduction, which is not the subject of this workshop.
However, Sections 1.2 and 1.3 are directly related to what we will do and might be useful.
(The model reduction idea is quite interesting, though, and you might find it fun to read this paper after the workshop!)
- A Fast Direct Solver for Elliptic Problems on General Meshes in 2D
This paper describes an O(N) fast direct solver for the linear systems arising from finite element / finite difference discretization
of elliptic PDEs in 2D. The numerical examples are very persuasive, and the illustrations are helpful. This paper is based on ideas
originally presented in:
Superfast Multifrontal Method For Large Structured Linear Systems Of Equations
This latter paper shows impressive numerical examples and is the foundation of much of the more recent work but is (I find) slightly harder to read.
An extension of these ideas to 3D is described here:
A fast direct solver for elliptic problems on Cartesian meshes in 3D
- An O(N) algorithm for constructing the solution operator to elliptic
boundary value problems in the absence of body loads
This paper shows that direct solvers can be particularly effective in situations where there is no body load present.
- Fast direct solvers for integral equations in complex three-dimensional domains
(Acta Numerica, 18, pp. 243-275, 2009.)
This paper describes direct solvers for integral equations. It provides a fairly detailed literature survey.
- A direct solver with O(N) complexity for integral equations on one-dimensional domains
This paper describes a direct solver that is simple and very fast for problems in 2D. (If you have difficulties reading the PDF
in the journal offprint, try this version instead.)
Finally, let us mention that many of the techniques covered are conceptually related to the so called H-matrix and H^2-matrix frameworks
of Hackbusch and co-workers. From a practical point of view, the H-matrix methods are implemented quite differently, but let us provide
links to two recent books that provide good introductions to this alternative set of methods:
Efficient Numerical Methods for Non-local Operators
H2-Matrix Compression, Algorithms and Analysis, by Steffen Borm.
Hierarchical Matrices, by Mario Bebendorf.
For an excellent introduction to spectral methods, please see Trefethen's
Research support by:
P.G. Martinsson, June 2014