This page was generated from unit-2.8-DG/DG.ipynb.

2.8 Discontinuous Galerkin Methods

  • Use discontinuous finite element spaces to solve PDEs.

  • Allows upwind-stabilization for convection-dominated problems

  • Requires additional jump terms for consistency

Interior penalty DG form for \(-\Delta u\):

\[\DeclareMathOperator{\Div}{div} A(u,v) = \sum_T \int_T \nabla u \nabla v - \sum_F \int_F \{ n \nabla u \} [v] - \sum_F \int_F \{ n \nabla v \} [u] + \frac{\alpha p^2}{h} \sum_F \int_F [u][v]\]

with the jump over facets

\[[u] = u_{left} - u_{right}\]

and the averaging operator

\[\{ n \nabla u \} = \tfrac{1}{2} (n_{left} \nabla u_{left} + n_{left} \nabla u_{right})\]

DG form for \(\Div (b u)\), where \(b\) is the given wind:

\[B(u,v) = -\sum_T \int_T b u \nabla v + \sum_F \int_F b\cdot n u^{upwind} [v]\]
[1]:
from ngsolve import *
from ngsolve.webgui import Draw
mesh = Mesh(unit_square.GenerateMesh(maxh=0.3))

The space is responsible for allocating the matrix graph. We tell it to reserve entries for the coupling terms across facets:

[2]:
order=4
fes = L2(mesh, order=order, dgjumps=True)
u,v = fes.TnT()

Every facet has a master element. The value from the other element is referred to via the Other() operator:

[3]:
jump_u = u-u.Other()
jump_v = v-v.Other()
n = specialcf.normal(mesh.dim)
mean_dudn = 0.5*n * (grad(u)+grad(u.Other()))
mean_dvdn = 0.5*n * (grad(v)+grad(v.Other()))

Integrals on facets are computed by setting skeleton=True.

  • dx(skeleton=True) iterates over all internal facets

  • ds(skeleton=True) iterates over all boundary facets

On the boundary facets we get Nitsche’s method for the Dirichlet boundary condition \(u = 0\):

[4]:
alpha = 4
h = specialcf.mesh_size
diffusion = grad(u)*grad(v) * dx \
    +alpha*order**2/h*jump_u*jump_v * dx(skeleton=True) \
    +(-mean_dudn*jump_v-mean_dvdn*jump_u) * dx(skeleton=True) \
    +alpha*order**2/h*u*v * ds(skeleton=True) \
    +(-n*grad(u)*v-n*grad(v)*u)* ds(skeleton=True)

All unknowns of the \(L_2\) space are element-local, but here they are coupled via the facet integrals. Static condensation is not possible, and we tell Solve not to try it:

[5]:
gfu = Solve(diffusion == 1*v*dx, condense=False)
Draw (gfu);

DG requires a lot of additional matrix entries:

[6]:
a = BilinearForm(diffusion).Assemble()

fes2 = L2(mesh, order=order)
ul2,vl2 = fes2.TnT()
a2 = BilinearForm(ul2*vl2*dx).Assemble()
print ("DG-matrix nze:", a.mat.nze)
print ("L2-matrix nze:", a2.mat.nze)
DG-matrix nze: 18900
L2-matrix nze: 5400

Next we solve a convection-diffusion problem.

The IfPos function checks whether the first argument is positive. Then it returns the second one, else the third one. This is used to define the upwind flux. The check is performed in every integration point on the skeleton:

[7]:
b = CF( (20,5) )
uup = IfPos(b*n, u, u.Other())

convection = -b * u * grad(v)*dx + b*n*uup*jump_v * dx(skeleton=True)

The system matrix is not symmetric anymore, the sparse direct solver takes care of it:

[8]:
gfu = Solve(diffusion + convection == 1*v*dx, condense=False)
Draw (gfu);

Hybrid Discontinuous Galerkin methods

use additionally the hybrid facet variable on the skeleton:

\[\DeclareMathOperator{\Div}{div} A(u,\widehat u; v, \widehat v) = \sum_T \int_T \nabla u \nabla v - \sum_T \int_{\partial T} n \nabla u (v-\widehat v) - \sum_T \int_{\partial T} n \nabla v (u-\widehat u) + \frac{\alpha p^2}{h} \sum_F \int_F (u-\widehat u)(v-\widehat v)\]

The jump term is now replaced by the difference \(u - \widehat u\).

No additional matrix entries across elements are produced, we don’t need the flag dgjumps:

[9]:
order=4
V = L2(mesh, order=order)
F = FacetFESpace(mesh, order=order)
fes = V*F
(u,uhat), (v,vhat) = fes.TnT()

Now, the jump is the difference between the element term and the facet term:

[10]:
jump_u = u-uhat
jump_v = v-vhat
[11]:
alpha = 4
h = specialcf.mesh_size
n = specialcf.normal(mesh.dim)
dS = dx(element_boundary=True)

hdg_diffusion = grad(u)*grad(v)*dx + \
    alpha*order**2/h*jump_u*jump_v*dS + \
    (-grad(u)*n*jump_v - grad(v)*n*jump_u)*dS

b = CF( (20,1) )
uup = IfPos(b*n, u, uhat)
hdg_convection = -b * u * grad(v)*dx + b*n*uup*jump_v *dS

Dirichlet boundary conditions are posed for the facet variable. The element unknowns are coupled only via the facet variable. Now Solve eliminates them by static condensation, see unit 2.7:

[12]:
gfu = Solve(hdg_diffusion + hdg_convection == 1*v*dx, uhat[BND(".*")] == 0)
Draw (gfu[u], mesh, "u-HDG");

The condensed system matrix is much smaller than the DG matrix:

[13]:
a = BilinearForm(hdg_diffusion + hdg_convection, condense=True).Assemble()
print ("A non-zero elements:", a.mat.nze)
A non-zero elements: 4650

Projected Jumps

The polynomial order of the facet space can be reduced by one by inserting an \(L_2\)-projection into the penalty term. This can be implemented by keeping the highest order basis functions of the facet space discontinuous, see Lehrenfeld-Schöberl: High order exactly divergence-free Hybrid Discontinuous Galerkin Methods for unsteady incompressible flows:

\[\DeclareMathOperator{\Div}{div} A(u,\widehat u; v, \widehat v) = \sum_T \int_T \nabla u \nabla v - \sum_T \int_{\partial T} n \nabla u (v-\widehat v) - \sum_T \int_{\partial T} n \nabla v (u-\widehat u) + \frac{\alpha p^2}{h} \sum_F \int_F (\Pi u-\widehat u)(\Pi v-\widehat v)\]

This is achieved by setting the flag highest_order_dc=True in the FacetFESpace. The number of matrix entries is reduced, while the order of convergence is preserved. This trick does not work in the case of significant convection.

[14]:
order=4
V = L2(mesh, order=order)
F = FacetFESpace(mesh, order=order, highest_order_dc=True)
fes = V*F
(u,uhat), (v,vhat) = fes.TnT()

jump_u = u-uhat
jump_v = v-vhat

alpha = 2
lhs = grad(u)*grad(v)*dx + \
    alpha*(order+1)**2/h*jump_u*jump_v*dS + \
    (-grad(u)*n*jump_v - grad(v)*n*jump_u)*dS

gfu = Solve(lhs == 1*v*dx, uhat[BND(".*")] == 0)
Draw (gfu[u], mesh, "u-HDG")

a = BilinearForm(lhs, condense=True).Assemble()
print ("A non-zero elements:", a.mat.nze)
A non-zero elements: 2976

Remarks on sparsity pattern in NGSolve

Remark 1: The sparsity pattern is set up a priori

  • The sparsity pattern of a sparse matrix in NGSolve is independent of its entries (it is set up a priori).

  • We can have "non-zero" entries that have the value 0

Below we show the reserved memory for the sparse matrix and the (numerically) non-zero entries in this sparse matrix.

[15]:
fes2 = L2(mesh, order=order, dgjumps=True)
u,v=fes2.TnT()
a3 = BilinearForm(u*v*dx + (u+u.Other())*v*dx(skeleton=True)).Assemble()
[16]:
import scipy.sparse as sp
import matplotlib.pylab as plt
plt.rcParams['figure.figsize'] = (12, 12)
A = sp.csr_matrix(a3.mat.CSR())
fig = plt.figure(); ax1 = fig.add_subplot(121); ax2 = fig.add_subplot(122)
ax1.set_xlabel("numerically non-zero"); ax1.spy(A)
ax2.set_xlabel("reserved entries (potentially non-zero)"); ax2.spy(A,precision=-1)
plt.show()
../../_images/i-tutorials_unit-2.8-DG_DG_31_0.png

Remark 2: Sparsity pattern with and without dgjumps=True is different

[17]:
fig = plt.figure(); ax1 = fig.add_subplot(121); ax2 = fig.add_subplot(122)
for ax, dgjumps in [(ax1,False), (ax2,True)]:
    fesx = L2(mesh, order=order, dgjumps=dgjumps)
    ux,vx = fesx.TnT()
    amass = BilinearForm(ux*vx*dx).Assemble()
    ax.set_xlabel("dgjumps="+str(dgjumps))
    ax.spy(sp.csr_matrix(amass.mat.CSR()), precision=-1)
plt.show()
../../_images/i-tutorials_unit-2.8-DG_DG_33_0.png

Remark 3: Dof numbering of higher order FESpaces

  • In NGSolve FESpaces typically have a numbering where the first block of dofs corresponds to a low order subspace (which is convenient for iterative solvers).

  • For L2 this means that the first dofs correspond to the constants on elements.

  • You can turn this behavior off for some spaces, e.g. for L2 by adding the flag all_dofs_together.

We demonstrate this in the next comparison:

[18]:
plt.rcParams['figure.figsize'] = (15, 15)
fig = plt.figure()
ax = [fig.add_subplot(131), fig.add_subplot(132), fig.add_subplot(133)]

for i, (order, all_dofs_together, label) in enumerate([(0,False, "non-zeros (p=0)"),
                                                    (1,False,"non-zeros (p=1, low order + high order)"),
                                                    (1,True,"non-zeros (p=1, all_dofs_together)")]):
    a = BilinearForm(L2(mesh,order=order,dgjumps=True,all_dofs_together=all_dofs_together))
    a.Assemble()
    ax[i].spy(sp.csr_matrix(a.mat.CSR()),markersize=3,precision=-1)
    ax[i].set_xlabel(label)
../../_images/i-tutorials_unit-2.8-DG_DG_36_0.png