Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Optimal complexity — where it appears

The property of costing a fixed amount of work per unknown however large the problem is. It is what multigrid achieves on the model problem and what a hierarchical solver approaches, and it is a statement about a limit rather than about any size that is run.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

567891010⁴10⁵10⁶10⁷10⁸10⁹log₂ nmultiplicationsdense factorisation, n³⁄3the recursion, countedwhere the format starts payingratio at n = 641.5ratio at n = 5120.16exponent, first doubling2.1exponent, last doubling1.7backward error1.4·10⁻¹⁰cheaper is a sizenot a property

Where the format starts paying

A hierarchical solve costs 1.48 times a dense factorisation at 64 unknowns and 0.16 times it at 512. The crossover is between 64 and 128, it walks right when the accuracy is tightened, and the exponent between consecutive sizes is 2.13, 1.93, 1.74 — falling towards one and never arriving.

cost · hierarchical solve 10¹10¹.³10¹.⁶10¹.⁹⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰¹10².²00.250.50.751grid points nresidual reduction per stepJacobiGauss–SeidelV-cycleV-cycle spread, 8× in size0.003Jacobi at n = 1270.99work exponent, fitted0.079the dashed curve is cos(πh), Jacobi's closed formthe flat line is the whole method

A rate that does not notice the size

The V-cycle reduces the residual by a factor of ten a cycle at fifteen points and at a hundred and twenty-seven. Jacobi on the same four problems goes from 0.981 to 0.9978, climbing towards one. One of those is a constant and the other is an exponent, and that is the whole distinction the field turns on.

iterative · multigrid

Named alongside it

The objects these essays reach for when they reach for this one.

Asymptotic analysisBackward errorBlock methodsConvergence factorData movementFlop countHierarchical matrixJacobi iterationLU factorisationTriangular solveThe V-cycleWoodbury identity

All concepts