The part a circulant can cancel

Six steps were six eigenvalues took a Toeplitz-block-Toeplitz system whose kernel is separable, $\rho^{|k_1|+|k_2|}$, and added a fraction $\varepsilon$ of the isotropic kernel $\rho^{\sqrt{k_1^2+k_2^2}}$. Preconditioned by the circulant sampled from the whole mixture’s symbol, the spectrum that had been six exact values — sixty-four of a hundred eigenvalues at one — broadened into six treads whose widths grew in proportion to $\varepsilon$, and conjugate gradients went from eight steps to thirteen at a ten-thousandth of isotropy.

Its last section proposed the cheaper preconditioner. “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.”

Both statements about the step count hold. The statement about the treads, which was offered as their reason, does not: the two preconditioners widen different treads, by amounts that differ by nearly an order of magnitude, and arrive at the same count anyway.

Two preconditioners for one matrix #

The matrix is the same in both: the Toeplitz-block-Toeplitz covariance of the kernel $(1-\varepsilon)\rho^{|k_1|+|k_2|} + \varepsilon\rho^{\sqrt{k_1^2+k_2^2}}$ at $\rho = 0.9$ on a grid of $m \times m$ points, $m$ from 6 to 16. The first preconditioner is the circulant whose eigenvalues are the mixture’s own symbol sampled at the grid’s frequencies, the one the earlier essay used. The second is the circulant sampled from the separable kernel’s symbol alone, whatever $\varepsilon$ is. It is cheaper in a way that matters in practice: it is a Kronecker product of two one-dimensional circulants, so it can be applied and inverted one dimension at a time, and it never needs the two-dimensional symbol of the isotropic part at all.

That structure is the one the staircase a separable kernel builds found doing all the work on the separable kernel: the two-dimensional operator is the one-dimensional one in each direction, multiplied, so its spectrum, its symbol and its preconditioned spectrum are all products of one-dimensional ones. With $\varepsilon = 0$ both preconditioners are this one, the preconditioned operator has six distinct eigenvalues, and conjugate gradients stops when it has found all six — the closed Krylov subspace that the zero that means it is finished describes as the one case in which a Krylov method’s breakdown is the answer. Every step past the separable kernel’s own count — eight at $10^{-10}$, two of them rounding’s — is a step spent resolving a tread that the isotropic part has turned from a value into an interval.

On the 10 × 10 grid the two curves are one curve to $\varepsilon = 10^{-3}$: 11, 12, 13 and 18 steps under both. At a hundredth they are 22 and 21, at three hundredths 25 and 28, and then they part: 29 against 35 at a tenth, 29 against 48 at three tenths, and on the isotropic kernel itself 26 against 83. The dial shows the same shape on the 6 × 6 and 16 × 16 grids. To $10^{-3}$ the counts are within one step of each other on every grid, at both tolerances measured; from a tenth the separable symbol needs more on every grid, and on the isotropic kernel more than twice as many. The prediction’s two clauses about the count are right.

The treads that widen are not the same treads #

The figure at the top of the page follows two of the six treads. Under the mixture’s symbol the tread near 6.5 — sixteen eigenvalues — is the widest, growing as $7.0\,\varepsilon$, and the tread at one grows as $1.7\,\varepsilon$; these are the slopes the earlier essay measured. Under the separable symbol the order is reversed. The tread at one grows as $13\,\varepsilon$, and the tread near 6.5 as $0.75\,\varepsilon$. The tread at one holds sixty-four of the hundred eigenvalues, and the cheaper preconditioner puts its error there, 7.6 times as much as the mixture’s symbol does, while leaving the mixture’s widest tread nine times narrower.

That is not a small disagreement about a detail. The prediction’s reason for the counts agreeing was that the two preconditioners do the same thing to the spectrum at small $\varepsilon$; they do quite different things, and every line in the figure has slope one, so the difference does not fade as $\varepsilon$ shrinks. At a millionth of isotropy the two spectra are as differently shaped, relative to their size, as at a thousandth.

Why the counts agree anyway #

Conjugate gradients on a spectrum of well-separated clusters pays, roughly, a number of steps for each cluster that depends on the logarithm of its width relative to its position — the estimate the earlier essay checked against its counts, and found one to four steps low. A tread of width $\delta$ costs about $\log(\text{tol}/2)/\log(\delta/4)$ steps; a tread of width $13\varepsilon$ and one of width $7\varepsilon$ cost nearly the same, because the factor of two between them is a fraction of a step once it is inside a logarithm. What decides the count is the width of the widest tread and how many treads are wide at all, and on both counts the two preconditioners are close: one wide tread, two narrower ones, and the rest exact.

Which tread is wide does not enter, and in particular how many eigenvalues it holds does not. A cluster of sixty-four eigenvalues and a cluster of sixteen of the same width cost conjugate gradients the same, because a polynomial that is small on an interval is small on every eigenvalue in it. Four orders of conditioning and four steps found the same indifference from the other side: a condition number that changed by four orders of magnitude cost four steps, because the extremes were isolated eigenvalues that each cost one.

At a hundredth of isotropy the picture shows both effects at once. Under the mixture’s symbol the tread near 6.5 has spread to 6.5 per cent of its centre and the tread at one to 1.7; under the separable symbol the tread at one has spread to twelve per cent and moved, centred at 1.077, while the tread near 6.5 is three quarters of a per cent wide. Counted at the one-per-cent rule, the mixture’s spectrum has nine clusters and the separable symbol’s seven. And yet the counts are 22 and 21.

What the mixture’s symbol cancels #

The reason the two preconditioners put their error in different places is in what each leaves uncancelled. Write the matrix as the separable part plus $\varepsilon E$, where $E$ is the Toeplitz matrix of the isotropic kernel minus the separable one. The separable symbol’s circulant inverts the separable part’s circulant approximation exactly, and leaves all of $\varepsilon E$ as error. The mixture’s symbol circulant includes $\varepsilon$ times the circulant of $E$’s own symbol, and so cancels the part of $E$ that a circulant can represent — leaving only $E$ minus its circulant, the part that lives in the corners of the Toeplitz blocks where a circulant and a Toeplitz matrix differ.

The tread at one is where the separable kernel’s Toeplitz matrix and its symbol circulant agree exactly, which is why sixty-four eigenvalues sat at one in the first place: the symbol that builds the staircase found each one-dimensional factor’s preconditioned operator to be the identity plus rank two, so its eigenvalue one belongs to every direction the rank-two correction does not reach, and the two-dimensional product has sixty-four such directions. On the evidence of the widths, those are directions in which most of $E$’s effect is circulant: the separable symbol leaves its error there in full, and the mixture’s symbol cancels seven-eighths of it. The tread near 6.5 is built from the correction’s own directions, where $E$’s Toeplitz-minus-circulant part is largest, and no circulant can cancel that — so the mixture’s symbol leaves its error there, and the separable symbol, whose error is spread over $E$ as a whole, has less there by comparison.

The centres say the same. Under the separable symbol the tread at one does not only widen; it moves, to 1.0077 at a thousandth of isotropy, 1.077 at a hundredth and 1.73 at a tenth — a shift of about $7.7\,\varepsilon$, which is the uncancelled circulant part of $\varepsilon E$ acting on the sixty-four directions as a near-multiple of the identity. The other treads barely move until $\varepsilon$ passes a hundredth. A shift by itself costs conjugate gradients nothing, since a cluster’s cost depends on its width relative to where it sits; a width is not free. The separable symbol’s error on the crowded tread is mostly shift, which is part of why its count keeps pace for so long.

Where the mixture’s symbol pulls ahead #

The second clause of the prediction gave the reason the mixture’s symbol would pull ahead: it “starts to absorb part of the isotropic structure”. The condition number shows it doing so. Under the separable symbol the condition number stays within three per cent of the separable kernel’s 361 all the way to $\varepsilon = 0.1$ — the preconditioner does not see the isotropy, so it cannot change the extremes — and then rises, to 390 at three tenths and 887 on the isotropic kernel. Under the mixture’s symbol it falls, to 344 at a hundredth, 260 at a tenth and 197 at three tenths, which is the absorption the prediction named. The steps follow the condition number: within a step of each other while both condition numbers are near 361, apart by four to six on every grid at a tenth, once the mixture’s has fallen by a quarter, and by twelve to twenty-one at three tenths.

The difference, grid by grid and tolerance by tolerance, is a step either way up to a thousandth, a few steps either way at a hundredth — on the 16 × 16 grid the separable symbol is one step ahead there — and then a gap that opens to 57 on the 10 × 10 grid and 110 on the 16 × 16 at $\varepsilon = 1$. For a field that is separable to within a per cent, the cheaper preconditioner costs nothing measurable; for one that is a tenth isotropic, it costs a fifth more steps on the 10 × 10 grid and more on larger grids.

The small dots in the figure, at $10^{-6}$, sit closer to zero than the lines at $10^{-10}$ wherever $\varepsilon$ is small, and the two sets of points cross zero in both directions below a hundredth: on the 10 × 10 grid at $10^{-5}$ the separable symbol is two steps behind at the looser tolerance and level at the tighter one, and on the 16 × 16 at $10^{-4}$ it is a step ahead at both. Differences of one or two steps that change sign with the grid and the tolerance are the noise floor of this comparison; a step count is an integer, and the two preconditioners’ spectra are different enough in shape that the integer can round either way. Nothing below a hundredth of isotropy is larger than that floor, on any of the three grids or at either of the two tolerances.

The tolerance decides how long the agreement lasts #

The earlier essay found that at small $\varepsilon$ the tolerance was the knife edge: at $10^{-4}$ a ten-thousandth of isotropy cost at most two steps, and at $10^{-10}$ it cost five or more. The comparison here behaves the same way across the two tolerances measured. To a residual of $10^{-6}$ the two preconditioners agree within two steps on every grid up to a thousandth of isotropy, and part by a tenth — 23 against 18 on the 6 × 6 grid and 25 against 20 on the 10 × 10. At $10^{-10}$ the agreement is tighter, within one step, and the parting comes at the same place.

That is the logarithm again. A looser tolerance asks the polynomial to be small on each tread by less, so each tread costs fewer steps and the difference between a tread of width $13\varepsilon$ and one of width $7\varepsilon$ is a smaller fraction of a step still. What does not shrink with the tolerance is the separable symbol’s failure past a tenth, because by then its spectrum is not six treads of small width but a spread of forty-odd clusters at the one-per-cent rule — 46 at three tenths, against the mixture’s 19 — and conjugate gradients pays for spread at every tolerance.

A limit the matrix never reaches warned that a statement about a Toeplitz family’s symbol is not a statement about the matrix actually being solved; the symbols here are statements about an infinite grid, and the matrices are 36 to 256 unknowns. The agreement to a thousandth holds on all three grids measured, and the size of the gap past a tenth grows with the grid — 12 extra steps on the 6 × 6 at three tenths, 19 on the 10 × 10, 21 on the 16 × 16 — which is the direction the symbol’s statement about the limit would predict: the larger the grid, the more of the matrix the circulant describes, and the more the part it leaves out matters.

What this says about choosing a symbol #

The symbol that builds the staircase found that a circulant built from a kernel’s own symbol gathers a separable kernel into six treads and leaves an isotropic one a ramp. This measurement says what part of a mixture’s symbol is worth computing: only the part a circulant can cancel, and only once there is enough of it to move the condition number. Below a hundredth of isotropy the separable symbol — two one-dimensional symbols and a Kronecker product — is as good as the full two-dimensional one, and its error lives on the crowded tread where a shift costs nothing. Two dimensions and the cluster that thins and the circulant that cannot be indefinite both found the symbol circulant’s virtues to be properties of the symbol’s sign and decay; the separable symbol has the separable kernel’s, which are as good as they get.

What these grids do not show #

Every measurement is at $\rho = 0.9$ on grids up to 16 × 16; the treads’ slopes are measured on the 10 × 10 grid only, and how they scale with the grid is not measured here. The step counts start from one right-hand side. The explanation of where each preconditioner leaves its error is an argument from the structure of $E$ checked against the widths and centres, not a computation of $E$’s circulant part on each eigenspace, which would settle it.

Still open: the slopes from the symbols, and a correction of rank one #

The slopes, computed. Under the separable symbol the tread at one widens as $13\,\varepsilon$ and shifts as $7.7\,\varepsilon$. 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.

A cheap correction to the cheap preconditioner. If the separable symbol’s error on the crowded tread is mostly a shift, a scalar correction — dividing the preconditioned operator’s action on that eigenspace by its mean — would remove it. The prediction is that such a correction, which costs one inner product per step, brings the separable symbol to within one step of the mixture’s symbol up to $\varepsilon = 10^{-2}$ on every grid, and does nothing past it, where the widths and not the shift decide.