Factorizing the factorization - a spectral-element solver for elliptic equations with linear operation count

Abstract

High-order methods gain more and more attention in computational fluid dynamics. However, the potential advantage of these methods depends critically on the availability of efficient elliptic solvers. With spectral-element methods, static condensation is a common approach to reduce the number of degree of freedoms and to improve the condition of the algebraic equations. The resulting system is block-structured and the face-based operator well suited for matrix-matrix multiplications. However, a straight-forward implementation scales super-linearly with the number of unknowns and, therefore, prohibits the application to high polynomial degrees. This paper proposes a novel factorization technique, which yields a linear operation count of just 13N multiplications, where N is the total number of unknowns. In comparison to previous work it saves a factor larger than 3 and clearly outpaces unfactored variants for all polynomial degrees. Using the new technique as a building block for a preconditioned conjugate gradient method resulted in a runtime scaling linearly with N for polynomial degrees $2\le p\le 32$ . Moreover the solver proved remarkably robust for aspect ratios up to 128.

References in corpus (1)

• An Immersed Boundary Method with Direct Forcing for the Simulation of Particulate Flows

Cited by in corpus (8)

• Fast matrix-free evaluation of discontinuous Galerkin finite element operators
• Robust multigrid for high-order discontinuous Galerkin methods: A fast Poisson solver suitable for high-aspect ratio Cartesian grids
• Scaling to the stars -- a linearly scaling elliptic solver for $p$-multigrid
• From Domain-Specific Languages to Memory-Optimized Accelerators for Fluid Dynamics
• Double-grid quadrature with interpolation-projection (DoGIP) as a novel discretisation approach: An application to FEM on simplexes
• Automatic Creation of High-Bandwidth Memory Architectures from Domain-Specific Languages: The Case of Computational Fluid Dynamics
• A Hermite-like basis for faster matrix-free evaluation of interior penalty discontinuous Galerkin operators
• Linearizing the hybridizable discontinuous Galerkin method: A linearly scaling operator