Combined CG-HDG Method for Elliptic Problems: Performance Model

Martin Vymazal, David Moxey, Chris D. Cantwell, Spencer J. Sherwin, Robert M. KirbyarXiv 2018 · DOI · arXiv

Abstract

This paper investigates a hybrid "CG-HDG" method that attempts to combine the low memory footprint of Continuous Galerkin (CG) with the superior parallel scaling of Hybridizable Discontinuous Galerkin (HDG). Starting from a hybrid discontinuous formulation, the authors replace element interiors with "macro-elements"—groups of elements supporting a piecewise-polynomial continuous expansion. While this approach yields a novel weak formulation for Dirichlet boundary conditions, a rigorous performance model reveals that computational overhead in 3D makes it significantly more expensive than existing methods.

Introduction

In high-order finite element methods, researchers face a fundamental trade-off between Continuous Galerkin (CG) and Discontinuous Galerkin (DG/HDG) methods. CG is efficient due to shared degrees of freedom (DOFs) between elements, leading to fewer total unknowns. However, its global coupling creates complex communication patterns that hinder performance on massive parallel supercomputers. HDG decouples elements by introducing a "trace" variable on the mesh skeleton, allowing for excellent parallel scaling at the cost of more unknowns and higher local computational requirements.

Comparison of standard finite element discretizations: Continuous Galerkin (CG), Discontinuous Galerkin (DG), and Hybridizable Discontinuous Galerkin (HDG).

The authors propose a "macro-element" approach to bridge this gap, using CG internally for efficiency while linking patches via HDG-style weak coupling for scaling.

Methodology

The Combined CG-HDG method is built on several key components:

  1. Macro-Element Formulation: Treating a collection of elements as a single patch where the solution is piecewise-polynomial and continuous.
  2. Weak Coupling: Using a hybrid trace variable $\lambda$, similar to HDG, to connect these patches.
  3. Weak Dirichlet Boundary Conditions: A byproduct of this formulation is a new method for imposing Dirichlet BCs weakly within a CG framework using penalty terms, which preserves the symmetry of the discrete Laplacian.
  4. Performance Modeling: Complexity estimates based on Floating Point Operations (FLOPs) and memory movement were derived to compare CG, HDG, and CG-HDG across different element types.

Numerical Verification

The implementation was verified using a scalar Helmholtz problem on a 2D square domain ($[-1, 1]^2$) with a known exact solution $u(x, y) = \sin(10\pi x) \cos(10\pi y) + x + y$. Results showed that the weak Dirichlet BC formulation produces errors nearly identical to standard "strong" BCs up to polynomial order $p \approx 11$. Beyond this, conditioning issues with penalty terms in finite-precision arithmetic create an error floor.

Performance Insights and Results

Despite the mathematical elegance of the hybrid formulation, the performance model identified several critical bottlenecks:

  • The Surface-to-Volume Trap: In 3D, the number of degrees of freedom on the surface of a macro-element grows much faster than in 2D, diminishing the relative efficiency of the CG interior.
  • Scaling Discrepancy: The Preconditioned Conjugate Gradient (PCG) algorithm for CG-HDG scales as $O(N^4)$ relative to the number of elements along a patch face, compared to $O(N^3)$ for standard HDG.
  • Memory and CPU Costs: The interior solve for a macro-element involves a large sparse matrix whose inverse is dense. Storing and applying these dense inverses leads to massive memory overhead and higher CPU costs that outweigh the benefits of reduced global communication.

Conclusion

The hybrid CG-HDG method, while providing a valuable new tool for weak boundary conditions in CG, is "prohibitively expensive" for practical large-scale 3D use compared to pure CG or HDG. The complexity of solving macro-element interiors remains the primary hurdle. Future research may focus on optimized interior solvers or alternative partitioning strategies to realize the theoretical benefits of this hybrid approach.

Summary updated

Abstract

We combine continuous and discontinuous Galerkin methods in the setting of a model diffusion problem. Starting from a hybrid discontinuous formulation, we replace element interiors by more general subsets of the computational domain - groups of elements that support a piecewise-polynomial continuous expansion. This step allows us to identify a~new weak formulation of Dirichlet boundary condition in the continuous framework. We examine the expected performance of a Galerkin solver that would use continuous Galerkin method with weak Dirichlet boundary conditions in each mesh partition and connect partitions weakly using trace variable as in HDG method.
BibTeX
@misc{vymazal2018combined,
  author = {Martin Vymazal and David Moxey and Chris D. Cantwell and Spencer J. Sherwin and Robert M. Kirby},
  title = {{Combined CG-HDG Method for Elliptic Problems: Performance Model}},
  year = {2018},
  eprint = {1811.11855},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.11855},
}
Figure