Four orders of conditioning, and four steps

A block Toeplitz matrix with Toeplitz blocks, assembled from the separable kernel ρ^(|k₁|+|k₂|) on a 10×10 grid, has a condition number of 62.2 at ρ = 0.5 and 818,561 at ρ = 0.98. That is a factor of thirteen thousand, and almost everything a reader is normally handed about such a problem is a function of it: how many digits the answer is entitled to, how far a residual can be trusted as a proxy for an error, and — through the square root that governs conjugate gradients — how many iterations to provision for.

Preconditioned by the averaged circulant, those same seven matrices take 18, 21, 21, 22, 21, 19 and 18 steps.

That column is not a smoothed reading of the first one. It is not a slowly growing function of it. It rises by four across a thirteen-thousandfold climb in conditioning and then comes back down, ending one step below where it started, on the hardest matrix of the seven. Something decides what the solver pays, and the condition number is not it.

The essay that measured the thinning drew this preconditioner’s spectrum at a single correlation and read the climbing step count as the two-dimensional clustering theorem arriving on schedule: all but O(mx + my) eigenvalues near one, which is a growing count where one dimension had a bounded one. That reading is right, and it is a statement about the grid. What a single correlation cannot show is that the count of eigenvalues the preconditioner brings near one — and therefore the count it leaves outside, which is the rest — is the same integer at every correlation the figure will draw.

The count is the same integer at every correlation #

The measurement is one sweep. Assemble the matrix and its averaged circulant at each correlation, form the preconditioned operator, take its whole spectrum by a dense symmetric eigensolve, and count how many eigenvalues sit within half a unit of one on each of the four grids:

Not approximately the same. The same integers, at correlations whose condition numbers differ by a factor of a hundred and forty within this table alone. A quantity that is supposed to count how much work the preconditioner has left undone is deaf to the only parameter the kernel has.

It is worth being exact about what the band is counting, because the two-dimensional clustering statement is easy to read backwards. Its claim is that all but O(mx + my) of the preconditioned eigenvalues fall into a shrinking neighbourhood of one, which at n = m² makes the count outside grow like the area and the count inside a vanishing share of it. At the grids a dense eigensolve can reach, none of that has happened yet: the tighter window the one-dimensional essays use — a tenth of a unit — holds five eigenvalues on the 4×4 grid and none on the other three, and half a unit either side of one is simply the widest window that still leaves most of the spectrum outside it. So the table above counts the eigenvalues the preconditioner has succeeded in bringing near one. The rest are what the solver still has to work through, and one number settles both.

The picture is worth comparing against the one above it before reading further, because nothing about it is unchanged. The spectrum is stretched: the top eigenvalue has gone from 13.2 to 20.3, the bottom from 0.2855 to 0.2565, and the ratio between them from 46 to 79. Every dot has moved. The number of them inside the shaded band has not.

The two-dimensional operator is the one-dimensional one squared, exactly #

The reason is available in closed form, and it is stronger than an explanation of the invariance — it predicts the count.

The kernel is separable by construction, chosen so that the two-dimensional problem is the one-dimensional problem twice and any difference between them is a property of the dimension. The consequence nobody drew out is that the separability survives the preconditioner. Averaging the competing diagonals in each index in turn, on a kernel that factorises, produces a first column that factorises: the two-dimensional circulant’s entries are the products of the one-dimensional circulant’s. So A is T ⊗ T and C is C₁ ⊗ C₁, and since a Kronecker product of inverses is the inverse of the Kronecker product,

C⁻¹A  =  (C₁⁻¹T)  ⊗  (C₁⁻¹T)

with C₁⁻¹T the one-dimensional preconditioned operator of the same side length m, not of the same number of unknowns. The spectrum of a Kronecker product is the set of pairwise products of the spectra, so the m² eigenvalues drawn in every figure above are the m² products of a list of m numbers. That is the same structure a Kronecker sum’s eigenvectors give a d-dimensional solve, and the same one that makes an index that is a pair a matrix nobody should assemble.

Stated, that is a claim about formulae. Checked, it is a claim about the matrices: the outer product of the ten-point one-dimensional spectrum against the hundred eigenvalues the dense eigensolve returns for the 10×10 grid, matched in sorted order, agrees to 3.5·10⁻¹³ relative at ρ = 0.9, and across twenty grid-and-correlation pairs the worst disagreement anywhere is 1.3·10⁻¹⁰. The two routes share no arithmetic: one is a hundred-by-hundred symmetric eigensolve of an assembled operator, the other multiplies ten numbers by ten numbers.

Here is the list of ten, at ρ = 0.9:

0.5186  0.6185  0.6186  0.6188  0.6194  0.6203  0.6229  0.6282  1.0845  4.0502

Eight values in a tight bunch below two thirds, one just above one, and one large. That shape is what the count reads, and the arithmetic of which products land in the band is short enough to do by hand. The bunch times itself reaches at most 0.6282² = 0.3947, which is below the band. The bunch times 1.0845 runs from 0.5625 to 0.6813, all inside, and there are eight of them counted in each order: sixteen. The middle value squared is 1.1762, inside: one more. The bunch times 4.0502 starts at 2.1006, outside. Sixteen and one is seventeen, which is what the figure prints for the 10×10 grid, and 2(m − 2) + 1 is 2m − 3.

Unit steps are what make the formula legible: 13, 15, 17, 19, 21 at m = 8, 9, 10, 11, 12 is exactly 2m − 3, and the count rises by precisely two for each extra line of the grid. The cluster count is not an asymptotic statement being approached. It is an integer, and it is the size of the one-dimensional spectrum’s low bunch counted twice plus one. What conjugate gradients pays for is m² − 2m + 3, the count outside, and that is a function of the grid side alone for the same reason.

Seventeen inside the band on the 10×10 grid against 21 preconditioned steps is worth reading against the rule that each eigenvalue away from a cluster costs about one step, because the two numbers do not line up the way that rule would put them. Sixteen of the seventeen sit between 0.5625 and 0.6813 — a bunch a tenth of a unit wide — and the seventeenth is alone at 1.1762. A polynomial small on a tight bunch spends one root on the bunch rather than one on each of its members, so the obstructions here are grouped rather than counted, and at ρ = 0.98 the same seventeen are met in 18 steps rather than 21. That is the difference between a count of eigenvalues and a count of things the method has to spend a root on, and it is why the arithmetic above predicts which integer appears on the figure and not which integer appears in the solver.

Where the formula begins, and it is not at the first grid drawn #

The four grids in the opening figure read 9, 11, 13, 17, and 2m − 3 at m = 4, 6, 8, 10 would be 5, 9, 13, 17. The two agree on the larger half and not on the smaller, and the same arithmetic says why.

At m = 4 and ρ = 0.9 the one-dimensional spectrum is 0.5269, 0.5516, 1.0231, 1.8984. Its largest entry is only 1.90, so the bunch multiplied by it gives 1.0003 and 1.0472 — both inside the band, four more ordered pairs, and 5 + 4 = 9. At m = 6 the largest has grown to 2.70 and only the smallest of the bunch still reaches the band with it, giving 9 + 2 = 11. By m = 7 the top eigenvalue is far enough out that no product involving it lands inside, and from there the count is 2m − 3 at every grid: 11, 13, 15, 17, 19, 21 at m = 7 through 12.

Predicting the count from ten numbers and then measuring it from a hundred is a check worth running in bulk rather than at one point. Over 54 combinations — six correlations from 0.84 to 0.98 and nine grid sides from 4 to 12 — the count predicted by multiplying out the one-dimensional list and the count measured from the dense two-dimensional eigensolve agree in all 54 cases, including the twenty-two where the answer is not 2m − 3.

Below ρ = 0.825 the figure refuses, and the refusal is the same fact from the other end #

The generator refuses a correlation of 0.825 or below. It asserts that the cluster grows like the side of the grid rather than like its area — the count inside the band must stay under 3m — and at ρ = 0.825 the 10×10 grid puts 31 eigenvalues there against the 30 the assertion allows. At ρ = 0.82 it is 33, at ρ = 0.8 it is 66, and at ρ = 0.5 it is 82 of a hundred.

That refusal is not a limitation to be worked around by widening the bound. It is the same product structure reporting from the other side, and there is a second, sharper threshold above it that belongs to the same mechanism. The bunch of m − 2 low eigenvalues rises towards one as the correlation weakens: 0.6282 at ρ = 0.9, 0.7042 at ρ = 0.84, 0.7103 at ρ = 0.835. A product of two of them enters the band when it reaches ½, so the count leaves 2m − 3 at the moment the largest of the bunch crosses 1/√2 = 0.70711 — and it does, to the third decimal. At ρ = 0.84 the largest is 0.7042, its square is 0.4959, and the 10×10 count is 17. At ρ = 0.835 the largest is 0.7103, its square is 0.5045, one ordered pair has moved inside, and the count is 18. At ρ = 0.83 it is 20.

Between 0.83 and 0.825 the products arrive faster than the count can absorb them and the assertion gives way. What has happened by then is that the band has stopped separating a cluster from the rest and started containing the whole spectrum: at a gentle decay the preconditioned eigenvalues are packed tightly enough to sit inside a fixed absolute window, so a figure that kept drawing would show a cluster growing spectacularly and would be counting a different thing. The refusal is the instrument declining to report a number it can no longer interpret, which is what an assertion on a figure is for.

The conditioning moves by thirteen thousand and the preconditioned conditioning by thirteen #

The condition number is not merely uninformative about the step count. Its own behaviour, measured across the same sweep, is the clearest statement of how completely the preconditioner removes the correlation and how completely it leaves the grid behind.

The matrix’s condition number moves by a factor of 13,160 and the preconditioned one by a factor of 12.8. Three orders of magnitude separate the two ranges, and it is the second that the step count is entitled to be a function of — through the square root, √12.8 is 3.6, which is the right order for a column that moves by four steps.

Both columns are squares, and that is the whole of the difference between them. On ten points the one-dimensional matrix has κ = 135.4866 at ρ = 0.9 and the 10×10 grid has 18,356.63, which is its square to 2·10⁻¹³ relative; the one-dimensional preconditioned operator has κ = 7.8092 and the two-dimensional one has 60.983, which is its square to 2·10⁻¹⁴. The product structure squares whatever it is handed, indifferently. What the preconditioner decides is which number gets squared, and squaring 7.81 is a different event from squaring 135.5. That is a sharper account of what this preconditioner buys than any ratio of step counts, and it says what would happen on a third axis: the same construction would cube both, so the quantity worth making small is the one-dimensional preconditioned condition number rather than the two-dimensional one that gets quoted.

The unpreconditioned column is the control that says the measurement can see difficulty when there is some: 43 to 178 across the same seven matrices, a factor of 4.1, climbing at every correlation. It is also far below the factor of 114 the square root of κ allows, which is the ordinary looseness the rate the condition number predicts prices. The instrument works. It is the preconditioned column that has stopped depending on the correlation, and the reason is that the averaged circulant is built from the same kernel: whatever the correlation makes hard, the preconditioner already knows.

The two-dimensional limit is the fourth power rather than the second — the symbol is a product of two one-dimensional symbols and the range of a product is the product of the ranges — so the limit the matrix never reaches is reached even less well here than in one dimension, and how badly is itself a function of the correlation.

Those two shares, 76.7% and 14.1%, are worth keeping beside the step counts. At ρ = 0.5 the finite grid is three quarters of the way to its asymptotic conditioning; at ρ = 0.9 it is a seventh of the way. A reader provisioning from the closed-form limit would be wrong by a factor of 1.3 at one end of this sweep and by a factor of 7 at the other, and would be wrong about a quantity that decides nothing anyway — which is the trap the number that decides nothing sets with the determinant and a condition number scaling cannot move sets with the normwise κ.

The bottom of the preconditioned spectrum is a half raised to the dimension #

One quantity in this sweep does have a clean form, and the product structure hands it over.

The smallest eigenvalue of the one-dimensional preconditioned operator on ten points reads 0.6797, 0.5918, 0.5522, 0.5343, 0.5186, 0.5065, 0.5017 and 0.5007 at ρ = 0.5, 0.7, 0.8, 0.85, 0.9, 0.95, 0.98 and 0.99. It settles on ½. The two-dimensional smallest, on the 10×10 grid at the same correlations, reads 0.4621, 0.3502, 0.3049, 0.2855, 0.2690, 0.2565, 0.2517 and 0.2507 — and every one of those is the square of the number above it, to every digit printed, because the smallest product of a list with itself is the smallest entry squared.

So λ_min(C⁻¹A) tends to 2⁻ᵈ, and the second dimension does not degrade the bottom of the spectrum gradually: it halves it, once, for being a second dimension. At matched unknown counts rather than matched sides the reading is the same — 64 unknowns in one dimension give 0.4878 at ρ = 0.98 and the 8×8 grid gives 0.2529, a ratio of 0.5185.

The d in that expression is an extrapolation from two points and the site has no three-dimensional assembler to test it on, so it is offered as what the product structure predicts rather than as something measured. What is measured is that a bound of ½ becomes a bound of ¼, and that the whole of the difference is one multiplication.

What follows for anything that uses this preconditioner #

A step count sold as size-independent is size-dependent here, and correlation-independent. The first half is the earlier essay’s finding and stands. The second is the addition: the parameter that makes the problem hard is the one parameter the solver does not notice, which is the strongest available statement that the preconditioner works.

Provisioning iterations from κ is worse than useless here. It is not merely loose in the way every conjugate gradient bound is loose; it is loose in a direction that reverses. Between ρ = 0.85 and ρ = 0.98 the condition number grows by 140 times and the measured step count falls, from 22 to 18. A budget derived from κ would grow monotonically across a range on which the truth is not monotone at all.

What a genuinely size-independent count looks like is elsewhere in this collection. The flat 7, 8, 9, 10, 10 of the circulant that cannot be indefinite across a factor of sixteen in size is one, and the multigrid field’s rate that does not notice the size is the other. The count measured here is neither: it is flat in the correlation and logarithmic in the side.

And the mechanism is a warning about separable test problems. Everything above holds because the kernel factorises, which is what makes the two-dimensional operator the one-dimensional one squared and hands over the spectrum for free. That is a property of the family chosen so the comparison would be honest, and it is also the property doing all the work. A non-factorising kernel — the same distinction the kernel with nothing to compress turns on, and the one the coarse problem is a different problem found when a one-dimensional identity met a second axis — has no such spectrum, and every closed form above becomes a measurement.

What this essay is not entitled to say #

The grids stop at 12. The step counts alone would run much further, since a preconditioned conjugate gradient step is a dense matrix–vector product and a transform. The spectrum is what limits the figures: at 12×12 the eigensolve is a 144×144 problem and the preconditioner has to be applied to 144 unit vectors to form the similarity. Whether 2m − 3 survives to m = 40 is a claim these measurements do not support, though the one-dimensional list that produces it is cheap at any size.

The band is a choice. Half a unit either side of one is the window at which the count is legible; asked about a tenth of a unit the count at ρ = 0.85 is 5, 0, 0, 0 across the four grids, and the cluster is empty at the three larger ones. Both windows were reported when the figure was first drawn and both are reported here, because a figure drawn only at the tight band would suggest the preconditioner had failed and one drawn only at the wide band would suggest it was fine.

And 2m − 3 is a fact about this family, not a theorem. It is derived from the measured shape of a one-dimensional spectrum — m − 2 low values, one just above one, one large — and that shape is the Kac–Murdock–Szegő family’s, checked at six correlations and nine sizes. What generalises is the product structure, which holds for any separable kernel; what the count would be for a different low bunch is a different arithmetic on a different list of m numbers, and it would be run rather than assumed.