This page was generated from unit-2.1.3-bddc/bddc.ipynb.

2.1.3 Element-wise BDDC Preconditioner

The element-wise BDDC (Balancing Domain Decomposition preconditioner with Constraints) preconditioner in NGSolve is a good general purpose preconditioner that works well both in the shared memory parallel mode as well as in distributed memory mode. In this tutorial, we discuss this preconditioner, related built-in options, and customization from python.

Let us start with a simple description of the element-wise BDDC in the context of Lagrange finite element space \(V\). Here the BDDC preconditoner is constructed on an auxiliary space \(\widetilde{V}\) obtained by connecting only element vertices (leaving edge and face shape functions discontinuous). Although larger, the auxiliary space allows local elimination of edge and face variables. Hence an analogue of the original matrix \(A\) on this space, named \(\widetilde A\), is less expensive to invert. This inverse is used to construct a preconditioner for \(A\) as follows:

\[C_{BDDC}^{-1} = R {\,\widetilde{A}\,}^{-1}\, R^t\]

Here, \(R\) is the averaging operator for the discontinous edge and face variables.

To construct a general purpose BDDC preconditioner, NGSolve generalizes this idea to all its finite element spaces by a classification of degrees of freedom. Dofs are classified into (condensable) LOCAL_DOFs that we saw in 1.4 and a remainder that includes these types:

WIREBASKET_DOF
INTERFACE_DOF

The original finite element space \(V\) is obtained by requiring conformity of both the above types of dofs, while the auxiliary space \(\widetilde{V}\) is obtained by requiring conformity of WIREBASKET_DOFs only.

Here is a figure of a typical function in the default \(\widetilde{V}\) (and the code to generate this is at the end of this tutorial) when \(V\) is the Lagrange space:

title

[1]:

import netgen.gui
from ngsolve import *
from ngsolve.la import EigenValues_Preconditioner
from netgen.csg import unit_cube
from netgen.geom2d import unit_square
SetHeapSize(100*1000*1000)

[2]:

mesh = Mesh(unit_cube.GenerateMesh(maxh=0.5))
# mesh = Mesh(unit_square.GenerateMesh(maxh=0.5))

Built-in options

Let us define a simple function to study how the spectrum of the preconditioned matrix changes with various options.

Effect of condensation

[3]:

def TestPreconditioner (p, condense=False, **args):
    fes = H1(mesh, order=p, **args)
    u,v = fes.TnT()
    a = BilinearForm(fes, eliminate_internal=condense)
    a += grad(u)*grad(v)*dx + u*v*dx
    c = Preconditioner(a, "bddc")
    a.Assemble()
    return EigenValues_Preconditioner(a.mat, c.mat)

[4]:

lams = TestPreconditioner(5)
print (lams[0:3], "...\n", lams[-3:])

 1.00409
 1.11195
 1.34829
 ...
  33.7436
 37.2337
 38.0012

Here is the effect of static condensation on the BDDC preconditioner.

[5]:

lams = TestPreconditioner(5, condense=True)
print (lams[0:3], "...\n", lams[-3:])

 1.00139
 1.04212
 1.12173
 ...
  6.95459
 7.03965
  7.3257

Tuning the auxiliary space

Next, let us study the effect of a few built-in flags for finite element spaces that are useful for tweaking the behavior of the BDDC preconditioner. The effect of these flags varies in two (2D) and three dimensions (3D), e.g.,

  • wb_fulledges=True: This option keeps all edge-dofs conforming (i.e. they are marked WIREBASKET_DOFs). This option is only meaningful in 3D. If used in 2D, the preconditioner becomes a direct solver.

  • wb_withedges=True: This option keeps only the first edge-dof conforming (i.e., the first edge-dof is marked WIREBASKET_DOF and the remaining edge-dofs are marked INTERFACE_DOFs).

The complete situation is a bit more complex due to the fact these options can take the three values True, False, or Undefined, the two options can be combined, and the space dimension can be 2 or 3. The default value of these flags in NGSolve is Undefined. Here is a table with the summary of the effect of these options:

wb_fulledges

wb_withedges

2D

3D

True

any value

all

all

False/Undefined

Undefined

none

first

False/Undefined

False

none

none

False/Undefined

True

first

first

An entry \(X \in\) {all, none, first} of the last two columns is to be read as follows: \(X\) of the edge-dofs is(are) WIREBASKET_DOF(s).

Here is an example of the effect of one of these flag values.

[6]:

lams = TestPreconditioner(5, condense=True,
                          wb_withedges=False)
print (lams[0:3], "...\n", lams[-3:])

 1.00468
 1.09359
 1.32949
 ...
  31.1877
 33.3524
 34.3632

Clearly, when moving from the default case (where the first of the edge dofs are wire basket dofs) to the case (where none of the edge dofs are wire basket dofs), the conditioning became less favorable.

Customize

From within python, we can change the types of degrees of freedom of finite element spaces, thus affecting the behavior of the BDDC preconditioner.

To depart from the default and commit the first two edge dofs to wire basket, we perform the next steps:

[7]:

fes = H1(mesh, order=10)
u,v = fes.TnT()

for ed in mesh.edges:
    dofs = fes.GetDofNrs(ed)
    for d in dofs:
        fes.SetCouplingType(d, COUPLING_TYPE.INTERFACE_DOF)

    # Set the first two edge dofs to be conforming
    fes.SetCouplingType(dofs[0], COUPLING_TYPE.WIREBASKET_DOF)
    fes.SetCouplingType(dofs[1], COUPLING_TYPE.WIREBASKET_DOF)

a = BilinearForm(fes, eliminate_internal=True)
a += grad(u)*grad(v)*dx + u*v*dx
c = Preconditioner(a, "bddc")
a.Assemble()

lams=EigenValues_Preconditioner(a.mat, c.mat)
max(lams)/min(lams)

[7]:

18.310200831381874

This is a slight improvement from the default.

[8]:

lams = TestPreconditioner (10, condense=True)
max(lams)/min(lams)

[8]:

27.55054816083112

Combine BDDC with AMG for large problems

The coarse inverse \({\,\widetilde{A}\,}^{-1}\) of BDDC is expensive on fine meshes. Using the option coarsetype=h1amg flag, we can ask BDDC to replace \({\,\widetilde{A}\,}^{-1}\) by an Algebraic MultiGrid (AMG) preconditioner. Since NGSolve’s h1amg is well-suited
for the lowest order Lagrange space, we use the option wb_withedges=False to ensure that \(\widetilde{A}\) is made solely with vertex unknowns.
[9]:

p = 5
mesh = Mesh(unit_cube.GenerateMesh(maxh=0.05))
fes = H1(mesh, order=p, dirichlet="left|bottom|back",
         wb_withedges=False)
print("NDOF = ", fes.ndof)
u,v = fes.TnT()
a = BilinearForm(fes)
a += grad(u)*grad(v)*dx
f = LinearForm(fes)
f += v*dx

with TaskManager():
    pre = Preconditioner(a, "bddc", coarsetype="h1amg")
    a.Assemble()
    f.Assemble()

    gfu = GridFunction(fes)
    solvers.CG(mat=a.mat, rhs=f.vec, sol=gfu.vec,
               pre=pre, maxsteps=500)
Draw(gfu)

NDOF =  1165206

iteration 0 error = 0.7073079321639637
iteration 1 error = 0.2923489925962686
iteration 2 error = 0.2850423590749115
iteration 3 error = 0.2909985858220177
iteration 4 error = 0.31960338063241023
iteration 5 error = 0.2548899214031629
iteration 6 error = 0.19211663159074405
iteration 7 error = 0.1544809206920569
iteration 8 error = 0.12629396108308197
iteration 9 error = 0.10147830081475578
iteration 10 error = 0.07424583493548154
iteration 11 error = 0.05662434993346135
iteration 12 error = 0.04501661464420655
iteration 13 error = 0.038222441472400503
iteration 14 error = 0.03168341537618145
iteration 15 error = 0.0251729569922349
iteration 16 error = 0.019311927758283765
iteration 17 error = 0.015540050652096493
iteration 18 error = 0.012426984200611802
iteration 19 error = 0.0099886996093495
iteration 20 error = 0.007772096531793511
iteration 21 error = 0.0060989889794596935
iteration 22 error = 0.004845023443492083
iteration 23 error = 0.0038936689458989385
iteration 24 error = 0.003121178650821568
iteration 25 error = 0.002514683062479336
iteration 26 error = 0.002018458722079843
iteration 27 error = 0.0016178291793917036
iteration 28 error = 0.0012923972201624525
iteration 29 error = 0.0010424470017298773
iteration 30 error = 0.0008356482973016196
iteration 31 error = 0.0006714480065978794
iteration 32 error = 0.0005352623318995786
iteration 33 error = 0.0004215503628216218
iteration 34 error = 0.0003333305814681234
iteration 35 error = 0.0002673703978420652
iteration 36 error = 0.0002129266723335907
iteration 37 error = 0.00016781697413274763
iteration 38 error = 0.00013450312384210092
iteration 39 error = 0.00010875174584049099
iteration 40 error = 8.77190798404098e-05
iteration 41 error = 7.041354864255908e-05
iteration 42 error = 5.698975226821396e-05
iteration 43 error = 4.549968019506661e-05
iteration 44 error = 3.658807446970805e-05
iteration 45 error = 2.9152587032894027e-05
iteration 46 error = 2.3080793175007102e-05
iteration 47 error = 1.870094550457846e-05
iteration 48 error = 1.5030440049793684e-05
iteration 49 error = 1.2051856509027843e-05
iteration 50 error = 9.778231424356914e-06
iteration 51 error = 7.826482451346208e-06
iteration 52 error = 6.201639849639216e-06
iteration 53 error = 4.939636623333283e-06
iteration 54 error = 3.914819687502274e-06
iteration 55 error = 3.1363011982838795e-06
iteration 56 error = 2.527140301843157e-06
iteration 57 error = 2.041077567756973e-06
iteration 58 error = 1.6311701124297885e-06
iteration 59 error = 1.2845984617590618e-06
iteration 60 error = 1.0402375507475985e-06
iteration 61 error = 8.352505853165419e-07
iteration 62 error = 6.684146548762174e-07
iteration 63 error = 5.326854521174166e-07
iteration 64 error = 4.261471708881116e-07
iteration 65 error = 3.4050622502674315e-07
iteration 66 error = 2.7074679826523523e-07
iteration 67 error = 2.174805905909416e-07
iteration 68 error = 1.7486873277612537e-07
iteration 69 error = 1.4059048242922973e-07
iteration 70 error = 1.1189128195963983e-07
iteration 71 error = 8.936904440266781e-08
iteration 72 error = 7.124603875921606e-08
iteration 73 error = 5.644888143150493e-08
iteration 74 error = 4.5592025087747955e-08
iteration 75 error = 3.624271333232043e-08
iteration 76 error = 2.929784240968944e-08
iteration 77 error = 2.3414605946005943e-08
iteration 78 error = 1.847097656155232e-08
iteration 79 error = 1.4931212690489944e-08
iteration 80 error = 1.2089091245447602e-08
iteration 81 error = 9.759677840391938e-09
iteration 82 error = 8.003500870773274e-09
iteration 83 error = 6.5263406063130575e-09
iteration 84 error = 5.23041538933932e-09
iteration 85 error = 4.2299551118433464e-09
iteration 86 error = 3.396578983743685e-09
iteration 87 error = 2.7552716778550195e-09
iteration 88 error = 2.1748380193028722e-09
iteration 89 error = 1.7382662379044517e-09
iteration 90 error = 1.3897208554677216e-09
iteration 91 error = 1.1169159738600958e-09
iteration 92 error = 8.947106306529196e-10
iteration 93 error = 7.209510834596976e-10
iteration 94 error = 5.787645250384608e-10
iteration 95 error = 4.5710701257180756e-10
iteration 96 error = 3.664196361203072e-10
iteration 97 error = 2.9452368427997325e-10
iteration 98 error = 2.3405624163196807e-10
iteration 99 error = 1.8874170437620892e-10
iteration 100 error = 1.5097074950897316e-10
iteration 101 error = 1.2061887061393986e-10
iteration 102 error = 9.810989306276126e-11
iteration 103 error = 8.067008372678654e-11
iteration 104 error = 6.557546546224767e-11
iteration 105 error = 5.280835033752963e-11
iteration 106 error = 4.193107100269396e-11
iteration 107 error = 3.337255772579617e-11
iteration 108 error = 2.6432210943517952e-11
iteration 109 error = 2.1316992546048517e-11
iteration 110 error = 1.7168165188629964e-11
iteration 111 error = 1.3753302307525789e-11
iteration 112 error = 1.1161010883243728e-11
iteration 113 error = 8.898840774569827e-12
iteration 114 error = 7.041277880302392e-12
iteration 115 error = 5.6523671185726564e-12
iteration 116 error = 4.5006005160173896e-12
iteration 117 error = 3.577220478148489e-12
iteration 118 error = 2.8852792710319253e-12
iteration 119 error = 2.303948173033582e-12
iteration 120 error = 1.8192936039891198e-12
iteration 121 error = 1.4528517863495352e-12
iteration 122 error = 1.1754329560735893e-12
iteration 123 error = 9.439381890780595e-13
iteration 124 error = 7.574388852600666e-13
iteration 125 error = 6.08379648943182e-13

Postscript

By popular demand, here is the code to draw the figure found at the beginning of this tutorial:

[10]:

from netgen.geom2d import unit_square
mesh = Mesh(unit_square.GenerateMesh(maxh=0.1))
fes_ho = Discontinuous(H1(mesh, order=10))
fes_lo = H1(mesh, order=1, dirichlet=".*")
fes_lam = Discontinuous(H1(mesh, order=1))
fes = FESpace([fes_ho, fes_lo, fes_lam])
uho, ulo, lam = fes.TrialFunction()

a = BilinearForm(fes)
a += Variation(0.5 * grad(uho)*grad(uho)*dx
               - 1*uho*dx
               + (uho-ulo)*lam*dx(element_vb=BBND))
gfu = GridFunction(fes)
solvers.Newton(a=a, u=gfu)
Draw(gfu.components[0])

Newton iteration  0
err =  0.3937351156371161
Newton iteration  1
err =  3.874027236775335e-15