Six steps were six eigenvalues

The symbol that builds the staircase preconditioned a Toeplitz-block-Toeplitz system by a circulant sampled from the kernel’s own two-dimensional symbol, and found it doing something specific to one kernel. On the separable kernel $\rho^{|k_1|+|k_2|}$ the preconditioned spectrum collapsed to six values — sixty-four of a hundred eigenvalues at exactly one — and conjugate gradients took eight steps on every grid from 6 to 16 points a side, because the preconditioned operator was a Kronecker product of two one-dimensional ones, each the identity plus rank two. On the isotropic kernel $\rho^{\sqrt{k_1^2+k_2^2}}$ it left a ramp, and the step count grew with the grid.

The essay asked what lies between. “Add to the separable kernel a fraction ε of the isotropic one. … The prediction with a sign is that the six treads broaden into six clusters whose width grows with ε, that the step count stays near eight while those clusters stay under the one-per-cent threshold, and that it then climbs towards the isotropic count — so that the knife edge of the earlier essay, measured in ε rather than in p, has a width that can be read off before the solve.”

The figure at the top is the step count against ε on three grids, and the knife edge is not where the prediction put it. It is at the far left. A millionth of the isotropic kernel takes eight steps to eleven on every grid; a ten-thousandth takes them to thirteen and fifteen. The clusters, measured at one per cent, have not moved.

The mixture #

The kernel is $(1-\varepsilon)\,\rho^{|k_1|+|k_2|} + \varepsilon\,\rho^{\sqrt{k_1^2+k_2^2}}$ at $\rho = 0.9$, so that its value at the origin stays one: ε = 0 is the separable kernel the earlier essay measured, ε = 1 the isotropic one, and the eight values between run from a millionth to three tenths. The preconditioner is the symbol circulant of the mixed kernel, which is the same thing as $(1-\varepsilon)$ times the separable kernel’s symbol circulant plus ε times the isotropic one’s, since sampling a symbol is linear in the kernel. Conjugate gradients runs from zero to a relative residual of $10^{-10}$, as before, and also to $10^{-8}$, $10^{-6}$ and $10^{-4}$. The preconditioned spectrum is computed in full on the 10 × 10 grid.

Without the isotropic part the spectrum is six numbers: one eigenvalue at 0.1175, sixteen at 0.3428, sixty-four at exactly 1, two at 2.2327, sixteen at 6.5132 and one at 42.42, a condition number of 361. Those are the six treads.

Where the six levels come from #

The six values are not arbitrary, and knowing what they are says which of them can move. The symbol circulant preconditions each axis of the separable kernel by its own one-dimensional symbol circulant, and in one dimension the preconditioned operator is the identity plus a correction of rank two: eight of its ten eigenvalues on the 10 × 10 grid are exactly one, and the other two are $a = 0.3428$ and $b = 6.5132$. The two-dimensional operator is the Kronecker product of two copies, so its eigenvalues are every product of one value from each: $1 \cdot 1$ sixty-four times, $a \cdot 1$ and $1 \cdot a$ sixteen times between them, $b$ likewise, $ab = 2.2327$ twice, and $a^2 = 0.1175$ and $b^2 = 42.42$ once each. Sixty-four plus sixteen plus sixteen plus two plus one plus one is a hundred.

The isotropic part breaks the product structure, because $\rho^{\sqrt{k_1^2+k_2^2}}$ does not factor into a function of $k_1$ times a function of $k_2$. What the measurements show is which products the break disturbs. The three large treads — the products of a one-dimensional outlier with a one, and the ones with each other — widen. The pair at $ab$ stays a pair — its two eigenvalues agree to the thirteenth digit at every ε measured to three tenths — and the corners $a^2$ and $b^2$ are single eigenvalues, which can move but cannot widen. The large treads are the ones whose eigenvectors span many directions at the same eigenvalue, and a perturbation chooses among them; a single eigenvalue or a pair has no such freedom to spend. An eigenvalue that arrives twice found Lanczos returning copies of eigenvalues it had already found; here the opposite happens, sixty-four copies of one value becoming sixty-four values, and the Krylov method has to pay for each distinction.

The clusters do not see it #

The one-per-cent rule the earlier essays counted clusters by — consecutive eigenvalues within one per cent of each other belong together — reports six clusters at every ε up to $10^{-3}$, nine at $10^{-2}$, then 11, 17, 19 and the isotropic kernel’s 30. By that measure a thousandth of isotropy changes nothing.

Counted to twelve digits instead, the spectrum is a different object as soon as ε is positive. At ε = 0 the computed eigenvalues fall into 35 distinct values — the six treads, with the rounding in the eigenvalue computation splitting the larger ones — and from a millionth on they fall into 73 to 83. Each tread of sixteen or sixty-four equal eigenvalues has become sixteen or sixty-four nearly equal ones, spread over a relative width the one-per-cent rule cannot see and conjugate gradients can.

Why the count moves #

Conjugate gradients on a matrix with $d$ distinct eigenvalues terminates in $d$ steps in exact arithmetic: the residual polynomial it builds can put a root on each, and then it is zero. With six distinct preconditioned eigenvalues the method is done after six steps whatever the condition number, and that is what the separable kernel’s count was — six steps on the 10 × 10 grid at tolerances of $10^{-4}$, $10^{-6}$ and $10^{-8}$, and eight at $10^{-10}$, where rounding in the iteration itself costs two more. Four orders of conditioning, and four steps had already seen the count ignore the condition number; here the reason is exact.

When a tread splits into many eigenvalues spread over a width δ, one root can no longer zero them all. The polynomial has to be small across the whole interval, and the cheapest way to make a polynomial small on a narrow interval is a Chebyshev polynomial, which reduces it by about a factor of δ/4 per degree. Reducing the residual on that tread from one to the tolerance therefore costs about $\log(\mathrm{tol}/2)/\log(\delta/4)$ steps instead of one. At δ = $10^{-4}$ and a tolerance of $10^{-10}$ that is about two steps; at δ = $10^{-2}$, about four. A tread costs one step only while it is a single number.

So the cost of a little isotropy is not about whether the clusters stay under one per cent. It is about how many decades the solve must reduce the residual, against how narrow each tread still is.

The widths, and what they predict #

Three treads widen. The sixteen eigenvalues at 6.51 are the widest, $7.0\cdot 10^{-6}$ at a millionth of isotropy and $7.0\cdot 10^{-4}$ at a ten-thousandth; the sixty-four at one are a quarter of that, and the sixteen at 0.34 a thirtieth. The two eigenvalues at 2.23 and the two single ones do not widen at all. Each width grows in exact proportion to ε while ε is small — a factor of ten in ε moves each by a factor of ten — which is what a first-order perturbation of six exact levels should do. The widest tread reaches one per cent at about $1.5\cdot 10^{-3}$, the tread at one at about $6\cdot 10^{-3}$, the narrowest between five hundredths and a tenth: that is where the cluster count begins to rise, and it is far to the right of where the step count did.

Summing the Chebyshev estimate over the six treads — one step for each tread that is still a single value, $\log(\mathrm{tol}/2)/\log(\delta/4)$ for each that has a width — gives 9, 10, 11, 14 and 18 steps at ε from a millionth to a hundredth, against 11, 12, 13, 18 and 22 measured. The sum is low by two to four steps everywhere, which is the two steps rounding already cost the separable kernel plus the price of resolving six intervals with one polynomial rather than six. It tracks the climb’s shape across four decades of ε.

That is the sense in which the prediction’s last clause holds. The width of the knife edge can be read off before the solve — not from the cluster count, but from the treads’ widths, which grow linearly in ε and can be had from a first-order perturbation, and from the tolerance, which the caller chose.

What rounding already cost #

The separable kernel’s count at $10^{-10}$ is eight, not six, and the two extra steps are worth understanding because they are the same phenomenon at the smallest scale. In floating point the six levels are not exactly six. The eigenvalue computation here finds the treads split at widths of $10^{-13}$ to $10^{-10}$, part of which is that routine’s own rounding and part the operator’s; either way the operator conjugate gradients iterates with is six tight bunches rather than six points. A width of $10^{-10}$ against a tolerance of $10^{-10}$ costs about a step by the Chebyshev estimate; against $10^{-8}$ it costs nothing, which is why the count there is the exact six. Conjugate gradients’ finite termination is a property of exact arithmetic, and one eigenvalue and two steps found the same gap in GMRES: an operator whose every eigenvalue is one, which a Krylov method should finish in one step, needs two because the computed operator is not the exact one.

So the separable kernel’s eight was already a count paid partly for widths, and an isotropic fraction of a millionth only makes the widths larger than rounding’s. The jump from eight to eleven is the point at which the treads’ widths stop being set by the arithmetic and start being set by the kernel.

The tolerance is the knife edge #

The Chebyshev estimate says the tolerance should decide how much a given width costs, and the dial shows it does. At $10^{-4}$ the separable kernel takes six steps, a millionth of isotropy seven, a ten-thousandth eight: two steps for ε up to $10^{-4}$. At $10^{-10}$ a millionth already costs three. At $10^{-8}$ the count jumps from six to eleven at a millionth — a larger jump than at $10^{-10}$, because at $10^{-8}$ the separable kernel’s count is the exact six while at $10^{-10}$ rounding had already added two.

Read across, the same ε that costs a solve to $10^{-4}$ nothing costs a solve to $10^{-10}$ half again its steps. A nearly separable field and a loose tolerance can share the separable kernel’s count; a nearly separable field and a tight tolerance cannot, however nearly.

Between the two kernels is harder than either #

At the other end of ε the count does not climb towards the isotropic kernel’s and stop. On the 10 × 10 grid the isotropic kernel takes 26 steps and the mixtures at a tenth and three tenths take 29; on the 16 × 16 grid the isotropic kernel takes 35 and the mixture at three tenths 37. Mixing the two kernels produces a spectrum harder for conjugate gradients than either produces alone.

And it does so while the condition number falls. The rate the condition number predicts found the classical bound — a rate set by the square root of the condition number — loose enough to waste nine iterations in ten when used to provision a solve; here it is not merely loose but pointed the wrong way. The separable kernel’s preconditioned condition number is 361 and its count eight; at three tenths of isotropy the condition number is 197 and the count 29; the isotropic kernel’s is 250 and 26. The condition number moves the opposite way to the step count over almost the whole range. That is the lesson two dimensions, and the cluster that thins and the essays after it kept drawing for this family: the count is set by how the spectrum is arranged, not by its extremes. At three tenths the three widening treads have spread to 3, 22 and 74 per cent of their values and run into each other without yet forming the isotropic kernel’s smoother ramp; a polynomial that must be small on several overlapping wide intervals, with gaps between them that are not quite closed, needs more degree than one small on a single ramp.

What this means for a nearly separable field #

The staircase a separable kernel builds and the essay after it offered separability as the property that makes this preconditioner exact. Fields in practice are rarely exactly separable; correlation models fitted to data are often separable plus a small departure, because separability is what makes them cheap. The measurement says the departure costs in proportion to its size only on a logarithmic scale and only after a threshold set by the tolerance. A millionth of departure is not free at $10^{-10}$; a hundredth is not ruinous at $10^{-4}$, costing fourteen steps against six.

For a solver that means the right question about a nearly separable kernel is not “how close to separable is it” but “how narrow are the treads, against how many decades does the solve need”. Both are cheap to estimate: the treads’ widths to first order in ε from the two symbols, before any iteration, and the decades from the accuracy the answer needs. A limit the matrix never reaches was the first of these essays, and it opened with a statement about a family that did not describe the matrix in front of the reader; the cluster count at one per cent is the same kind of statement, about a spectrum’s shape at a resolution the solver does not work at.

What these grids do not show #

One correlation, one form of departure from separability, grids to 16 points a side, and spectra computed in full only on the 10 × 10 grid. The Chebyshev sum is a heuristic for well-separated clusters, and its two-to-four-step undercount is measured here rather than explained; a sharper account would treat the six intervals together, as one polynomial must, and would need the gaps between treads as well as their widths. The step counts come from one right-hand side, the earlier essays’ $b_i = \sin(1 + 0.7i) + 0.3$, which has weight on every eigenvector; a right-hand side with little weight on the widest tread would pay less for it, and one that lay entirely in the tread at one would see a single cluster and pay for that alone. Conjugate gradients pays only for the parts of the spectrum the right-hand side reaches, which is a second reason the cluster count, a property of the matrix alone, cannot be the whole story. A departure that is anisotropic — different correlations along the two axes — would split the treads differently, and a symbol circulant built from the separable part alone, ignoring the departure, is the cheaper preconditioner a code might actually use and is not measured.

Still open: the separable part alone, and the width from the symbols #

A preconditioner that ignores the departure. The symbol circulant of the separable part alone keeps the Kronecker structure exactly and treats ε as error in the matrix rather than in the preconditioner. The prediction with a sign is that it widens the treads by about the same amount as the mixed symbol does at small ε — so the count follows the same curve to $10^{-3}$ — and is worse past $10^{-2}$, where the mixed symbol starts to absorb part of the isotropic structure.

The widths from the symbols, before the solve. Each tread’s width is linear in ε with a slope that first-order perturbation gives from the separable operator’s eigenvectors and the isotropic part’s two symbols. The prediction is that the slopes computed that way match the measured ones — $7.0$, $1.7$ and $0.21$ per unit of ε for the three widening treads — to a few per cent, which would make the step count at any ε and tolerance a formula in two one-dimensional quantities and the solver’s tolerance.