%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 }