The slopes were in the symbols

The part a circulant can cancel compared two preconditioners for a kernel that is almost separable. The matrix is the BTTB matrix of $(1-\varepsilon)\rho^{|k_1|+|k_2|} + \varepsilon\rho^{\sqrt{k_1^2+k_2^2}}$ on a square grid: a separable kernel, whose symbol circulant turns its spectrum into a staircase of six treads, and a small isotropic part $\varepsilon$ that breaks the separability. The mixture’s own symbol circulant was compared with the separable part’s alone — the cheaper one, which keeps the Kronecker structure. On conjugate-gradient counts the two agreed to $\varepsilon = 10^{-3}$, and the spectrum said why they then parted: under the separable symbol the tread at one, sixty-four of the hundred eigenvalues on the $10 \times 10$ grid, widens as $13\varepsilon$ and shifts as $7.7\varepsilon$, while under the mixture’s symbol it widens as $1.7\varepsilon$.

Its closing section asked for those slopes from the symbols rather than from the spectrum. “First-order perturbation of the separable operator’s sixty-four-dimensional eigenspace at one by $C_s^{-1}E$ gives both: the shift as the mean of that block’s eigenvalues and the width as their spread. The prediction with a sign is that both computed slopes match the measured ones to within five per cent, and that the same computation with $E$ minus its circulant gives the mixture’s 1.7.”

The widths match to four digits. The shift matches too, but not as the mean.

Sixty-four eigenvalues at one, perturbed #

The computation is the textbook one. Precondition symmetrically: $S(\varepsilon) = C^{-1/2}T(\varepsilon)C^{-1/2}$, with $T(\varepsilon) = T_s + \varepsilon E$, $E = T_{\mathrm{iso}} - T_s$ the BTTB matrix of the isotropic kernel minus the separable one, and $C$ the separable part’s symbol circulant. At $\varepsilon = 0$ the matrix $S_0$ has an eigenvalue one of multiplicity sixty-four, with an orthonormal basis $U$ of its eigenspace. To first order in $\varepsilon$ those sixty-four eigenvalues move to $1 + \varepsilon\mu_k$, where the $\mu_k$ are the eigenvalues of the $64 \times 64$ compression $U^{\mathsf T}C^{-1/2}EC^{-1/2}U$. For the mixture’s own symbol the preconditioner moves with $\varepsilon$ too, $C(\varepsilon) = C + \varepsilon C_E$ with $C_E$ the circulant of $E$’s symbol, and the compression is of $C^{-1/2}(E - C_E)C^{-1/2}$ — the prediction’s “$E$ minus its circulant”.

The first-order widths are 13.372 for the separable symbol and 1.732 for the mixture’s. The measured widths over $\varepsilon$ at $\varepsilon = 10^{-6}$ are 13.372 and 1.732. They agree to a part in ten thousand, and at $10^{-5}$ and $10^{-4}$ the measured values are 13.371 and 13.362: the prediction’s five per cent was generous by three orders of magnitude. The width of the crowded tread is a first-order quantity, and the first-order quantity is computable from the two symbols and the eigenspace without running anything.

A shift that is the midpoint #

The prediction said the shift would be the mean of the sixty-four $\mu_k$.

The mean is 5.770. The measured shift is 7.671 at every $\varepsilon$ from $10^{-6}$ to $0.03$, and 7.29 at 0.1. The two are not close; the measured one is a third larger. But 7.671 is exactly $(\mu_{\min} + \mu_{\max})/2 = (0.985 + 14.357)/2$, to a part in ten thousand, and that is because of how the earlier essays measured a tread: its centre as the midpoint of its lowest and highest eigenvalue, its width as their difference over that centre. A tread’s midpoint moves with its two ends, and first order gives the ends. The prediction named the right object and the wrong statistic of it.

The difference between the two statistics is not a technicality. It says the sixty-four slopes are not symmetric about their midpoint: the mean sits a quarter below it, so more of the eigenvalues lie in the lower half of the spread than the upper. The question it bears on is the one the earlier essay asked next — whether a scalar correction on the eigenspace, dividing by the tread’s mean, would bring the cheap preconditioner level with the expensive one. A scalar correction moves every eigenvalue in the tread by the same factor; it can put the midpoint, or the mean, back at one, and it cannot change the spread. First order puts the spread at $13.37\varepsilon$ and the shift at $7.67\varepsilon$. The error is mostly spread, and conjugate gradients pays for spread.

It pays for spread relative to the cluster’s own size, and that is the decisive point. The steps conjugate gradients spends resolving a cluster depend on the ratio of the cluster’s width to its distance from zero, because its polynomial has to be small across the cluster while equal to one at zero. Dividing every eigenvalue in the cluster by the same number leaves that ratio exactly where it was. A scalar correction on the eigenspace therefore changes where the tread sits, which matters only for how it lines up with the other five, and changes nothing about what it costs to resolve. First order says the separable symbol’s tread has a relative spread of $13.37\varepsilon$ whatever is done to its centre; only a correction that acts differently on different directions in the eigenspace can narrow it.

What the sixty-four slopes look like #

Under the separable symbol they run from 0.985 to 14.357 and are spread across the whole range in clumps — quartiles at 2.6, 5.5 and 8.1, fifteen of the sixty-four below 2 and thirteen above 10. Under the mixture’s symbol they are almost all at zero: the middle half lie between $-0.02$ and $0.01$, and the spread of 1.73 comes from a few outliers, the lowest at $-1.17$ and the highest at $0.56$. The mixture’s symbol does not narrow the tread uniformly; it pins most of it in place and leaves a handful of eigenvalues to move.

The middle strip says where the difference comes from. Split $E$ into its circulant part $C_E$ — the part a symbol circulant can represent — and the remainder $E - C_E$. The mixture’s symbol subtracts $C_E$ exactly, which is why its block is the remainder’s. The separable symbol subtracts none of it. Compress the circulant part alone onto the eigenspace and its slopes run from 1.05 to 14.34, a width of 13.29: ninety-nine per cent of the separable symbol’s 13.37, with the remainder contributing the rest and part of the mixture’s outliers. So the cheap preconditioner’s cost on this tread is almost exactly the isotropic correction’s circulant part, which it could have represented and did not. The circulant the problem did not contain found a circulant preconditioner helping a problem with no circulant structure; here the problem has circulant structure in its correction, and leaving it out is the whole cost.

Rank by rank #

The width and shift are two numbers; first order predicts sixty-four.

At $\varepsilon = 10^{-2}$ every one of the sixty-four sits on its first-order slope: the largest departure is 0.17 per cent of the first-order width. At $10^{-4}$ it is 0.0017 per cent, at $0.03$ half a per cent. Only at a tenth does the tread bend visibly, with the top eigenvalues falling below their slopes by up to 11 per cent of the width. The staircase of clumps the strip figure showed is reproduced in the measured eigenvalues step for step, which is the strongest form the prediction could have taken: not two summary numbers but the whole distribution.

Six treads, both symbols #

The tread at one is the crowded one, but the staircase has six, and the same computation applies to each: take the eigenspace of $S_0$ at that tread’s value $v$, compress the perturbation onto it, and read the spread. For the mixture’s symbol the compression is of $C^{-1/2}(E - vC_E)C^{-1/2}$, because the preconditioner’s own derivative enters multiplied by the eigenvalue it perturbs.

The six values are 0.118, 0.343, 1, 2.233, 6.513 and 42.42, holding one, sixteen, sixty-four, two, sixteen and one eigenvalue. Three of them cannot spread at first order: a tread of one eigenvalue has no width, and the pair at 2.233 moves together, with a first-order width of zero under both symbols. The other three spread, and first order predicts every one of them. Under the separable symbol the relative widths over $\varepsilon$ are 0.547 at 0.343, 13.372 at one and 0.749 at 6.513; measured at $\varepsilon = 10^{-4}$ they are 0.547, 13.362 and 0.749. Under the mixture’s symbol they are 0.213, 1.732 and 7.016, measured 0.212, 1.732 and 7.011.

That last number is the trade the mixture’s symbol makes, and the earlier essay had seen its effect without its size. Subtracting the isotropic correction’s circulant narrows the tread at one by a factor of 7.7 and widens the tread at 6.5 by a factor of 9.4, from 0.75 to 7.02. The mixture’s symbol does not remove the correction’s effect on the spectrum; it moves it from the tread of sixty-four eigenvalues to a tread of sixteen. For conjugate gradients, whose cost depends on how many separate clusters it has to resolve and how wide each is, that is a good trade — the crowded tread is the one whose width costs steps — and it is a trade rather than a removal, which is why at $\varepsilon = 0.1$ and beyond the counts under both symbols rise. The staircase a separable kernel builds found the step count nearly independent of the correlation because the staircase’s treads stay six whatever $ho$ does; a correction moves the treads’ widths, and first order says which.

Two dimensions, and the cluster that thins and four orders of conditioning, and four steps are the essays where this staircase was first measured, and where the count of distinct eigenvalue groups, rather than the condition number, was found to set conjugate gradients’ work. The six first-order widths are that idea made quantitative for a perturbed kernel: the count is still six, and the work added by the correction is the sum of what each tread’s width costs, which is now computable before the solve. A limit the matrix never reaches is the reminder that a symbol is an asymptotic object and a finite section approaches it slowly; here the symbols are exact descriptions of the finite circulants, and nothing asymptotic is being claimed.

The centre, not the eigenvalues #

The earlier essay’s table showed the separable symbol’s width over $\varepsilon$ falling as $\varepsilon$ grew — 13.27 at $10^{-3}$, 12.41 at $10^{-2}$, 7.26 at 0.1 — and that reads like first order failing from a thousandth. It is not.

The width the essays measured is relative: the spread divided by the centre. The centre is $1 + 7.67\varepsilon$, so the relative width is the spread divided by a number that grows linearly in $\varepsilon$, and it falls below the first-order spread by $7.67\varepsilon$ to first order — 0.8 per cent at $10^{-3}$, seven at $10^{-2}$ — for no reason but its own definition. Multiply the measured relative width at $10^{-2}$ back by its centre and it is within 0.1 per cent of first order. The eigenvalues themselves follow first order to 0.17 per cent of the width at $10^{-2}$ and 0.5 per cent at $0.03$; the departure rises like $\varepsilon$, as a second-order term over a first-order one should, and only past a few hundredths does it matter.

That changes the reading of the earlier essays’ counts. Six steps were six eigenvalues found that conjugate gradients needed more steps than treads as soon as the treads widened, and that the tolerance decided how many; with first order holding to a few hundredths, the count at any $\varepsilon$ in that range is a function of the symbols alone, through the sixty-four slopes. A preconditioner designer can compute, before running anything, that the separable symbol will cost the tread about eight times the mixture’s width at every small $\varepsilon$, and that the factor is the isotropic correction’s circulant part.

How much of the width is the grid’s #

The first-order computation is cheap enough to repeat on other grids, and it answers a question the measurements on one grid could not: whether the cheap preconditioner’s cost on the crowded tread is a property of the kernel or of the grid. On grids of 6, 8, 10, 12 and 14 the middle tread holds 16, 36, 64, 100 and 144 eigenvalues — $(m-2)^2$ — and its first-order width under the separable symbol is 10.50, 12.34, 13.37, 14.13 and 14.59. It grows with the grid, by 1.84, 1.03, 0.76 and 0.47 at each step, so it is converging, but not fast, and on any grid an engineer would use it is above the 10 × 10 value. The midpoint shift falls as the width rises, from 8.10 to 7.33. The circulant part’s share of the width rises from 88 per cent on the 6 × 6 grid to 99.8 per cent on the 14 × 14, so the larger the grid, the more completely the cheap preconditioner’s cost is the circulant it leaves out. The mixture’s width barely moves: 1.58, 1.59, 1.73, 1.75 and 1.79.

So the ratio between the two preconditioners on this tread grows with the grid too, from 6.6 to 8.2 over these five grids, and that is a statement about the kernel and the grid together that no single-grid measurement could have made. It is the reason the prediction’s five per cent would have been the wrong tolerance for a law across grids: the first-order computation is exact on each grid, and the grids differ.

What the prediction got right #

Everything it asked for in substance. Its numbers — 13, 7.7 and 1.7 — were the measurements, and its method reproduces them; it was right that the mixture’s symbol corresponds to subtracting $E$’s circulant, and right that the eigenspace at one is the place to look. What it had wrong was the summary statistic, and the earlier essay’s apparent first-order failure was the same kind of mistake in the other direction: a relative width read as an absolute one. The symbol that builds the staircase found that the separable kernel’s symbol circulant produces the staircase exactly; this essay finds that the symbols produce its first-order deformation exactly too, and the only things standing between the symbols and the spectrum were two definitions.

What five grids do not show #

The spectra are measured on the $10 \times 10$ grid only, at $\rho = 0.9$; first order is computed on five grids, and on the other four it is checked against nothing but its own convergence. The tread at one is computed on all five and the other treads on one. Every claim about conjugate gradients here is an inference from the eigenvalues — first order describes the spectrum, not the count, which depends on it through a polynomial that first order does not touch — and the one count that would test the inference, the separable symbol’s steps on the $14 \times 14$ grid against the mixture’s, is not made. A different $\rho$ would change both symbols and every number above, and whether the circulant part’s share of the width approaches one at every correlation is the kind of statement five grids at one $\rho$ can suggest and not settle.

Still open: the grid’s limit, and a correction that is not scalar #

The limit of the width. The first-order width under the separable symbol grows by less at each step of the grid — 1.84, 1.03, 0.76, 0.47. The prediction with a sign is that it converges, that on a 30 × 30 grid it is between 15.5 and 16.5, and that its limit is the spread of the isotropic correction’s symbol divided by the separable symbol’s, taken over the frequencies where the separable symbol equals its middle value — a number computable from the two kernels with no matrix at all.

A correction of rank sixteen. If the mixture’s symbol pins all but a handful of the tread and the separable symbol leaves the circulant part spread across all sixty-four, the cheapest repair is not a scalar but a low-rank correction on the eigenspace’s top directions. The prediction is that projecting out the sixteen largest first-order slopes and correcting them by their own values brings the separable symbol’s tread width to within a factor of two of the mixture’s, at a cost of sixteen inner products a step, up to $\varepsilon = 10^{-2}$.