Iterative Solvers

20.5. Iterative Solvers#

So far we have used direct solvers to solve the linear system of equations. Although a direct solver can profit from the sparse matrix, it’s arithmetic complexity is sub-optimal. For large-scale problems iterative solvers are a must.

The conjugate gradient (cg) method is the standard method for symmetric and positive definite matrices. It’s convergence rate depends on a preconditioner, what is a cheap approximative inverse to the matrix.

from ngsolve import *
from ngsolve.webgui import Draw

We generate a 3D geometry and mesh using the OCC constructive solid geometry (CSG) modeler:

from netgen.occ import *
cube = Box((0,0,0),(1,1,1))
cyl = Cylinder((0,0.5,0.5),X, r=0.2, h=1)
cube.faces.name = "outer"
cyl.faces.name = "cyl"
shape = cube-cyl
ea = { "euler_angles" : [-180, -80, 165] }
Draw(shape, **ea);
ngmesh = OCCGeometry(shape).GenerateMesh(maxh=0.1)

mesh = Mesh(ngmesh).Curve(3)

for l in range(0):
    mesh.Refine()

Draw (mesh, **ea);
fes = H1(mesh, order=3, dirichlet="outer", wb_withedges=False)
print ("we have", fes.ndof, "unknowns")

u,v = fes.TnT()

a = BilinearForm(grad(u)*grad(v)*dx)
f = LinearForm(1*v*dx)

# pre = preconditioners.MultiGrid(a)
pre = preconditioners.Local(a)
# pre = preconditioners.BDDC(a)

gfu = GridFunction(fes)
we have 23787 unknowns

assemble system and setup preconditioner in parallel:

with TaskManager():
    a.Assemble()
    f.Assemble()

solve the system using the preconditioned conjugate gradient method:

from ngsolve.krylovspace import CGSolver
from time import time

ts = time()
with TaskManager():
    # inv = a.mat.Inverse(inverse="sparsecholesky", freedofs=fes.FreeDofs())
    inv = CGSolver(mat=a.mat, pre=pre, printrates='\r', maxiter=1000)
    gfu.vec.data = inv * f.vec
te = time()
print ("needed", te-ts, "seconds for", fes.ndof, "unknowns")
CG iteration 1, residual = 0.047739949075105856     
CG iteration 2, residual = 0.05294727938543793     
CG iteration 3, residual = 0.05500960698375213     
CG iteration 4, residual = 0.04606877270694545     
CG iteration 5, residual = 0.02987610730035413     
CG iteration 6, residual = 0.023382706739268008     
CG iteration 7, residual = 0.01804714645520979     
CG iteration 8, residual = 0.0126509958311419     
CG iteration 9, residual = 0.008947539939651408     
CG iteration 10, residual = 0.007134209747036227     
CG iteration 11, residual = 0.006486603723518201     
CG iteration 12, residual = 0.006445337337709604     
CG iteration 13, residual = 0.006679235208108392     
CG iteration 14, residual = 0.006938067131387424     
CG iteration 15, residual = 0.0067050245746779836     
CG iteration 16, residual = 0.0055839674136199885     
CG iteration 17, residual = 0.0042079647269859044     
CG iteration 18, residual = 0.003077708743241627     
CG iteration 19, residual = 0.0022925537101338186     
CG iteration 20, residual = 0.0017210286974316954     
CG iteration 21, residual = 0.0013918891862596495     
CG iteration 22, residual = 0.0012867256293030037     
CG iteration 23, residual = 0.0012207824425805747     
CG iteration 24, residual = 0.0011508422442719902     
CG iteration 25, residual = 0.0010326259360892084     
CG iteration 26, residual = 0.00086508724160988     
CG iteration 27, residual = 0.0006834122553817228     
CG iteration 28, residual = 0.0005203227711120674     
CG iteration 29, residual = 0.0003856893581649338     
CG iteration 30, residual = 0.0003028901691673214     
CG iteration 31, residual = 0.00024687481859008163     
CG iteration 32, residual = 0.00020057770497666509     
CG iteration 33, residual = 0.000163997019088868     
CG iteration 34, residual = 0.00013686401056622847     
CG iteration 35, residual = 0.00011413361303568412     
CG iteration 36, residual = 9.451369431613465e-05     
CG iteration 37, residual = 8.065214654944006e-05     
CG iteration 38, residual = 7.150818336039983e-05     
CG iteration 39, residual = 6.34536219469067e-05     
CG iteration 40, residual = 5.598287673765576e-05     
CG iteration 41, residual = 4.817075802670545e-05     
CG iteration 42, residual = 3.92769967779306e-05     
CG iteration 43, residual = 3.084502899259497e-05     
CG iteration 44, residual = 2.3441691859581664e-05     
CG iteration 45, residual = 1.8068091668968068e-05     
CG iteration 46, residual = 1.4349833606446254e-05     
CG iteration 47, residual = 1.1766739852763844e-05     
CG iteration 48, residual = 9.964987268310974e-06     
CG iteration 49, residual = 9.056719106388723e-06     
CG iteration 50, residual = 8.561745619842754e-06     
CG iteration 51, residual = 8.026554471089203e-06     
CG iteration 52, residual = 7.097536033197572e-06     
CG iteration 53, residual = 5.944747573670308e-06     
CG iteration 54, residual = 4.555910099875377e-06     
CG iteration 55, residual = 3.3819070629162315e-06     
CG iteration 56, residual = 2.4711107258406215e-06     
CG iteration 57, residual = 1.8477611726611042e-06     
CG iteration 58, residual = 1.4857145554662006e-06     
CG iteration 59, residual = 1.282596445313242e-06     
CG iteration 60, residual = 1.197238196894268e-06     
CG iteration 61, residual = 1.1728671909923258e-06     
CG iteration 62, residual = 1.1261790491974705e-06     
CG iteration 63, residual = 9.894511688700764e-07     
CG iteration 64, residual = 7.958772966268729e-07     
CG iteration 65, residual = 5.901602467726152e-07     
CG iteration 66, residual = 4.353425978780634e-07     
CG iteration 67, residual = 3.323706447740351e-07     
CG iteration 68, residual = 2.6987925058119627e-07     
CG iteration 69, residual = 2.3028612227105223e-07     
CG iteration 70, residual = 2.0838537111743767e-07     
CG iteration 71, residual = 1.922849030135571e-07     
CG iteration 72, residual = 1.733607768111983e-07     
CG iteration 73, residual = 1.492597757047087e-07     
CG iteration 74, residual = 1.2342270369698867e-07     
CG iteration 75, residual = 1.0181258757645605e-07     
CG iteration 76, residual = 8.450738564506094e-08     
CG iteration 77, residual = 7.132426090476822e-08     
CG iteration 78, residual = 6.05078834419688e-08     
CG iteration 79, residual = 4.9963497374961447e-08     
CG iteration 80, residual = 4.00974917691095e-08     
CG iteration 81, residual = 3.144267225795033e-08     
CG iteration 82, residual = 2.5066837117426907e-08     
CG iteration 83, residual = 2.032771093314939e-08     
CG iteration 84, residual = 1.7509107499083012e-08     
CG iteration 85, residual = 1.6082328744006093e-08     
CG iteration 86, residual = 1.5078522274833037e-08     
CG iteration 87, residual = 1.372464070339818e-08     
CG iteration 88, residual = 1.2121170028104597e-08     
CG iteration 89, residual = 1.0087260742954472e-08     
CG iteration 90, residual = 7.8869971030574e-09     
CG iteration 91, residual = 5.867893509935677e-09     
CG iteration 92, residual = 4.3815173445283805e-09     
CG iteration 93, residual = 3.3856145575029244e-09     
CG iteration 94, residual = 2.8291252344435234e-09     
CG iteration 95, residual = 2.5139715744309356e-09     
CG iteration 96, residual = 2.3866714214933196e-09     
CG iteration 97, residual = 2.3287809378902394e-09     
CG iteration 98, residual = 2.181974072345939e-09     
CG iteration 99, residual = 1.9105330490467436e-09     
CG iteration 100, residual = 1.5467155609747464e-09     
CG iteration 101, residual = 1.1770806807467393e-09     
CG iteration 102, residual = 8.70406187610107e-10     
CG iteration 103, residual = 6.433449743345483e-10     
CG iteration 104, residual = 4.873107226189711e-10     
CG iteration 105, residual = 3.9075413958165465e-10     
CG iteration 106, residual = 3.3945106117397135e-10     
CG iteration 107, residual = 3.1515768113974216e-10     
CG iteration 108, residual = 3.0199909459266927e-10     
CG iteration 109, residual = 2.804796000047661e-10     
CG iteration 110, residual = 2.4414017824796583e-10     
CG iteration 111, residual = 1.9562916315981984e-10     
CG iteration 112, residual = 1.5087962227477278e-10     
CG iteration 113, residual = 1.1473143947385539e-10     
CG iteration 114, residual = 8.614755778111384e-11     
CG iteration 115, residual = 6.765128085970411e-11     
CG iteration 116, residual = 5.472491251450974e-11     
CG iteration 117, residual = 4.742309580107411e-11     
CG iteration 118, residual = 4.2965974901038526e-11     
CG iteration 119, residual = 3.949720276531568e-11     
CG iteration 120, residual = 3.616719395719608e-11     
CG iteration 121, residual = 3.1997168193489106e-11     
CG iteration 122, residual = 2.6860730446968504e-11     
CG iteration 123, residual = 2.166221985749301e-11     
CG iteration 124, residual = 1.694803338628977e-11     
CG iteration 125, residual = 1.2972114614928826e-11     
CG iteration 126, residual = 1.00226125923212e-11     
CG iteration 127, residual = 8.140618447154032e-12     
CG iteration 128, residual = 6.675420570084242e-12     
CG iteration 129, residual = 5.7539602161614326e-12     
CG iteration 130, residual = 5.254300738381873e-12     
CG iteration 131, residual = 5.0232966041056616e-12     
CG iteration 132, residual = 4.699131202271144e-12     
CG iteration 133, residual = 4.192023275694789e-12     
CG iteration 134, residual = 3.4460705922160184e-12     
CG iteration 135, residual = 2.618149869903044e-12     
CG iteration 136, residual = 1.9001908253773825e-12     
CG iteration 137, residual = 1.3674105735366592e-12     
CG iteration 138, residual = 9.948991175617615e-13     
CG iteration 139, residual = 7.754910546058193e-13     
CG iteration 140, residual = 6.747570689708641e-13     
CG iteration 141, residual = 6.421730292178154e-13     
CG iteration 142, residual = 6.335106091376755e-13     
CG iteration 143, residual = 5.863188253378522e-13     
CG iteration 144, residual = 5.113190058895784e-13     
CG iteration 145, residual = 4.1063638949259246e-13     
CG iteration 146, residual = 3.0889347534911434e-13     
CG iteration 147, residual = 2.2612072220532705e-13     
CG iteration 148, residual = 1.6986752064421176e-13     
CG iteration 149, residual = 1.3034475621761722e-13     
CG iteration 150, residual = 1.079069079212223e-13     
CG iteration 151, residual = 9.580591823496576e-14     
CG iteration 152, residual = 8.954049875989656e-14     
CG iteration 153, residual = 8.595700840575989e-14     
CG iteration 154, residual = 8.076337491786032e-14     
CG iteration 155, residual = 6.981455131698702e-14     
CG iteration 156, residual = 5.579468300749988e-14     
CG iteration 157, residual = 4.1962460649046894e-14     
CG converged in 157 iterations to residual 4.1962460649046894e-14
needed 0.046002864837646484 seconds for 23787 unknowns
Draw (gfu, **ea);