A direct solver for elliptic PDEs in three dimensions based on hierarchical merging of Poincare-Steklov operators

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:308

Article

Hao, Sijia¹  Martinsson, Per-Gunnar¹ 

[1] Univ Colorado, Dept Appl Math, 526 UCB, Boulder, CO 80309 USA

关键词: Muitidomain spectral method;    High order discretization;    Direct solver;    Nested dissection;    Multifrontal solver;    Structured matrix algebra;   

DOI  :  10.1016/j.cam.2016.05.013

来源: Elsevier

【 摘 要 】

A numerical method for variable coefficient elliptic PDEs on three dimensional domains is, described. The method is designed for problems with smooth solutions, and is based on a multidomain spectral collocation discretization scheme. The resulting system of linear equations can very efficiently be solved using a nested dissection style direct (as opposed to iterative) solver. This makes the scheme particularly well suited to solving problems for which iterative solvers struggle; in particular for problems with oscillatory solutions. A principal feature of the scheme is that once the solution operator has been constructed, the actual solve is extremely fast. An upper bound on the asymptotic cost of the build stage of O(N-4/3) is proved (for the case where the PDE is held fixed as N increases). The solve stage has close to linear complexity. The scheme requires a relatively large amount of storage per degree of freedom, but since it is a high order scheme, a small number of degrees of freedom is sufficient to achieve high accuracy. The method is presented for the case where there is no body load present, but it can with little difficulty be generalized to the non-homogeneous case. Numerical experiments demonstrate that the scheme is capable of solving Helmholtz type equations on a domain of size 20 x 20 x 20 wavelengths to three correct digits on a modest personal workstation, with N approximate to 2.10(6). (C) 2016 Elsevier B.V. All rights reserved.

【 授权许可】

Free