A Fast Adaptive Solver for Linear Differential Equations Based on Potential Theory

Jingfang Huang
Courant Institute of Mathematical Sciences
251 Mercer Street
New York, NY 10012
Email : huangjf@cims.nyu.edu

Abstract
We present a new class of fast solvers for ordinary and partial differential equations using finite difference discretizations with adaptive mesh refinement. The method is a combination of fast solvers for uniform grids, potential theory, and multilevel sweeps to evaluate layer potentials. In brief, we solve uncoupled problems on uniform data structures and then use layer potentials to patch together solutions at coarse/fine interfaces. Unlike hierarchical iterations, such as multigrid and domain decomposition, the method we propose is direct. For strongly elliptic problems, where the norm of the Green's function ||G|| is small, one "N"-Cycle gives the optimal result obtainable for a given finite difference discretization. An "N"-Cycle consists of one downward sweep, from the coarsest to the finest mesh, using boundary conditions inherited from the parent, one upward sweep to compute the jumps at all coarse/fine interfaces, and a second downward sweep to propagate the layer potential correction to all subgrids. Our method preserves the order of accuracy of the underlying difference scheme without the need for complex stencils at grid boundaries. We illustrate the performance of the method with numerical examples arising in stiff and nonstiff two-point boundary value problems, parabolic equations in one space dimension, and elliptic partial differential equations in two space dimensions. Generalizations and limitations of the method are also addressed.