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
where the matrix \(A\) comes from
and the matrix \(B\) from
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);