PaperlayerView exact revision on arXiv

Source-linked AI summary

The Compact Discontinuous Galerkin (CDG) Method for Elliptic Problems

Jaume Peraire, Per-Olof Persson

arXiv:math/0702353v3math.NA

TL;DR

Elliptic DG discretizations need compact connectivity without sacrificing the flexibility and stability associated with DG and LDG methods. The paper introduces CDG, whose flux design permits element-level elimination of the auxiliary flux and nearest-neighbor global coupling. CDG therefore uses fewer matrix nonzeros and lower storage than the compared alternatives, while remaining effective without stabilization in relevant orientations.

  • Problem

    Multidimensional LDG discretizations create connections to nonneighboring elements, increasing connectivity when compact implicit systems are needed.

  • Method

    CDG applies DG to a first-order elliptic system and chooses numerical fluxes so the auxiliary flux can be eliminated elementwise, leaving a primal global system.

  • Results

    CDG produces a sparser matrix than LDG and fewer nonzero elements than BR2 or IP, with lower storage requirements and higher computational performance.

  • Takeaways & Limitations

    CDG connects only neighboring elements and its added numerical-flux complexity is offset by increased compactness and computational efficiency.

  • Takeaways & Limitations

    The error estimates require C11 = O(h^-1); with C11 = O(1), only suboptimal convergence is demonstrated, and p = 0 is generally inconsistent.

Abstract

from arXiv · show

We present a compact discontinuous Galerkin (CDG) method for an elliptic model problem. The problem is first cast as a system of first order equations by introducing the gradient of the primal unknown, or flux, as an additional variable. A standard discontinuous Galerkin (DG) method is then applied to the resulting system of equations. The numerical interelement fluxes are such that the equations for the additional variable can be eliminated at the element level, thus resulting in a global system that involves only the original unknown variable. The proposed method is closely related to the local discontinuous Galerkin (LDG) method [B. Cockburn and C.-W. Shu, SIAM J. Numer. Anal., 35 (1998), pp. 2440-2463], but, unlike the LDG method, the sparsity pattern of the CDG method involves only nearest neighbors. Also, unlike the LDG method, the CDG method works without stabilization for an arbitrary orientation of the element interfaces. The computation of the numerical interface fluxes for the CDG method is slightly more involved than for the LDG method, but this additional complication is clearly offset by increased compactness and flexibility. Compared to the BR2 [F. Bassi and S. Rebay, J. Comput. Phys., 131 (1997), pp. 267-279] and IP [J. Douglas, Jr., and T. Dupont, in Computing Methods in Applied Sciences (Second Internat. Sympos., Versailles, 1975), Lecture Notes in Phys. 58, Springer, Berlin, 1976, pp. 207-216] methods, which are known to be compact, the present method produces fewer nonzero elements in the matrix and is computationally more efficient.

1 Introduction

The paper develops CDG for elliptic problems to retain DG flexibility while avoiding LDG’s nonlocal multidimensional connectivity. CDG is presented as compact and more efficient than established compact alternatives.

  • DG motivation: DG methods support stable convection discretizations, arbitrary meshes, and straightforward elementwise approximation orders, but duplicate interface degrees of freedom.The duplication is especially problematic for low-order polynomial approximations.
  • Existing elliptic schemes: Elliptic problems require extensions of DG methods, with LDG, IP, and BR2 among the principal alternatives.LDG is described as a popular choice, while IP and BR2 discretize the second-order form directly with explicit stabilization.
  • CDG contribution: CDG modifies LDG to eliminate distant connections between nonneighboring elements in multidimensional discretizations.CDG and LDG are identical in one dimension but differ in their multidimensional interface gradient approximation.
  • CDG contribution: Numerical experiments indicate that CDG is slightly more stable than LDG and less sensitive to element or interface orientation.With zero stabilization, CDG remains stable in situations where LDG is unstable.
  • Reported advantages: CDG produces a sparser matrix than LDG and is computationally simpler and sparser than IP or BR2 in the reported comparisons.The paper reports lower storage requirements, higher computational performance, and slightly greater accuracy than BR2 in its numerical tests.

2 Discontinuous Galerkin formulation

The formulation rewrites the elliptic problem as a first-order DG system with primal and flux variables, then derives LDG fluxes and a primal form exposing symmetry and noncompactness.

  • 2.1 Problem definition: The model problem is Poisson-type diffusion, with a positive coefficient on a bounded domain whose boundary has Dirichlet and Neumann parts.The dimension is restricted to d = 1, 2, or 3, and the Dirichlet boundary has nonzero length.
  • 2.2 DG Formulation for elliptic problems: The DG formulation rewrites the second-order problem as a first-order system by introducing the flux σ = κ∇u alongside the primal variable.Elementwise equations use numerical approximations to the flux and primal variable on element boundaries.
  • 2.2 DG Formulation for elliptic problems: Broken spaces and finite-element subspaces are defined elementwise, using polynomial functions of degree at most p ≥1.Broken gradients and divergences are applied separately on each element.
  • 2.2 DG Formulation for elliptic problems: Interior-face averages, jumps, and outward normals provide the notation for assembling conservative global DG expressions from element equations.Scalar jumps are vectors, whereas vector jumps are scalars under the stated definitions.
  • 2.3 The LDG method: LDG specifies numerical interelement and boundary fluxes through a positive constant C11, a facewise vector C12, and switches satisfying a stated constraint.The switches are otherwise arbitrary, but their choice affects the final discrete equations; more general C12 choices produce wider stencils.
  • 2.3.1 Primal form of the LDG algorithm: The LDG flux equations are reduced to a primal form by introducing lifting operators that express σh in terms of uh and boundary data.The flux equals the broken gradient contribution plus perturbations driven by jumps, C12, and the Dirichlet boundary mismatch.
  • 2.3.1 Primal form of the LDG algorithm: The primal LDG bilinear form is symmetric, while the conservative fluxes guarantee conservation and adjoint consistency.The form includes products of lifting-function contributions.
  • 2.3.1 Primal form of the LDG algorithm: In multidimensional general meshes, LDG is noncompact because lifting-function volume terms connect degrees of freedom beyond immediate neighboring elements.Changing face switches cannot remove these additional connections, and the issue also occurs on quadrilateral and hexahedral meshes.

3 The CDG algorithm

The CDG method localizes LDG lifting contributions facewise, eliminating nonneighboring-element connections while retaining symmetry, consistency, adjoint consistency, and optimal a priori estimates. Its numerical flux evaluation is more involved but produces a sparser matrix than related compact schemes.

  • 3 The CDG algorithm: The CDG method decomposes LDG lifting operators into facewise contributions to eliminate connectivities between nonneighboring elements.The localized face-associated lifting functions are the key design choice behind compactness.
  • 3 The CDG algorithm: CDG numerical fluxes differ from LDG only in evaluating terms involving the numerical flux σ̂, while the numerical flux û is chosen as in LDG.The CDG flux evaluation uses the definitions associated with the facewise construction.
  • 3.1 Primal form of the CDG algorithm: The CDG scheme is symmetric and retains LDG's consistency and adjoint consistency.
  • 3.1 Primal form of the CDG algorithm: CDG can be viewed as LDG with some indefinite stabilizing terms turned off, which removes nonneighboring-element connectivities.The facewise lifting functions are responsible for this localization.
  • 3.2 Error estimates: CDG inherits the LDG coercivity and boundedness proofs, yielding optimal a priori estimates under the stated stabilization scaling.The estimates require C11 to be of order O(h^-1); with C11 of order O(1), only suboptimal convergence is demonstrated.
  • 3.2 Error estimates: The stabilization parameter C11 must be of order O(h^-1) for the stated a priori estimates, while p = 0 is inconsistent for general discretizations.Optimal results are nevertheless observed in practical computations with C11 of order O(1).

4 Stabilization

The stabilization analysis distinguishes LDG's switch-dependent stability from CDG's greater flexibility. CDG permits zero stabilization on internal faces with arbitrary switch combinations satisfying its stated constraint, while LDG requires a specific switch rule for the same simplification.

  • 4 Stabilization: LDG can set C11 = 0 on internal interfaces without performance degradation when its switches satisfy rule (42).Under this rule, the scheme converges at the optimal rate without explicit stabilization.
  • 4 Stabilization: CDG does not require LDG's switch rule for uniqueness and permits C11 = 0 on internal faces with any switch combination satisfying constraint (17).
  • 4.1 Null-space dimension: In the periodic test, LDG with the consistent switch has the expected one-dimensional null-space, whereas its natural switch produces a null-space growing with p.The natural switch is based on element numbering, while the consistent switch satisfies rule (42).
  • 4.1 Null-space dimension: The natural switch has computational advantages for ILU(0) factorization because it avoids additional fill-in in the lower triangular blocks.Arbitrary switch choices can make some lower triangular blocks completely full after factorization.

5 Implementation

The implementation compares CDG, LDG, and BR2 sparsity and storage, showing that CDG retains nearest-neighbor connectivity while reducing nonzeros and memory requirements.

  • Sparsity patterns: CDG produces the smallest number of nonzero matrix entries because it connects only switched face nodes to neighboring-element interior nodes.
  • Sparsity patterns: The four-triangle p = 3 example shows CDG and BR2 connect neighboring triangles, whereas LDG also connects nonneighboring triangles 3 and 4.
  • Sparsity patterns: LDG adds nonlocal connections involving nonneighboring face nodes; the assumed average number of such neighbors is α = 0, 1, and 2 in one, two, and three dimensions.
  • Sparsity patterns: BR2 and IP add connections from all face nodes to all neighboring-element interior nodes, creating denser off-diagonal blocks than CDG.
  • Storage requirements: CDG has the lowest memory requirements; in three dimensions with p = 4, LDG and BR2 require 14% and 36% additional storage, respectively.
  • Storage requirements: CDG matrices can be stored with dense diagonal and rectangular off-diagonal block arrays, unlike the more complex LDG and BR2 storage patterns.

6 Numerical results

Numerical experiments on a two-dimensional Poisson problem assess CDG accuracy, stabilization, convergence, and comparisons with LDG and BR2. CDG achieves optimal convergence, remains weakly dependent on stabilization, and is generally the most accurate among the tested schemes.

  • Experimental setup: The experiments use triangular meshes from n×n Cartesian grids, with h = 1/n, and nodal polynomial bases of degrees p = 1 through p = 5.The meshes use n = 2, 4, 8, 16, 32, producing 2n^2 triangles.
  • Stabilization study: The computed L2 error is evaluated for multiple mesh sizes, polynomial degrees, stabilization values, and both consistent and natural switches.The stabilization values tested are C11 = 0, 1, and 10.
  • Stabilization study: Accuracy depends only weakly on C11, except for underresolved p = 1, 2 cases on the coarsest mesh with C11 = 10.With the natural switch, errors are on average 11% larger and at most 42% larger than with the consistent switch.
  • Convergence: The CDG solution converges optimally at rate p+1, while its gradient converges at the expected optimal rate p.The gradient results use the consistent switch with C11 = 0.
  • Comparison with LDG and BR2: CDG is the most accurate scheme in most test cases, often exceeding LDG and BR2 by more than a factor of 2 for low p and coarse meshes.For well-resolved solutions CDG and LDG are similar, while BR2 is about 10% less accurate; all schemes converge near p + 1 in L2 error.
  • Spectral radius: CDG and LDG have nearly identical scaled spectral radii, whereas BR2 produces values about 50% larger.The spectral radii are scaled by (h/p)^2; reducing BR2’s lifting parameter may lower the radius but may compromise stability.

7 Conclusions

The CDG method is proposed as a compact DG scheme for elliptic operators. It connects only neighboring elements, reduces matrix nonzeros relative to compact alternatives, and retains optimal convergence with competitive accuracy.

  • Compactness: CDG connects only degrees of freedom in neighboring elements, unlike LDG’s nonneighboring connections in multidimensional settings.Its reduced sparsity is important for implicit solution techniques.
  • Efficiency: Compared with BR2 and IP, CDG has fewer off-diagonal nonzeros, and its nonzero entries support dense block matrix storage.The conclusion also describes CDG as computationally simpler than BR2 and IP.
  • Accuracy and flexibility: CDG converges optimally, and numerical tests show accuracy comparable to LDG or BR2.The method may also be insensitive to face ordering when used with minimal interior dissipation.
Loading math/0702353v3…