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²) 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, T_FMM denotes the FMM time (in seconds on a single processor) and T_DIR 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.