Fast Tensor-Product Solvers for the Numerical Solution of Partial Differential Equations: Application to Deformed Geometries and to Space-Time Domains

Abstract

Spectral discretization in space and time of the weak formulation of a partial differential equations (PDE) is studied. The exact solution to the PDE, with either Dirichlet or Neumann boundary conditions imposed, is approximated using high order polynomials. This is known as a spectral Galerkin method. The main focus of this work is the solution algorithm for the arising algebraic system of equations. A direct fast tensor-product solver is presented for the Poisson problem in a rectangular domain. We also explore the possibility of using a similar method in deformed domains, where the geometry of the domain is approximated using high order polynomials. Furthermore, time-dependent PDE's are studied. For the linear convection-diffusion equation in $mathbb{R}$ we present a tensor-product solver allowing for parallel implementation, solving $mathcal{O}(N)$ independent systems of equations. Lastly, an iterative tensor-product solver is considered for a nonlinear time-dependent PDE. For most algorithms implemented, the computational cost is $mathcal O (N^{p+1})$ floating point operations and a memory required of $mathcal O (N^{p})$ floating point numbers for $mathcal O (N^{p})$ unknowns. In this work we only consider $p=2$, but the theory is easily extended to apply in higher dimensions. Numerical results verify the expected convergence for both the iterative method and the spectral discretization. Exponential convergence is obtained when the solution and domain geometry are infinitely smooth.