HPS Accelerated Spectral Solvers for Time Dependent Problems: Part I, Algorithms

A high-order convergent numerical method for solving linear and non-linear parabolic PDEs is presented. The time-stepping is done via an explicit, singly diagonally implicit Runge–Kutta (ESDIRK) method of order 4 or 5, and for the implicit solve, we use the recently developed “Hierarchial Poincare–Steklov (HPS)” method. The HPS method combines a multidomain spectral collocation discretization technique (a “patching method”) with a nested-dissection type direct solver. In the context under consideration, the elliptic solve required in each time-step involves the same coefficient matrix, which makes the use of a direct solver particularly effective. In this chapter is the first in a two part sequence; the first part describes the methodology, the second part presents numerical experiments.