Every essay — page 12
Iterating, instead of factorising
At scale nobody factorises, and the reason is not accuracy — it is that the factors of a sparse matrix are not sparse. What replaces elimination is a sequence of approximations, and the question changes shape: not what the residual of the factorisation is, but how fast the error falls and whether the thing you can measure tracks the thing you cannot. On the model problem every rate is known in closed form before anything runs.
How much direction there was to lose
At 45° the nine-point stencil hands smoothed aggregation the same wrong hierarchy at every anisotropy — six strong neighbours per interior point, 121 aggregates, the identical partition from ε = 10⁻⁴ to 0.099.
The switch does not know which side is better
The strength threshold moves the coarsening from full to semi at θ = ε exactly, at every anisotropy.
A proof that does not ask how large the matrix is
Proving a Hessian indefinite costs three matrix–vector products when the negative eigenvalue is 3 and nine to eleven when it is a thousandth, and that pair of numbers barely moves across a fourfold range in n.
A walk needs a length
The gap between the two residuals grows as the square root of something, and a square root needs a length.
The answer that arrives when the space runs out
A second-order Krylov recurrence holds vectors of length n for a problem with 2n eigenvalues, so it is exact at n steps where the linearised route needs 2n.
The certificate that arrives soonest is worth least
The more negative a Hessian's smallest eigenvalue, the sooner conjugate gradients meets a direction of negative curvature — and the less of the exact trust-region decrease that direction turns out to be worth.
Sparsity, and what elimination costs
Eliminating a variable couples everything it touched to everything else it touched, and every one of those couplings is an entry that was zero in the matrix and is not zero in its factor. On the same matrix one elimination order gives a factor of a thousand entries and another gives ten thousand — the two factorisations equally accurate, one of them fitting in memory. Nothing numerical chooses between them.
The factor is not sparse
A sparse matrix has a factor that is not sparse, and the gap between them is the entire reason iterative methods exist.
The order decides the memory
Four elimination orderings on one matrix give factors of 1,739, 1,354, 1,413 and 1,026 entries.
Two ends of the same arrow
One matrix, one row moved from the front of the elimination order to the back, and the factor goes from completely dense to no fill at all.
Structure and stability stop being separable
The sparsest variable to eliminate on this matrix has a diagonal entry of 10⁻¹².
A threshold between fill and growth
One number decides how small a pivot an elimination will accept.
What the symbolic phase can only bound
Without pivoting, the fill can be computed from the graph and the count is exact — 233 predicted, 233 measured.
The order that was right last time
A pivot order computed once and reused across a sequence saves the symbolic phase, and the price is that a pivot which was large may now be small.
The fill that is not independent
Eliminate both halves of a grid and what is left on the separator is 100 per cent nonzero — the sparsity field's result, unchanged.
An ordering that does not wait for the numbers
A sparse factorisation's memory is decided by an ordering computed from the graph, and its stability by pivots computed from the values, and the two decisions fight.
The cliff behind the count
The fill's rank is an integer between three and six across every separator two dense half-eliminations can afford, and this field has already recorded that a handful of such integers cannot carry a law.
An ordering that buys processors, not time
Nested dissection loses to minimum degree on fill and on total work at every grid either measurement could draw.
The least fill there is
Finding the elimination order with the least fill is NP-hard, and that is a statement about the hardest graph and the largest size.
Two minima that are one minimum
The order that decides the memory found the operation count behaving like the square of the fill, which leaves room for an order with slightly more fill but a shorter heaviest column to do less arithmetic.
The depth that is worse than both ends
Nested dissection to a chosen depth and minimum degree below it is the ordering codes ship, and sweeping the depth was supposed to find a setting that keeps most of dissection's parallelism for most of minimum degree's work.
The column that was never fixed
Every threshold-pivoting measurement so far chose the pivot row in a fixed column, and the routine's own description said that choosing the column as well would change the constants and not the argument.
How few columns the search needs
A full row-and-column pivot search is quadratic in the active submatrix at every step, and no library performs one.
The freedom a symmetric factorisation does not have
Permuting rows and columns together leaves no column to choose, so the conflict between the sparsest pivot and the sound one should be worse rather than better.
The halves were the price
One level of nested dissection followed by minimum degree was worse than both no dissection and full dissection on a grid, and the explanation offered was the separator's dense block sitting on every path.