This page was generated from unit-2.11-matrixfree/matrixfree.ipynb.

2.11 Matrix free operator application

Usually, we assemble matrices in sparse matrix format. Certain methods allow us to improve performance and to reduce memory requirements considerably by avoiding building and storing the system matrix. The downside of this approach is that it is more difficult to build preconditioners.

Hybrid mixed method

Consider the hybrid mixed method

\[\begin{split}\begin{array}{ccccl} A \sigma & + & B^T u & = & f \\ B \sigma & & & = & g \end{array}\end{split}\]

where the matrix \(A\) comes from

\[\int \sigma \tau dx\]

and the matrix \(B\) from

\[\sum_T \int_T \operatorname{div} \, \sigma \, v_T - \int_{\partial T} \sigma_n v_F\]

For \(\sigma\) we use a VectorL2 space, with a Piola mapping to the physical elements

[1]:
from ngsolve import *
from ngsolve.webgui import Draw
from ngsolve.fem import MixedFE

mesh = Mesh(unit_square.GenerateMesh(maxh=0.3))
order=1
Sigma = VectorL2(mesh, order=order, piola=True)
Vt = L2(mesh, order=order-1)
Vf = FacetFESpace(mesh, order=order)
V = Vt*Vf
sigma,tau = Sigma.TnT()
(ut,uf), (vt,vf) = V.TnT()
[2]:
a = BilinearForm(sigma*tau * dx)

n = specialcf.normal(mesh.dim)
dS = dx(element_boundary=True)
b = BilinearForm(div(sigma) * vt * dx - sigma*n*vf * dS).Assemble();

Compute the element matrices …

We should observe that the element matrices of the \(A\) operator are block-diagonal with \(2\times 2\) blocks, and that each element matrix of \(B\) belongs to one of two equivalence classes.

[3]:
for el in mesh.Elements():
    felS = Sigma.GetFE(el)
    trafo = mesh.GetTrafo(el)
    elmat = a.integrators[0].CalcElementMatrix(felS, trafo)
    print (elmat)
       1       0       0    -0.5       0       0
       0     0.5       0       0   -0.25       0
       0       0 0.166667       0       0 -0.0833333
    -0.5       0       0     0.5       0       0
       0   -0.25       0       0    0.25       0
       0       0 -0.0833333       0       0 0.0833333

 0.544455       0       0 -0.18327       0       0
       0 0.272227       0       0 -0.091635       0
       0       0 0.0907425       0       0 -0.030545
 -0.18327       0       0 0.520866       0       0
       0 -0.091635       0       0 0.260433       0
       0       0 -0.030545       0       0 0.086811

 0.468768       0       0 -0.338876       0       0
       0 0.234384       0       0 -0.169438       0
       0       0 0.078128       0       0 -0.0564793
 -0.338876       0       0 0.778289       0       0
       0 -0.169438       0       0 0.389144       0
       0       0 -0.0564793       0       0 0.129715

 0.471122       0       0 -0.253486       0       0
       0 0.235561       0       0 -0.126743       0
       0       0 0.0785203       0       0 -0.0422477
 -0.253486       0       0 0.667036       0       0
       0 -0.126743       0       0 0.333518       0
       0       0 -0.0422477       0       0 0.111173

 0.395521       0       0 -0.31666       0       0
       0 0.19776       0       0 -0.15833       0
       0       0 0.0659201       0       0 -0.0527767
 -0.31666       0       0 0.885601       0       0
       0 -0.15833       0       0  0.4428       0
       0       0 -0.0527767       0       0  0.1476

 0.363113       0       0 -0.351628       0       0
       0 0.181556       0       0 -0.175814       0
       0       0 0.0605188       0       0 -0.0586046
 -0.351628       0       0   1.029       0       0
       0 -0.175814       0       0 0.514499       0
       0       0 -0.0586046       0       0  0.1715

 0.721841       0       0 -0.621509       0       0
       0 0.360921       0       0 -0.310755       0
       0       0 0.120307       0       0 -0.103585
 -0.621509       0       0 0.881459       0       0
       0 -0.310755       0       0 0.44073       0
       0       0 -0.103585       0       0 0.14691

 0.545301       0       0 -0.41047       0       0
       0 0.272651       0       0 -0.205235       0
       0       0 0.0908835       0       0 -0.0684117
 -0.41047       0       0 0.76744       0       0
       0 -0.205235       0       0 0.38372       0
       0       0 -0.0684117       0       0 0.127907

 0.538787       0       0 -0.130151       0       0
       0 0.269393       0       0 -0.0650754       0
       0       0 0.0897978       0       0 -0.0216918
 -0.130151       0       0 0.495445       0       0
       0 -0.0650754       0       0 0.247723       0
       0       0 -0.0216918       0       0 0.0825742

 0.438564       0       0 -0.305684       0       0
       0 0.219282       0       0 -0.152842       0
       0       0 0.073094       0       0 -0.0509474
 -0.305684       0       0 0.783108       0       0
       0 -0.152842       0       0 0.391554       0
       0       0 -0.0509474       0       0 0.130518

 0.511232       0       0 -0.265398       0       0
       0 0.255616       0       0 -0.132699       0
       0       0 0.0852053       0       0 -0.0442331
 -0.265398       0       0 0.626792       0       0
       0 -0.132699       0       0 0.313396       0
       0       0 -0.0442331       0       0 0.104465

 0.412015       0       0 -0.296495       0       0
       0 0.206007       0       0 -0.148248       0
       0       0 0.0686691       0       0 -0.0494159
 -0.296495       0       0 0.820139       0       0
       0 -0.148248       0       0 0.41007       0
       0       0 -0.0494159       0       0 0.13669

 0.520553       0       0 -0.539121       0       0
       0 0.260277       0       0 -0.26956       0
       0       0 0.0867589       0       0 -0.0898535
 -0.539121       0       0 1.03861       0       0
       0 -0.26956       0       0 0.519304       0
       0       0 -0.0898535       0       0 0.173101

 0.418673       0       0 -0.256739       0       0
       0 0.209337       0       0 -0.128369       0
       0       0 0.0697789       0       0 -0.0427898
 -0.256739       0       0 0.754562       0       0
       0 -0.128369       0       0 0.377281       0
       0       0 -0.0427898       0       0 0.12576

 0.601841       0       0 -0.472487       0       0
       0 0.30092       0       0 -0.236244       0
       0       0 0.100307       0       0 -0.0787479
 -0.472487       0       0 0.786328       0       0
       0 -0.236244       0       0 0.393164       0
       0       0 -0.0787479       0       0 0.131055

 0.363113       0       0 -0.374598       0       0
       0 0.181556       0       0 -0.187299       0
       0       0 0.0605188       0       0 -0.062433
 -0.374598       0       0 1.07494       0       0
       0 -0.187299       0       0 0.537469       0
       0       0 -0.062433       0       0 0.179156

 0.52825       0       0 -0.0858047       0       0
       0 0.264125       0       0 -0.0429023       0
       0       0 0.0880416       0       0 -0.0143008
 -0.0858047       0       0 0.487198       0       0
       0 -0.0429023       0       0 0.243599       0
       0       0 -0.0143008       0       0 0.0811997

 0.533605       0       0 -0.2905       0       0
       0 0.266802       0       0 -0.14525       0
       0       0 0.0889341       0       0 -0.0484166
 -0.2905       0       0 0.626663       0       0
       0 -0.14525       0       0 0.313331       0
       0       0 -0.0484166       0       0 0.104444

 0.462213       0       0 -0.1491       0       0
       0 0.231106       0       0 -0.0745502       0
       0       0 0.0770355       0       0 -0.0248501
 -0.1491       0       0 0.588973       0       0
       0 -0.0745502       0       0 0.294487       0
       0       0 -0.0248501       0       0 0.0981622

 0.788452       0       0 -0.416608       0       0
       0 0.394226       0       0 -0.208304       0
       0       0 0.131409       0       0 -0.0694347
 -0.416608       0       0 0.537208       0       0
       0 -0.208304       0       0 0.268604       0
       0       0 -0.0694347       0       0 0.0895346

 0.773195       0       0 -0.436502       0       0
       0 0.386598       0       0 -0.218251       0
       0       0 0.128866       0       0 -0.0727504
 -0.436502       0       0 0.569758       0       0
       0 -0.218251       0       0 0.284879       0
       0       0 -0.0727504       0       0 0.0949597

 0.31625       0       0 -0.060888       0       0
       0 0.158125       0       0 -0.030444       0
       0       0 0.0527083       0       0 -0.010148
 -0.060888       0       0 0.802237       0       0
       0 -0.030444       0       0 0.401119       0
       0       0 -0.010148       0       0 0.133706

 0.479999       0       0 -0.262317       0       0
       0 0.239999       0       0 -0.131158       0
       0       0 0.0799998       0       0 -0.0437195
 -0.262317       0       0 0.66419       0       0
       0 -0.131158       0       0 0.332095       0
       0       0 -0.0437195       0       0 0.110698

 0.539466       0       0 -0.229267       0       0
       0 0.269733       0       0 -0.114633       0
       0       0 0.089911       0       0 -0.0382112
 -0.229267       0       0 0.560857       0       0
       0 -0.114633       0       0 0.280429       0
       0       0 -0.0382112       0       0 0.0934762

[4]:
for el in mesh.Elements():
    felS = Sigma.GetFE(el)
    felV = V.GetFE(el)
    fel = MixedFE(felS, felV)
    trafo = mesh.GetTrafo(el)

    # try integrators 0 and 1 ...
    elmat = b.integrators[0].CalcElementMatrix(fel, trafo)
    print (elmat)
       0       0       1       0    -1.5    -0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0       0       1       0    -1.5    -0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0 4.33364e-17      -1       0     1.5     0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0 6.09104e-17      -1       0     1.5     0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0       0       1       0    -1.5    -0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0       0       1       0    -1.5    -0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0 1.04525e-17      -1       0     1.5     0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0 5.01659e-17       1       0    -1.5    -0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0       0       1       0    -1.5    -0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0 4.04252e-17      -1       0     1.5     0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0       0      -1       0     1.5     0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0       0       1       0    -1.5    -0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0       0       1       0    -1.5    -0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0       0       1       0    -1.5    -0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0       0      -1       0     1.5     0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0 -4.47693e-18      -1       0     1.5     0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0 1.29672e-16      -1       0     1.5     0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0       0       1       0    -1.5    -0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0 -8.01618e-17       1       0    -1.5    -0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0       0       1       0    -1.5    -0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0 -2.4425e-16       1       0    -1.5    -0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0 -4.95061e-17      -1       0     1.5     0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0       0       1       0    -1.5    -0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

       0       0      -1       0     1.5     0.5
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0
       0       0       0       0       0       0

Geometry-free matrix multiplication

NGSolve can benefit from the geometry-independent element matrices. Just one matrix per equivalence class is stored, and the matrix-vector product is performed for all elements simultaneously using dense matrix algebra.

[5]:
from netgen.csg import *
geom = CSGeometry()
geom.Add (Sphere(Pnt(50,50,50),80) \
          -Cylinder(Pnt(-100,0,0),Pnt(200,0,0), 40) \
          -Cylinder(Pnt(100,-100,100),Pnt(100,200,100),40)
          -Cylinder(Pnt(0,100,-100), Pnt(0,100,200),40)
          -Sphere(Pnt(50,50,50),50))
# geom.Draw()

mesh = Mesh(geom.GenerateMesh(maxh=25)).Curve(5)
# Draw (mesh)

The same as above, with the geom_free flag for the BilinearForm:

[6]:
order=6
Sigma = VectorL2(mesh, order=order, piola=True, tp=True)
Vt = L2(mesh, order=order-1)
Vf = FacetFESpace(mesh, order=order, dirichlet=[2])
V = Vt*Vf
print ("Sigma.ndof =", Sigma.ndof, ", V.ndof =", V.ndof)
sigma,tau = Sigma.TnT()
(ut,uf), (vt,vf) = V.TnT()

n = specialcf.normal(mesh.dim)
dS = dx(element_boundary=True)
b = BilinearForm(div(sigma) * vt * dx - sigma*n*vf * dS, geom_free=True).Assemble();
Sigma.ndof = 118692 , V.ndof = 58492

Check the timing with geom_free=True/False:

[7]:
vx = b.mat.CreateRowVector()
vy = b.mat.CreateColVector()
vx[:] = 1

%timeit vy.data = b.mat * vx
3.43 ms ± 33.3 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

L2 finite element spaces have a Mass method generating a linear operator for the multiplication with the block-diagonal mass matrix. In the case of variable coefficients or curved elements it uses numerical integration. It also provides an inverse operator:

[8]:
ainv = Sigma.Mass(rho=1).Inverse()

Check the timing with tp=True/False:

[9]:
vx = ainv.CreateRowVector()
vy = ainv.CreateColVector()
vx[:] = 1

%timeit vy.data = ainv * vx
52.6 ms ± 769 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Combine the operators to form the Schur complement, which is actually a discretization of the Laplace operator:

[10]:
Laplace = b.mat @ ainv @ b.mat.T
[11]:
f = LinearForm(1*vt*dx).Assemble()

proj = Projector(V.FreeDofs(), True)

gfu = GridFunction (V)
from time import time
start = time()
with TaskManager():
    inv = solvers.CGSolver(Laplace, proj, maxiter=5000)
    gfu.vec.data = inv * f.vec
print ("iterations =", inv.iterations, ", time =", time()-start)
iterations = 3150 , time = 57.576348066329956

The iteration count is very high since we used only the most trivial preconditioner. We can add a low order coarse-grid preconditioner to get rid of the mesh dependency, and also local inverses to improve the \(p\)-dependency.

[12]:
Draw (gfu.components[1], mesh, "gfu1", draw_vol=False);