Vol. 6, No. 1, 2011

Download this article
Download this article For screen
For printing
Recent Issues
Volume 12, Issue 1
Volume 11, Issue 2
Volume 11, Issue 1
Volume 10, Issue 2
Volume 10, Issue 1
Volume 9, Issue 2
Volume 9, Issue 1
Volume 8, Issue 1
Volume 7, Issue 2
Volume 7, Issue 1
Volume 6, Issue 1
Volume 5, Issue 2
Volume 5, Issue 1
Volume 4, Issue 1
Volume 3, Issue 1
Volume 2, Issue 1
Volume 1, Issue 1
The Journal
Cover
About the Cover
Editorial Board
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Subscriptions
Editorial Login
Contacts
Author Index
To Appear
 
ISSN: 2157-5452 (e-only)
ISSN: 1559-3940 (print)
A free-space adaptive {FMM}-Based {PDE} solver in three dimensions

M. Harper Langston, Leslie Greengard and Denis Zorin

Vol. 6 (2011), No. 1, 79–122
Abstract

We present a kernel-independent, adaptive fast multipole method (FMM) of arbitrary order accuracy for solving elliptic PDEs in three dimensions with radiation and periodic boundary conditions. The algorithm requires only the ability to evaluate the Green’s function for the governing equation and a representation of the source distribution (the right-hand side) that can be evaluated at arbitrary points. The performance is accelerated in three ways. First, we construct a piecewise polynomial approximation of the right-hand side and compute far-field expansions in the FMM from the coefficients of this approximation. Second, we precompute tables of quadratures to handle the near-field interactions on adaptive octree data structures, keeping the total storage requirements in check through the exploitation of symmetries. Third, we employ shared-memory parallelization methods and load-balancing techniques to accelerate the major algorithmic loops of the FMM. We present numerical examples for the Laplace, modified Helmholtz and Stokes equations.

Keywords
volume integrals, Poisson solver, fast multipole method, adaptive methods, kernel-independent fast multipole method
Mathematical Subject Classification 2010
Primary: 31B10, 65N99, 65R10, 65Y20
Secondary: 65N15, 76D07
Milestones
Received: 1 April 2011
Revised: 20 July 2011
Accepted: 22 July 2011
Published: 28 August 2011
Authors
M. Harper Langston
Courant Institute
New York University
251 Mercer Street
New York 10012
United States
http://cs.nyu.edu/~harper/
Leslie Greengard
Courant Institute
New York University
251 Mercer Street
New York NY 10012
United States
http://math.nyu.edu/faculty/greengar/
Denis Zorin
Courant Institute
New York University
251 Mercer Street
New York 10012
United States
http://mrl.nyu.edu/~dzorin/