A Direct Solver with \textdollarO(N)\textdollar Complexity for Variable Coefficient Elliptic PDEs Discretized via a High-Order Composite Spectral Collocation Method
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
Society for Industrial & Applied Mathematics (SIAM)
volume
36
file
:Article/Gillman2014 - A Direct Solver with O(N) Complexity for Variable Coefficient Elliptic PDEs Discretized Via a High Order Composite Spectral Collocation Method.pdf:PDF
%0 Journal Article
%1 Gillman2014
%A Gillman, A.
%A Martinsson, P. G.
%D 2014
%I Society for Industrial & Applied Mathematics (SIAM)
%J SIAM Journal on Scientific Computing
%K imported
%N 4
%P A2023--A2046
%R 10.1137/130918988
%T A Direct Solver with \textdollarO(N)\textdollar Complexity for Variable Coefficient Elliptic PDEs Discretized via a High-Order Composite Spectral Collocation Method
%V 36
%X 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
@article{Gillman2014,
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},
added-at = {2018-12-03T19:42:16.000+0100},
author = {Gillman, A. and Martinsson, P. G.},
biburl = {https://www.bibsonomy.org/bibtex/2d268ea35e3643ae22ef51de0318b5cb5/tobydriscoll},
doi = {10.1137/130918988},
file = {:Article/Gillman2014 - A Direct Solver with O(N) Complexity for Variable Coefficient Elliptic PDEs Discretized Via a High Order Composite Spectral Collocation Method.pdf:PDF},
interhash = {0f15d566309b741b173a10d8b5d4da71},
intrahash = {d268ea35e3643ae22ef51de0318b5cb5},
journal = {{SIAM} Journal on Scientific Computing},
keywords = {imported},
month = jan,
number = 4,
pages = {A2023--A2046},
publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
timestamp = {2018-12-03T19:43:16.000+0100},
title = {A Direct Solver with {\textdollar}O(N){\textdollar} Complexity for Variable Coefficient Elliptic {PDEs} Discretized via a High-Order Composite Spectral Collocation Method},
volume = 36,
year = 2014
}