Every essay — page 14
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.
One step past the zero
The squared Laplacian, solved through its twisted circulant and a rank-four correction, lost 6 to 34 times more accuracy than elimination, because its symbol's fourth-order zero keeps the wrap as ill conditioned as the matrix whatever the twist.
The staircase a separable kernel builds
A block-circulant preconditioner took 18, 21, 22, 21, 19 and 18 steps on a 10 × 10 Toeplitz-block-Toeplitz system as the correlation rose from 0.5 to 0.98 and the unpreconditioned count rose from 43 to 178 — the parameter that makes the problem hard was the one the solver did not notice.
Where one step stops being enough
One step of iterative refinement took the squared Laplacian's circulant-wrap solve to elimination's accuracy at every size, and the account was that each step multiplies the error by the wrap's condition number times the rounding, so one step suffices while that product is small.
The symbol that builds the staircase
A block-circulant preconditioner left the isotropic kernel's spectrum a ramp of thirty-eight clusters where the separable kernel's was a staircase of ten, and the proposal was a circulant sampled from the isotropic kernel's own symbol, to gather the ramp into treads of its own.
Six steps were six eigenvalues
A circulant sampled from a separable kernel's symbol held conjugate gradients at eight steps on every grid, because the preconditioned spectrum was six values.
A backward error the answer does not feel
Both ways of solving AX + XB = C leave a residual at the rounding level, and for a linear system that would be backward stability.
The residual knew the error
A Sylvester solve's structured backward error climbed by a factor of 26,000 while its forward error did not move, and the reading was that the condition number belonging to those structured perturbations must fall by the same factor.
The part a circulant can cancel
A separable kernel with a small isotropic part was preconditioned by the circulant sampled from the whole mixture's symbol.
Neither sparse nor dense
There is a third answer to a matrix that is too large, and it is the only one whose cost you choose. Sparsity is handed over by the problem — an entry is zero or it is not — and an operator with no entries is handed over by the code. A kernel matrix has no zero entries, is described by no fewer numbers than it contains, and is cheap anyway, because the block between two clusters of points that are far apart is numerically low rank. Where you cut its singular values is a decision, so the storage is a function of the accuracy asked for rather than of the matrix; and the accuracy turns out not to be an accuracy at all, but a backward error chosen at the top of the program.
A block nobody can call sparse
A 96 × 96 block of a kernel matrix has ninety-six nonzero singular values and five that matter.
A rank that is a number of digits
Ask a kernel block for two digits and it costs two columns; ask for fourteen and it costs nine.
The size the rank does not notice
Sample a kernel block at 32, 64, 128 and 256 points a side and it needs five columns, five, five and five.
The kernel with nothing to compress
Hold the geometry fixed at q = ½, fix the wavelength, and scale the picture up by sixteen.
Which pairs are allowed to be small
A hierarchical representation is a partition of the matrix into blocks, and the rule that produces it reads four numbers per pair of index clusters and not one entry of the matrix.
The test that costs what it saves
The partition that refuses to compress a touching pair keeps every rank at five while the other lets them climb from nine to thirteen.
The same matrix, numbered twice
One symmetric permutation. The condition number is 24.3948 either way to eight digits and the Frobenius norm is 6.13996414·10³ either way to twelve.
The accuracy worth paying for
Used as a preconditioner, a hierarchical representation gets better at every accuracy — the iteration count falls monotonically all the way to the tightest tolerance.
The rounding that was not the problem
A rank-k block plus a rank-k block is a rank-2k block, exactly, so every arithmetic in this format truncates after every addition.
A knob calibrated in residuals
A formatted Cholesky has two numbers in it and only one of them is an accuracy.
The count that is not the budget
A Cholesky performed inside a low-rank format truncates 0, 2, 10, 34 and 98 times as the leaf falls from 128 to 8, and those five integers are the same at every accuracy from 10⁻¹² to 10⁻².
The knob that moved two things
Decide how many digits the answer needs, divide by the condition number, and compress to that.
The offset that moved the slope
The accuracy is supposed to lift a storage curve and leave its growth alone.
The partition that does not move
The storage curve's growth rate more than triples between two digits and twelve, and the earlier measurement said so without saying what moves it.
Two knobs on one number
The tolerance raises every block's rank and leaves the partition alone.
A second objective that is the first one doubled
Counting the operations a hierarchical product does was supposed to give the leaf size a second optimum, somewhere other than where the storage puts it.