Quasi-optimal complexity $hp$-FEM for Poisson on a rectangle
<|reference_start|>Quasi-optimal complexity $hp$-FEM for Poisson on a rectangle: 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 \emph{reverse Cholesky factorisation} -- Cholesky starting from the bottom right instead of the top left -- remains sparse. Moreover, computing and inverting the factorisation almost entirely trivially parallelises across the different elements. By incorporating this approach into an Alternating Direction Implicit (ADI) method \`a la Fortunato and Townsend (2020) we can solve, within a prescribed tolerance, an $hp$-FEM discretisation of the (screened) Poisson equation on a rectangle, in parallel, 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.<|reference_end|>
@article{knook2024quasi-optimal,
    title={Quasi-optimal complexity $hp$-FEM for Poisson on a rectangle},
    author={Kars Knook and Sheehan Olver and Ioannis P. A. Papadopoulos},
    journal={arXiv preprint arXiv:2402.11299},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.11299},
    primaryClass={math.NA cs.NA}
}