A Direct Solver with \textdollarO(N)\textdollar Complexity for Variable Coefficient Elliptic PDEs Discretized via a High-Order Composite Spectral Collocation Method
SIAM Journal on Scientific Computing, 36 (4):
A2023--A2046 (January 2014)DOI: 10.1137/130918988
Abstract
A numerical method for solving elliptic PDEs with variable co-
efficients on two-dimensional domains is presented. The method is based on
high-order composite spectral approximations and is designed for problems with
smooth solutions. The resulting system of linear equations is solved using a direct
(as opposed to iterative) solver that has optimal O(N) complexity for all stages of
the computation when applied to problems with non-oscillatory solutions such as
the Laplace and the Stokes equations. Numerical examples demonstrate that the
scheme is capable of computing solutions with relative accuracy of 10−10 or bet-
ter, even for challenging problems such as highly oscillatory Helmholtz problems
and convection-dominated convection diffusion equations. In terms of speed, it is
demonstrated that a problem with a non-oscillatory solution that was discretized
using 108 nodes was solved in 115 minutes on a personal work-station with two
quad-core 3.3GHz CPUs. Since the solver is direct, and the “solution operator”
fits in RAM, any solves beyond the first are very fast. In the example with 108