WIAS Preprint No. 3229, (2025)

Quasi--optimal complexity hp--FEM for the Poisson equation on a rectangle


Authors

  • Knook, Kars
  • Olver, Sheehan
  • Papadopoulos, Ioannis
    ORCID: 0000-0003-3522-8761

2020 Mathematics Subject Classification

  • 35J05 65M60 65Y20

Keywords

  • Quasi-optimal complexity, Poisson equation, hp-finite element method, alternating direction implicit algorithm

DOI

10.20347/WIAS.PREPRINT.3229

Abstract

We show, in one dimension, that an hp-Finite Element Method (hp-FEM) discretisation can be solved in optimal complexity because the discretisation has a special sparsity structure that ensures that the reverse Cholesky factorisation---Cholesky starting from the bottom right instead of the top left---remains sparse. Moreover, computing and inverting the factorisation may parallelise across different elements. By incorporating this approach into an Alternating Direction Implicit (ADI) method à la Fortunato and Townsend (2020) we can solve, within a prescribed tolerance, an hp-FEM discretisation of the (screened) Poisson equation on a rectangle with quasi-optimal complexity: O(N^2 log N) operations where N is the maximal total degrees of freedom in each dimension. When combined with fast Legendre transforms we can also solve nonlinear time-evolution partial differential equations in a quasi-optimal complexity of O(N^2 log^2 N) operations, which we demonstrate on the (viscid) Burgers' equation. We also demonstrate how the solver can be used as an effective preconditioner for PDEs with variable coefficients, including coefficients that support a singularity.

Appeared in

Download Documents