Every essay — page 13
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.
An order fixed before the numbers
On a saddle-point matrix whose constraint rows have no diagonal, taking the sparsest pivot at every step beat the natural order on fill and growth at once, and the reading was deferral: the constraint rows go last and have filled in by then.
Pieces ordered blind
One level of nested dissection followed by minimum degree lengthened the factorisation's critical path, and the blame moved from the separator to the halves: minimum degree's path through a 12 × 24 half was longer than through the whole 24 × 24 grid.
A plan redrawn where it was refused
A symmetric indefinite factorisation planned once from the pattern loses its fill saving as small pivots are scattered through the diagonal — on an 8 × 8 grid it keeps 74 per cent of what re-reading the degrees at every step saves at one small pivot in twenty, and 20 per cent at three in ten.
A small pivot with a small neighbour
A fill-reducing plan computed from the pattern loses its saving as small pivots are scattered through a symmetric indefinite matrix, and redrawing it where the pivoting test refuses it wins the saving back.
A refusal has no fixed price
A symmetric indefinite factorisation planned once from the pattern is refused by its pivoting test where small diagonal entries sit, and the earlier essays read the refusal count as the plan's cost: scattered small pivots were refused 7 to 19 times and saved little, clustered ones 0 to 6 and saved much more.
The baseline was the interchanges
Small pivots along grid rows gave a fixed fill-reducing plan twice the saving over the natural order that scattered ones did, for a factor of the same size, and the reading was that the natural order did badly on rows.
A clique has no order
Ordering a dissection's pieces with their separator in view cut the critical path by a quarter, and the next proposal was to order the separator's own vertices by how much fill each carries in.
Structure, and the solver that cannot see it
The sparsity field is about a matrix most of whose entries are zero. This is the other way a matrix can be small: a circulant is n numbers and a Toeplitz matrix is 2n − 1, and neither of them has a single zero entry, so nothing in the sparsity field applies. What the structure buys is an exact spectrum, a condition number in closed form and a solve in n log n — and what it does not buy is a well-conditioned problem, which is the half that gets summarised away.
The matrix that is one row
A circulant of size 16 is sixteen numbers, has no zero entry anywhere, and hands over its entire spectrum in closed form — the discrete Fourier transform of its first column, exactly.
A limit the matrix never reaches
Szegő's theorem gives a Toeplitz family's condition number in closed form — ((1+ρ)/(1−ρ))², which is 81 at ρ = 0.8.
A preconditioner that changes sign
Strang's circulant preconditioner takes Toeplitz conjugate gradients from 179 steps to 10 at n = 256.
The circulant that cannot be indefinite
The previous essay found a preconditioner taking 117 steps against an unpreconditioned 59, because its smallest eigenvalue was −0.173.
Two dimensions, and the cluster that thins
The same kernel, the same averaging, the same transform — applied along two axes instead of one.
An equation whose unknown is a matrix
AX + XB = C is linear in X, so it has a coefficient matrix, and writing it down is the obvious thing to do.
A nearby problem of the wrong kind
A good algorithm returns the exact answer to a nearby problem.
The condition number of the model
Describe a 40×40 Toeplitz matrix by its 1,600 entries and its condition number is 78,800.
A perturbation that keeps the symmetry
The smallest perturbation that makes a computed answer exact is the backward error.
A speedup with a ceiling of its own
At ρ = 0.5 the averaged circulant takes 5 conjugate gradient steps at n = 512 against an unpreconditioned 30 — and that 30 is where the unpreconditioned count stops.
Four orders of conditioning, and four steps
On a 10×10 grid the two-dimensional kernel's condition number runs from 62 at ρ = 0.5 to 818,561 at ρ = 0.98.
The elimination the matrix does not need
The Kronecker form of AX + XB = C is dismissed with a hundred million entries and (2/3)n⁶ operations.
The number that cannot rank them
Levinson and Gaussian elimination are indistinguishable on the backward error a library reports — every one of ninety-six measurements between 1.16·10⁻¹⁷ and 5.73·10⁻¹⁷.
The circulant the problem did not contain
A matrix that differs from a circulant in two corner entries can be solved through the circulant, by a transform and a two-by-two correction, and the cost claim is exact.
Two near-zeros cost less than one
Solve a well-conditioned tridiagonal matrix through a nearly singular wrap and the correction's accuracy is not set by how singular the wrap is.
The correction lost to its own two-by-two solve
Solving a band matrix through a circulant and a small correction was measured losing the answer to 10⁻⁴ where elimination kept it to 10⁻¹⁴, and a wrap that landed one sample on a zero was measured costing four orders more than one that landed a pair.
A zero no twist can step around
Solved through its circulant wrap with the small capacitance system factorised stably, a banded matrix was found to lose only what the cancellation in the correction costs, and a twist of half a step kept that cancellation near one.