Numerical Methods for Solving Linear Elliptic PDEs: Direct Solvers and High Order Accurate Discretizations

Sijia Hao, University of Colorado Boulder


This dissertation describes fast and highly accurate techniques for solving linear elliptic boundary value problems associated with elliptic partial differential equations such as Laplace's, Helmholtz equations and time-harmonic Maxwell's equation. It is necessary to develop efficient methods to solve these problems numerically.

The techniques we develop in this dissertation are applicable to most linear elliptic PDEs, especially to the Helmholtz equation. This equation models frequency domain wave-propagation, and has proven to be particularly difficult to solve using existing methodology, in particular in situations where the computational domain extends over dozens or hundreds of wave-lengths. One of the difficulties is that the linear systems arising upon discretization are ill-conditioned that have proven difficult to solve using iterative solvers. The other is that errors are aggregated over each wave-length such that a large number of discretization nodes are required to achieve certain accuracy. The objective of this dissertation is to overcome these difficulties by exploring three sets of ideas: 1) high order discretization, 2) direct solvers and 3) local mesh refinements.

In terms of "high-order" discretization, the solutions to the PDEs are approximated by high-order polynomials. We typically use local Legendre or Chebyshev grids capable of resolving polynomials up to degree between 10 and 40. For solving the linear system formed upon high-order discretization, there exist a broad range of schemes. Most schemes are "iterative" methods such as multigrid and preconditioned Krylov methods. In contrast, we in this thesis mainly focus on ``direct" solvers in the sense that they construct an approximation to the inverse of the coefficient matrix. Such techniques tend to be more robust, versatile and stable compared to the iterative techniques. Finally, local mesh refinement techniques are developed to effectively deal with sharp gradients, localized singularities and regions of poor resolution. A variety of two-dimensional and three-dimensional problems are solved using the three techniques described above.