4. 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 (i.e. not linear in the number of degrees of freedom). 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
Draw(shape);
Generate a mesh, and perform uniform mesh refinement:
ngmesh = OCCGeometry(shape).GenerateMesh(maxh=0.1)
for l in range(1):
ngmesh.Refine()
mesh = Mesh(ngmesh)
mesh.Curve(3)
Draw (mesh);
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(v*dx)
# c = Preconditioner(a, "direct", inverse="sparsecholesky")
c = Preconditioner(a, "local")
# c = Preconditioner(a, "bddc")
gfu = GridFunction(fes)
we have 177430 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
with TaskManager():
inv = CGSolver(mat=a.mat, pre=c.mat, printrates='\r', maxiter=400)
gfu.vec.data = inv * f.vec
CG iteration 1, residual = 0.024273223974312075
CG iteration 2, residual = 0.037204475895342
CG iteration 3, residual = 0.04829608173279241
CG iteration 4, residual = 0.047831452027208586
CG iteration 5, residual = 0.03503614777663428
CG iteration 6, residual = 0.029378085186036483
CG iteration 7, residual = 0.031006371846374843
CG iteration 8, residual = 0.02881189922538989
CG iteration 9, residual = 0.026991393488043674
CG iteration 10, residual = 0.025607813233479115
CG iteration 11, residual = 0.023059227507159427
CG iteration 12, residual = 0.020188714252706304
CG iteration 13, residual = 0.017677856690926363
CG iteration 14, residual = 0.01570390414750895
CG iteration 15, residual = 0.01450892008875497
CG iteration 16, residual = 0.013060236654630365
CG iteration 17, residual = 0.01148717272069801
CG iteration 18, residual = 0.010359419640115403
CG iteration 19, residual = 0.009639280718573347
CG iteration 20, residual = 0.008983784519869005
CG iteration 21, residual = 0.008250496171208304
CG iteration 22, residual = 0.007352872683189109
CG iteration 23, residual = 0.0064397891421690305
CG iteration 24, residual = 0.005596514201958335
CG iteration 25, residual = 0.004766219873666417
CG iteration 26, residual = 0.004022073286663706
CG iteration 27, residual = 0.0034196513449910823
CG iteration 28, residual = 0.0029400048222059856
CG iteration 29, residual = 0.0025083332705242
CG iteration 30, residual = 0.0021046499274098534
CG iteration 31, residual = 0.0017484379251981065
CG iteration 32, residual = 0.0014397425850613988
CG iteration 33, residual = 0.0011912144262735045
CG iteration 34, residual = 0.0009893154642094026
CG iteration 35, residual = 0.0008329679456139172
CG iteration 36, residual = 0.0007272861126943784
CG iteration 37, residual = 0.0006352763333349191
CG iteration 38, residual = 0.0005645223644237875
CG iteration 39, residual = 0.0004942564003676569
CG iteration 40, residual = 0.00042780257753367363
CG iteration 41, residual = 0.00036683687047396396
CG iteration 42, residual = 0.0003112297948991817
CG iteration 43, residual = 0.00026555485540291635
CG iteration 44, residual = 0.00023057965122062087
CG iteration 45, residual = 0.00020810720521774676
CG iteration 46, residual = 0.00019208909401800605
CG iteration 47, residual = 0.00017853792896837772
CG iteration 48, residual = 0.00016491550344460967
CG iteration 49, residual = 0.0001498362645389152
CG iteration 50, residual = 0.0001338648614332045
CG iteration 51, residual = 0.00011598796595447701
CG iteration 52, residual = 9.959344694700465e-05
CG iteration 53, residual = 8.519641137784833e-05
CG iteration 54, residual = 7.322459830883026e-05
CG iteration 55, residual = 6.417417797477789e-05
CG iteration 56, residual = 5.699684507733734e-05
CG iteration 57, residual = 5.166607912750655e-05
CG iteration 58, residual = 4.7110717192708665e-05
CG iteration 59, residual = 4.3231615399420306e-05
CG iteration 60, residual = 3.9523838011088034e-05
CG iteration 61, residual = 3.5483623051359466e-05
CG iteration 62, residual = 3.115776481808797e-05
CG iteration 63, residual = 2.6858896178966197e-05
CG iteration 64, residual = 2.2452143271619613e-05
CG iteration 65, residual = 1.8667683822022966e-05
CG iteration 66, residual = 1.5676517902103517e-05
CG iteration 67, residual = 1.3491991701423895e-05
CG iteration 68, residual = 1.1932267987396277e-05
CG iteration 69, residual = 1.1006946297625608e-05
CG iteration 70, residual = 1.0456629339641523e-05
CG iteration 71, residual = 9.883740543600398e-06
CG iteration 72, residual = 9.186544775446272e-06
CG iteration 73, residual = 8.152829147699458e-06
CG iteration 74, residual = 6.959623023960013e-06
CG iteration 75, residual = 5.777798497624973e-06
CG iteration 76, residual = 4.775007175940237e-06
CG iteration 77, residual = 3.979591970780287e-06
CG iteration 78, residual = 3.3697656755438388e-06
CG iteration 79, residual = 2.931468204779986e-06
CG iteration 80, residual = 2.6063431809725343e-06
CG iteration 81, residual = 2.339109257479704e-06
CG iteration 82, residual = 2.1073268104192383e-06
CG iteration 83, residual = 1.8783881773434057e-06
CG iteration 84, residual = 1.6729157958379345e-06
CG iteration 85, residual = 1.477359372021876e-06
CG iteration 86, residual = 1.2787374496223366e-06
CG iteration 87, residual = 1.1065178148932502e-06
CG iteration 88, residual = 9.440247699033299e-07
CG iteration 89, residual = 8.070630129019807e-07
CG iteration 90, residual = 6.801601436853941e-07
CG iteration 91, residual = 5.689323984540329e-07
CG iteration 92, residual = 4.779751500223053e-07
CG iteration 93, residual = 4.0322338191445864e-07
CG iteration 94, residual = 3.443176683566252e-07
CG iteration 95, residual = 2.983673740203993e-07
CG iteration 96, residual = 2.64890769583779e-07
CG iteration 97, residual = 2.3834677872461816e-07
CG iteration 98, residual = 2.1324039739542678e-07
CG iteration 99, residual = 1.9014339920530615e-07
CG iteration 100, residual = 1.6878351817818138e-07
CG iteration 101, residual = 1.4807078864792983e-07
CG iteration 102, residual = 1.3005077941994067e-07
CG iteration 103, residual = 1.1410181950377555e-07
CG iteration 104, residual = 9.815400446992752e-08
CG iteration 105, residual = 8.263818148215092e-08
CG iteration 106, residual = 6.984159946931181e-08
CG iteration 107, residual = 5.908274034770534e-08
CG iteration 108, residual = 5.0612004296881115e-08
CG iteration 109, residual = 4.384548734703711e-08
CG iteration 110, residual = 3.851545498892002e-08
CG iteration 111, residual = 3.4359368486597825e-08
CG iteration 112, residual = 3.100139362740519e-08
CG iteration 113, residual = 2.8136342454941936e-08
CG iteration 114, residual = 2.5808008395922967e-08
CG iteration 115, residual = 2.3538480472957442e-08
CG iteration 116, residual = 2.138838983489785e-08
CG iteration 117, residual = 1.8834840815121618e-08
CG iteration 118, residual = 1.6357941765358154e-08
CG iteration 119, residual = 1.4032958225323066e-08
CG iteration 120, residual = 1.1973176149489421e-08
CG iteration 121, residual = 1.0330722476742483e-08
CG iteration 122, residual = 9.060421857389568e-09
CG iteration 123, residual = 8.010205668737527e-09
CG iteration 124, residual = 7.1550389688295956e-09
CG iteration 125, residual = 6.394917627264948e-09
CG iteration 126, residual = 5.746988905891274e-09
CG iteration 127, residual = 5.180098524265756e-09
CG iteration 128, residual = 4.6298437650060975e-09
CG iteration 129, residual = 4.151239212626374e-09
CG iteration 130, residual = 3.7171682211344884e-09
CG iteration 131, residual = 3.28636674165708e-09
CG iteration 132, residual = 2.875922769123227e-09
CG iteration 133, residual = 2.4976441070032594e-09
CG iteration 134, residual = 2.1695613375814276e-09
CG iteration 135, residual = 1.868479538952061e-09
CG iteration 136, residual = 1.6186157638062868e-09
CG iteration 137, residual = 1.3965604941420359e-09
CG iteration 138, residual = 1.230062807166462e-09
CG iteration 139, residual = 1.0837253706493335e-09
CG iteration 140, residual = 9.728766308288062e-10
CG iteration 141, residual = 8.732708184104283e-10
CG iteration 142, residual = 7.863948847061986e-10
CG iteration 143, residual = 6.947907556144233e-10
CG iteration 144, residual = 6.079255401192082e-10
CG iteration 145, residual = 5.246753131763292e-10
CG iteration 146, residual = 4.5036598509313203e-10
CG iteration 147, residual = 3.883349334841279e-10
CG iteration 148, residual = 3.346108176246629e-10
CG iteration 149, residual = 2.922398248092175e-10
CG iteration 150, residual = 2.5494201485235853e-10
CG iteration 151, residual = 2.2453548564298967e-10
CG iteration 152, residual = 1.9788107295271953e-10
CG iteration 153, residual = 1.7312763680539798e-10
CG iteration 154, residual = 1.5149410265326552e-10
CG iteration 155, residual = 1.3206146501632598e-10
CG iteration 156, residual = 1.1601092281831917e-10
CG iteration 157, residual = 1.0257310986172217e-10
CG iteration 158, residual = 9.035057863467162e-11
CG iteration 159, residual = 8.012900680539926e-11
CG iteration 160, residual = 7.053091225238836e-11
CG iteration 161, residual = 6.177975481974726e-11
CG iteration 162, residual = 5.4105955877807516e-11
CG iteration 163, residual = 4.6972458570229063e-11
CG iteration 164, residual = 4.059962390744391e-11
CG iteration 165, residual = 3.48344467893236e-11
CG iteration 166, residual = 2.962748743407555e-11
CG iteration 167, residual = 2.5116661890005876e-11
CG iteration 168, residual = 2.1313848999463623e-11
CG iteration 169, residual = 1.838939606568788e-11
CG iteration 170, residual = 1.5917993944175503e-11
CG iteration 171, residual = 1.3925445641690011e-11
CG iteration 172, residual = 1.222905569117103e-11
CG iteration 173, residual = 1.0798810040492257e-11
CG iteration 174, residual = 9.507026363501187e-12
CG iteration 175, residual = 8.35640106452074e-12
CG iteration 176, residual = 7.287100776090044e-12
CG iteration 177, residual = 6.446668911117099e-12
CG iteration 178, residual = 5.738961003585408e-12
CG iteration 179, residual = 4.955476591094188e-12
CG iteration 180, residual = 4.179276503633465e-12
CG iteration 181, residual = 3.51484360347095e-12
CG iteration 182, residual = 2.961192049799402e-12
CG iteration 183, residual = 2.506908218354334e-12
CG iteration 184, residual = 2.14706588838844e-12
CG iteration 185, residual = 1.8529520194379847e-12
CG iteration 186, residual = 1.5975760598785288e-12
CG iteration 187, residual = 1.3938574627111934e-12
CG iteration 188, residual = 1.2231484138440663e-12
CG iteration 189, residual = 1.0799504864837223e-12
CG iteration 190, residual = 9.576679382931486e-13
CG iteration 191, residual = 8.47711133461441e-13
CG iteration 192, residual = 7.410634905428783e-13
CG iteration 193, residual = 6.409720725027058e-13
CG iteration 194, residual = 5.482969009887021e-13
CG iteration 195, residual = 4.62576805756395e-13
CG iteration 196, residual = 3.8570338555821037e-13
CG iteration 197, residual = 3.2128164846413054e-13
CG iteration 198, residual = 2.7228777450440256e-13
CG iteration 199, residual = 2.363532192858452e-13
CG iteration 200, residual = 2.037214875409793e-13
CG iteration 201, residual = 1.743140248349613e-13
CG iteration 202, residual = 1.5116759654916236e-13
CG iteration 203, residual = 1.3371286004187721e-13
CG iteration 204, residual = 1.199662120862354e-13
CG iteration 205, residual = 1.0800838951175999e-13
CG iteration 206, residual = 9.724302716978304e-14
CG iteration 207, residual = 8.623330289029238e-14
CG iteration 208, residual = 7.573761126328625e-14
CG iteration 209, residual = 6.52514963956198e-14
CG iteration 210, residual = 5.550103983705584e-14
CG iteration 211, residual = 4.6103899203810424e-14
CG iteration 212, residual = 3.8099867233648296e-14
CG iteration 213, residual = 3.1789412583431215e-14
CG iteration 214, residual = 2.6741498611348335e-14
CG iteration 215, residual = 2.3329352056374313e-14
CG converged in 215 iterations to residual 2.3329352056374313e-14
Draw (gfu, draw_vol=False);
Exercise:
Experiment with differ problem sizes and preconditioners
How big systems can you solve on your computer (watch out for memory usage)