Date of Award

Spring 1-1-2019

Document Type


Degree Name

Doctor of Philosophy (PhD)

First Advisor

Per-Gunnar Martinsson

Second Advisor

Daniel Appelo

Third Advisor

Adrianna Gillman

Fourth Advisor

Bengt Fornberg

Fifth Advisor

Gregory Beylkin


The dissertation concerns numerical methods for approximately solving certain linear partial differential equations. The foundation is a solution methodology for linear elliptic boundary value problems that we call the ``Hierarchical Poincare-Steklov (HPS)'' method. This method is based on a high-order multidomain spectral discretization that is designed to work particularly well in conjunction with nested-dissection type direct solvers. The methods presented apply in any dimension, but their efficiency deteriorates as the dimension increases, and dimensions higher than three are generally not considered.

A key competitive advantage of the HPS method is that the linear system that results from discretizing an elliptic PDE is solved using a direct rather than an iterative solver. This solver is closely related to existing nested dissection and multifrontal solvers, and has a similar computational profile that involves a ``build stage'' that is reasonably efficient, and then a ``solve stage'' that is very fast. This makes the method particularly powerful for use in situations where a sequence of linear problems involving the same operator needs to be solved, as happens for instance when solving certain parabolic and hyperbolic PDEs. The use of a direct solver also enables the method to solve many problems that are intractable to iterative solvers, such as Helmholtz problems at intermediate and high frequencies.

The HPS methodology was originally published as a solution method for homogeneous elliptic problems, and the core contributions of the dissertation involve the extension of the methodology to more general environments. Specifically, there are four key contributions:

1. An extension of the method to handle non homogeneous elliptic equations that involve forcing terms in the volume of the domain.

2. A generalization of the method to allow the use of refined meshes in order to resolve local singularities.

3. An efficient solver for hyperbolic equations that works by applying the HPS methodology to explicitly build highly accurate approximations to the time evolution operator. This enables the use of very long time steps, and parallel in time implementations.

4. An efficient solver for parabolic problems, where the main idea is to accelerate implicit time-stepping schemes by using the HPS methodology to pre-compute the solution operator involved in the elliptic solve. This work also includes an extension to certain non-linear problems.

All techniques presented are analyzed in terms of their complexity. Accuracy and stability are demonstrated via extensive numerical examples.