Fast Algorithms and PDE Libraries
An active area of research in our group is the development
of fast and adaptive algorithms for computational problems in
electromagnetics, materials science, device physics and chemistry.
At the core of many simulations in these areas are solvers for the
Poisson, Helmholtz, and time-harmonic Maxwell equations,
time-domain wave propagation, and the diffusion equation.
While standard numerical methods typically rely on finite difference or
finite element discretization of the governing partial differential
equation, we concentrate on integral equation-based methods.
These have a number of advantages - they are geometrically flexible,
easy to use, compatible with
embedded boundary discretizations
,
and lead to well-conditioned linear systems. They do, however, require
some knowledge of the underlying Green's function and
a variety of fast algorithms in order to be practical.
Fast Multipole Methods
The simplest example of an "integral-equation" based fast
solver is, perhaps, the recasting of the Poisson equation
with a right-hand side consisting of a set N point sources
(delta functions) located at
{P
n} with strengths {ρ
n} in terms of the
solution expressed as a sum:
.
For the Helmholtz equation (with frequency k) and the same right-hand side,
the solution is expressed as
.
The advantages of this approach are clear. No linear system needs to be solved,
artificial radiation conditions are not needed on a finite
computational domain, and the answer is exact. However, a fast algorithm
is required for the approach to be practical for large scale problems.
Clearly, O(N
2) work is required to evaluate the solution at
N locations. In the last few decades, a wide variety of schemes have become
available that reduce the work load to O(N) or O(N log N). Our group
has concentrated on fast multipole methods (FMMs), beginning with the
two-dimensional, non-adaptive version in two dimensions:
- L. Greengard and V. Rokhlin,
A Fast Algorithm for Particle Simulations ,
J. Comput. Phys. 73, 325-348 (1987).
The speed-up provided by the fully adaptive three-dimensional,
scheme
- H. Cheng, L. Greengard and V. Rokhlin,
A Fast Adaptive Multipole Algorithm in Three Dimensions ,
J. Comput. Phys. 155, 468-498 (1999).
is shown in the following table, where
Lev is the number of
refinement levels,
p is the order of multipole expansion used,
TFMM denotes the FMM time
(in seconds on a single processor) and
TDIR denotes the time (in seconds) for direct evaluation.
.
For recent technical references on extensions to Stokes, Helmholtz
and screened Coulomb interactions, see:
- Z. Gimbutas and L. Greengard,
Fast Multi-Particle Scattering: a Hybrid Solver for the
Maxwell Equations in Microstructured Materials,
J. Comput. Phys., 232 , 22-32 (2013).
- A.-K. Tornberg and L. Greengard,
A Fast Multipole Method for the Three Dimensional Stokes Equations,
J. Comput. Phys. 227, 1613-1619 (2008).
- H. Cheng, W. Y. Crutchfield, Z. Gimbutas, L. Greengard,
F. Ethridge, J. Huang, V. Rokhlin, N. Yarvin, and J. Zhao,
A Wideband Fast Multipole Method for the Helmholtz Equation
in Three Dimensions,
J. Comput. Phys. 216, 300-325 (2006).
- L. Greengard and J. Huang,
A New Version of the Fast Multipole Method for
Screened Coulomb Interactions in Three Dimensions,
J. Comput. Phys. 180, 642-658 (2002).
A suite of open-source codes is available for release from the
Software tab.
A number of other useful documents/software packages can be obtained from
Fast Multipole.org.
FMM and related algorithms are not limited to particle interactions.
They are used in accelerating integral-equation based solvers for many
of the partial differential equations of classical physics.