Featured

## Hidden DOFs

Let us consider the Poisson problem in $\Omega\subset \mathbb{R}^d$, that is,

\begin{align*} - \Delta u &= f \quad \text{ in } \Omega, \\ u &= 0 \quad \text{ on } \partial\Omega. \end{align*}

from ngsolve import *
from netgen.geom2d import unit_square
from math import pi

mesh = Mesh(unit_square.GenerateMesh(maxh=1/4))


For such a problem, a meaningful choice of finite element spaces for an HDG method with $L^2$-lifting is the following:

\begin{align*} V_h &= \{ v_h \in L^2(\mathcal{T}_h)\colon v_h|_K \in P^k(K), ~\forall\, K \in \mathcal{T}_h\} \\ {\widehat{V}}_h &= \{ \widehat{v}_h \in L^2(\mathcal{F}_h)\colon \widehat{v}_h|_F \in P^k(F), ~\forall\, F \in \mathcal{F}_h;~\widehat{v}_h=0~\text{on}~\partial\Omega\} \end{align*}

The discrete weak formulation is then given by: With $[\![ v_h ]\!] = v_h - \widehat{v}_h$, find $(u_h,\widehat{u}_h) \in V_h\times\widehat{V}_h$ such that, for all $(v_h,\widehat{v}_h) \in V_h\times\widehat{V}_h$, there holds

\begin{align*} \sum_{K\in\mathcal{T}_h} \left( \int_K \nabla u_h \cdot \nabla v_h \,dx - \oint_{\partial K} (\nabla u_h \cdot \mathbf{n}_K) [\![v_h]\!] \,ds - \oint_{\partial K} [\![u_h]\!](\nabla v_h \cdot \mathbf{n}_K) \,ds + \oint_{\partial K} \frac{k}{h} [\![u_h]\!] [\![v_h]\!] \,ds + \sigma_\ell \int_K \mathcal{L}([\![u_h]\!]) \cdot \mathcal{L}([\![v_h]\!]) \,dx \right)  = \sum_{K\in\mathcal{T}_h} \int_K f v_h \,dx. \end{align*}

Here, the integral multiplied by $\sigma_\ell>1$ represents a lifting term which ensures stability for independent of $h$, $k$ and shape regularity. The lifting is defined element-by-element and depends only on element-local (including the element boundary) values. We define it using another FE space as follows:

\begin{align*}  &\text{For all }\varphi\in L^2(\mathcal{F}_h)\text{, the lifting }\mathcal{L}(\varphi)\in\mathbf{S}_h\text{ is defined as the solution of } \\ &\int_K \mathcal{L}(\varphi) \cdot \mathbf{s}_h \,dx = \oint_{\partial K} \varphi (\mathbf{s}_h\cdot\mathbf{n}_K) \,ds, \quad \forall\,\mathbf{s}_h\in\mathbf{S}_h, \quad \forall\, K\in\mathcal{T}_h, \\ &\mathbf{S}_h = \nabla V_h = \{ \mathbf{s}_h \in (L^2(\mathcal{T}_h))^d \colon \mathbf{s}_h|_K \in (P^{k-1}(K))^d, ~\forall\, K \in \mathcal{T}_h\}. \end{align*}

However, the actual implementation of such a method looks slightly different. We introduce the compound FE space:

\begin{align*} X_h &= \{ (v_h,\widehat{v}_h, \mathbf{s}_h) \colon v_h \in V_h, ~\widehat{v}_h \in \widehat{V}_h, ~\mathbf{s}_h\in \mathbf{S}_h \} \end{align*}

order = 8

V = L2(mesh, order=order)
Vhat = FacetFESpace(mesh, order=order, dirichlet=[1,2,3,4])
S = VectorL2(mesh, order=order-1, hide_all_dofs=True)
X = FESpace([V,Vhat,S])


In the VectorL2 FE space the "hide_all_dofs" flag marks all corresponding dofs as HIDDEN_DOFs (instead of LOCAL_DOF). Here are a few important properties of hidden d.o.f.s

• Hidden d.o.f.s will be removed (and will not be restored!) during static condensation. This has the following implications:
• A hidden d.o.f. is a LOCAL_DOF in the sense that it only couples with other d.o.f.s on the same element
• The entries of a r.h.s. vector of a linear system corresponding to a hidden d.o.f. are always zero
• During static condensation the (element-local) matrix blocks for hidden d.o.f.s have to be invertible
• No non-zero entries are reserved for hidden d.o.f.s in sparse matrices. Consequently, a hidden d.o.f. that is involved in a bilinear form will be ignored if not eliminated through static condensation.
• Hidden d.o.f.s (as other coupling types) only behave different from other coupling types when it comes to solving linear systems and static condensation is applied. This can be done with the "eliminate_internal" flag of a bilinear form or with the "eliminate_hidden" flag where the latter only applies static condensation of HIDDEN_DOFs and not for LOCAL_DOFs.

Then, the weak formulation of the implementation variant reads as follows. Find $(u_h,\widehat{u}_h, \mathbf{r}_h) \in X_h$ such that, for all $(v_h,\widehat{v}_h, \mathbf{s}_h) \in X_h$, there holds

\begin{align*} \sum_{K\in\mathcal{T}_h} \bigg( \int_K \nabla u_h \cdot \nabla v_h \,dx &- \oint_{\partial K} (\nabla u_h \cdot \mathbf{n}_K) [\![v_h]\!] \,ds - \oint_{\partial K} [\![u_h]\!](\nabla v_h \cdot \mathbf{n}_K) \,ds + \oint_{\partial K} \frac{k}{h} [\![u_h]\!] [\![v_h]\!] \,ds \bigg)  \\ &+\sigma_\ell\sum_{K\in\mathcal{T}_h} \left( -\int_K \mathbf{r}_h \cdot \mathbf{s}_h \,dx + \oint_{\partial K} [\![u_h]\!](\mathbf{s}_h \cdot \mathbf{n}_K) \,ds + \oint_{\partial K} [\![v_h]\!] (\mathbf{r}_h \cdot \mathbf{n}_K)\,ds  \right) = \sum_{K\in\mathcal{T}_h} \int_K f v_h \,dx. \end{align*}

sigma = 2
sigma_lift = 2

(u,uhat,r),(v,vhat,s) = X.TnT()

n = specialcf.normal(mesh.dim)
h = specialcf.mesh_size

jmp_u = u-uhat
jmp_v = v-vhat

a = BilinearForm( X, symmetric=True, eliminate_hidden=True)
a += SymbolicBFI( - sigma_lift*(r*s) )
a += SymbolicBFI( sigma_lift*( jmp_u*(s*n) + jmp_v*(r*n) ), element_boundary=True )

f = LinearForm(X)
f += SymbolicLFI( 2*pi**2*sin(pi*x)*sin(pi*y)*v )


Here, a right-hand side term $f$ is chosen such that in the end, the exact solution is known and an error can be computed. Note that use "eliminate_hidden=True" here only (in contrast to a full "eliminate_internal=True"). This flag is not needed whenever "eliminate_internal=True" is used. However, whenever hidden DOFs are used, they have to be eliminated in the corresponding bilinear form, regardless of static condensation for higher order bubbles is used or not.

Now, one can assemble the linear system and take a look at the number of non-zero entries in the matrix A and its factors which arise due to static condensation:

a.Assemble()
f.Assemble()

print("a.mat has {} non-zero entries.".format(a.mat.nze))



When applying static condensation (for all LOCAL_DOFs)  we simply obtain

a = BilinearForm( X, symmetric=True, eliminate_internal=True)
...
print("a.mat has {} non-zero entries.".format(a.mat.nze))
print("a.inner_solve has {} non-zero entries.".format(a.inner_solve.nze))
print("a.harmonic_extension has {} non-zero entries.".format(a.harmonic_extension.nze))

## Comparison of non-zero entries

The numbers for the method using hidden DOFs and compression of the FE spaces with static condensation are:

a.mat has 22680 non-zero entries.
a.inner_solve has 105300 non-zero entries.
a.harmonic_extension has 63180 non-zero entries.


The output without hidden DOFs and with static condensation is as follows:

a.mat has 22680 non-zero entries.
a.inner_solve has 711828 non-zero entries.
a.harmonic_extension has 164268 non-zero entries.


One observes the same number of non-zero entries in the Schur complement a.mat, but the factors a.inner_solve and a.harmonic_extension have significantly fewer non-zero entries when hidden DOFs are used. This actually leads to the fact that introducing such a large space for the lifting DOFs is only marginally more expensive and only during setup of the matrix.

## Compress d.o.f.s

Hidden d.o.f.s don't play a role in the solution, but only a local role in defining some projection-type operators. Hence, we don't need to reserve a global d.o.f. number for a hidden d.o.f.. To prevent hidden d.o.f.s from obtaining a global d.o.f. number, we can use a wrapper which is called a CompressedFESpace that removes HIDDEN_DOFs and UNUSED_DOFs from the global numbering. For an arbitrary FESpace V you obtain a compressed spaces as follows:

print(V.ndof)
V = Compress(V)
print(V.ndof)

When applied to a CompoundFESpace we use

print("dofs before compression:", X.ndof)
X = CompressCompound(X)
print("dofs after compression:", X.ndof)

resulting in a reduction of global d.o.f.s:

dofs before compression: 6876
dofs after compression: 3132


However, the non-zero entries in the matrices are essentially unaffected by the compression.

## Projected jumps

Another example where hidden d.o.f.s can be used are "projected jumps" where the highest order functions in the FacetFESpace are made element-local to realize a facet-wise $L^2$ projection into the space of polynomials up to degree $k-1$. With the concept of hidden d.o.f.s this is easily achieved by changing only the one line in the definition of the FacetFESpace:

Vhat = FacetFESpace(mesh, order=order, dirichlet=[1,2,3,4], highest_order_dc=True, hide_highest_order_dc=True)


A fully functional python script is attached to this article. In this script, more options to play with are included.

Attachments
Poisson HDG L2lifting.py [3.25Kb]
Uploaded Monday, 10 September 2018 by Christoph Lehrenfeld