CBMS/NSF Conference on Fast Direct Solvers, June 2014
Dartmouth College, June 23 - 27, 2014
| Home | Lectures | Codes | Bibliography | Support |
| FMM | RSVD | ID | BIEs | FDS for sparse | FDS for IE | Poincaré-Steklov |
The Fast Multipole Method
Early descriptions of the FMM include a 1985 paper by Vladimir Rokhlin, and the seminal 1987 JCP paper by 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 dissertation of Leslie Greengard, a short course on FMMs by Rick Beatson and Leslie Greengard, a tutorial by Liu and Nishimura, and a variety of books, including this by Chew, Jin, Michielssen, and Son, and this by Yijun Liu.
Adaptivity is described in a 1988 SISC paper by Carrier, Greengard, and Rokhlin.
An essential improvement to the FMM that allows high speed for Laplace problems in 3D is described here.
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 here and here. For a more comprehensive description of these algorithms, see this.
An FMM based on the interpolative decomposition (ID) is described here.
A general collection of references on the FMM is to be found at fastmultipole.org.
Randomized methods for low-rank approximation
This survey provides an accessible introduction. It is 72 pages long, but the introduction (Section 1) can be read on its own and provides a brief introduction.
Another, briefer, introduction is given in this 2011 PNAS paper.
The original paper we published on these methods is this 2006 tech report. The report was (after two rejections...) eventually published here in ACHA.
For a full description of the intellectual pedigree of these methods, please see the survey mentioned earlier, and also this 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 survey.
A seminal 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 1987 paper by Tony Chan.
Applications to functions of a continuum variable are described here.
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!), and "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 here. 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 here. (Local copy.)
A brief introduction to methods for handling corners can be found here. (Local copy.) Original work in this area by James Bremer and Johan Helsing.
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 2009 paper. (Local copy.) This is pursued further in the dissertation of Adrianna Gillman. A journal publication on this work is here.
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 by 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 home page.
Related work by Philip Schmitz and Lexing Ying is here, and by Ken Ho and Lexing Ying here.
For a rough introduction to matrix algebra for rank-structured matrices, see this rough extract from the monograph manuscript.
Original references for H-matrix algebra include a 1999 paper in Computing by Wolfgang Hackbusch. The H2-matrix arithmetic was introduced to reduce complexity from O(N (log N)k) to O(N) and is described in this 2000 paper by W. Hackbusch, B. Khoromskij, and S. A. Sauter. A 2008 book by Mario Bebendorf provides a full reference to H-matrix techniques, and a 2010 book by Steffen Börm describes H2-matrix methods.
Resources on H-matrices, including codes and an extensive bibliography, can be found at hlib.org.
So called hierarchically off-diagonal low-rank (HODLR) matrices are used in this 2014 manuscript by A. Aminfar, S. Ambikasaran, and E. Darve. This manuscript also contains a very informative literature survey.
Direct solvers for integral equations
The original paper describing "hierarchical skeletonization" is this 2005 paper, which in turn builds off of a single-level scheme described here. This survey article 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 2012 paper (local copy). A variation of the same scheme, which uses a general purpose sparse structured solver (UMFPACK) by Greengard and Ho can be found here. A variation that appears to attain O(N) complexity by Ho and Ying can be found here.
An extension to 3D based on hierarchical merging of scattering matrices can be found here (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 Hierarchical Matrices, 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 here (local copy).
Acceleration to O(N) complexity is described here (to appear in SISC).
Coupling with a BIE for the external domain to solve free space scattering here (local copy).
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 book.
Research support by:
P.G. Martinsson, June 2014