The circulant that cannot be indefinite

The previous essay in this field ends on a number that should not have been possible. Preconditioning a positive definite Toeplitz system with the circulant nearest to it — the standard method, with a theorem behind it saying the step count stops depending on n — took 109 steps against an unpreconditioned 66 at ρ = 0.95 and n = 64. The preconditioner was making things worse, and the reason was that its smallest eigenvalue was −0.173: the approximation to a positive definite matrix was not positive definite.

That essay left a question open in as many words, and the phase that wrote it recorded the question as a deferral: is an indefinite preconditioner a fact about circulant preconditioning, or about that particular circulant?

It is the second, and the settling takes one line of arithmetic.

Two circulants, and the line between them #

A Toeplitz matrix is constant along each diagonal. A circulant is too, and its diagonals wrap: entry (i, j) depends on (i − j) mod n. So a circulant has n free entries where the Toeplitz matrix has 2n − 1, and building one from the other means deciding what to do with the two diagonals — the kth sub-diagonal and the (n − k)th super-diagonal — that compete for each circulant slot.

Strang’s answer is to choose. Keep whichever of the two is nearer the main diagonal and discard the other; at the halfway point, where neither is nearer, put a zero. It is a projection in the plain sense: keep as much of each diagonal as fits.

T. Chan’s answer is to average, weighted by how many entries each diagonal contributes:

cⱼ  =  ((n − j)·tⱼ  +  j·tⱼ₋ₙ) / n

That formula is not a heuristic and it is worth seeing why, because the reason is the whole essay. The circulants form a linear subspace of the matrices, and the minimiser of a Frobenius distance to a linear subspace is the orthogonal projection onto it — which, entry by entry, averages over each residue class of the index. The weights (n − j)/n and j/n are the counts of entries in each class.

The consequence, in one sentence #

An average of positive quantities is positive; a choice between them need not be.

Every entry of the averaged circulant is a convex combination of entries of T’s own diagonals, and its eigenvalues are the transform of that vector. Measured across the sweep the previous essay used:

The averaged one’s margin shrinks with n, which is asserted rather than glossed: 0.0431 down to 0.0276 across the sweep. It is not comfortable — a preconditioner whose smallest eigenvalue is approaching zero is a preconditioner heading towards trouble — and it is a different situation from crossing.

What the step counts do #

Three things in that table, and the third is the one this field has been waiting for.

The wrapped circulant is worse than useless while it is indefinite. 55 steps against an unpreconditioned 37, 117 against 59, 122 against 99. Conjugate gradients requires a positive definite preconditioner — the derivation uses M⁻¹ to define an inner product, and an indefinite M has no inner product — so what runs in those rows is a method outside its own hypotheses.

It is excellent the moment it becomes definite. 9 steps at n = 256, better than the averaged circulant’s 10. Strang’s construction is a sharper approximation of the symbol where it works, and this table is not an argument that it is a bad idea.

And the averaged circulant delivers, at every size drawn, the thing this field’s organising finding says not to expect. The structure field exists because an asymptotic statement is not a statement about a computation: Szegő’s limit reached to 52% at n = 8, the O(1) step count arriving as 109. Here the O(1) arrives as 7, 8, 9, 10, 10 — at n = 16, where “asymptotically” has no business meaning anything.

That is worth having as a counter-case rather than an exception. The promise was never about circulant preconditioning in general. It was about a circulant that stays definite, and the literature’s habit of stating it without that condition is what made the previous essay’s measurement look like a refutation of a theorem rather than of a sentence.

Where the crossing actually is #

The table above brackets Strang’s crossing between n = 128 and n = 256 at ρ = 0.95, which is a bracket rather than a threshold — and the threshold is the number a practitioner needs, because it says at what size the wrapped circulant may be used at all.

Bisecting over even sizes (odd n has no ambiguous middle diagonal, so Strang’s construction is a different one there) gives it exactly:

ρ = 0.7 → n = 12. ρ = 0.8 → 22. ρ = 0.9 → 58. ρ = 0.95 → 144. ρ = 0.98 → 456. ρ = 0.99 → 1,056.

Two criteria suggest themselves for what that threshold is, and neither survives the numbers.

Not a fixed number of correlation lengths. The width measured in them, n·ln(1/ρ), runs 4.28, 4.91, 6.11, 7.39, 9.21, 10.61 — rising by a factor of two and a half across the range.

And not a fixed size of discarded diagonal. The entry Strang throws away is ρ^(n/2), and at the threshold it runs 0.118, 0.086, 0.047, 0.025, 0.010, 0.005 — falling by a factor of twenty-four, in the opposite direction.

So the two natural explanations drift by an order of magnitude each and neither is the rule. What the measurement gives instead is a fitted law: the threshold grows like (1 − ρ)⁻¹·³², which is faster than the correlation length 1/(1 − ρ) it might have been expected to track. Doubling the correlation more than doubles the size at which the method becomes admissible.

It is worth saying why the two candidate rules fail in opposite directions, because between them they bracket the real mechanism. A criterion in correlation lengths asks whether the matrix is wide enough to see the decay; a criterion on ρ^(n/2) asks whether the discarded entry is small. The definiteness of the wrapped circulant depends on neither alone: it depends on whether the discarded half-diagonal, summed with its own sign pattern across the transform, can pull any one eigenvalue below zero — which is a statement about the whole discarded tail against the whole kept one, and both of those change shape as ρ moves. A single scalar summary of a tail is what neither criterion can be.

What that means for using it #

The practical reading is sharper than the previous essay’s and points the same way.

At ρ = 0.9 the crossing is at n = 58, so almost any real problem is past it and Strang’s circulant is the better preconditioner — nine steps against ten at n = 256, which is the trade the section below prices. At ρ = 0.99 the crossing is at 1,056, so a matrix of a few hundred rows is on the wrong side of it, and conjugate gradients preconditioned by an indefinite matrix is running outside its own hypotheses with a step count that gets worse rather than failing. That is exactly the reading that made the previous essay’s 109 steps look like a refutation of a theorem.

And the threshold is computable before anything is built. It needs ρ and n and no matrix at all — a bisection over a discrete transform of a geometric sequence, which is milliseconds — so a code choosing between the two circulants has the information to choose correctly and no reason not to. The averaged circulant is the safe default precisely because it needs no such check, and the wrapped one is worth its extra step only where the check passes.

What the threshold does not say is anything about how badly an indefinite preconditioner behaves. It crosses zero at n*, and at n slightly below it the smallest eigenvalue is slightly negative, and the measured step counts — 55 against 37, 117 against 59 — are not a smooth function of how negative it is. A method outside its hypotheses has no error bound to be small, which is the same distinction a backward error draws between an answer that is inaccurate and an answer that is not the answer to anything.

The honest half: what never failing costs #

At n = 256 both circulants are definite and the wrapped one takes 9 steps against the averaged one’s 10. The trade is one step, it is real, and it is asserted:

the preconditioner that discards half of each diagonal is the sharper approximation where it works, and the one that averages them is the one that always works.

So the choice between them is not a choice between a good method and a broken one. It is the ordinary engineering trade — a slightly better typical case against a guarantee — with the unusual feature that the guarantee costs almost nothing and is available for free from a formula one line long.

And the flattering-looking half is not the one that decides it: the averaged circulant is also the nearer of the two in the Frobenius norm, at every size, since it is the minimiser by construction. That fact is the refusal this essay’s family runs, fed the claim that a nearer circulant is a better preconditioner — which at n = 256 is false by one step, on the same pair of matrices where it is nearer.

What the preconditioned spectrum looks like #

The step counts have to come from somewhere, and the somewhere is the spectrum of C⁻¹T.

Measured across the family, the averaged circulant’s preconditioned spectrum stays inside a range whose lower end barely moves: the smallest eigenvalue of C⁻¹T is 0.68 at ρ = 0.5, 0.56 at 0.8, 0.52 at 0.9 and 0.50 at 0.95, at every size from 16 to 64. The upper end grows — 1.9, 4.7, 8.8, 15.0 at n = 64 — so the preconditioned condition number is not constant either; it climbs slowly, and the step count climbs slowly with it.

That is the honest account of “O(1)”: not a constant, but a quantity growing so slowly that a factor of sixteen in the problem size costs three iterations. Compare the unpreconditioned column, which grows by a factor of 7.5 over the same range.

The measurement also says which quantity the step count follows, and it is not the one the theorems are stated about. At ρ = 0.95 and n = 64 the averaged circulant clusters nothing within a tenth of one — and takes 9 steps. What it does is keep the whole spectrum away from zero and inside a modest range. The clustering is what makes the asymptotic argument work; the boundedness is what makes the finite-size count small.

Why the wrapped one is indefinite at all #

One paragraph on the mechanism, because “it discards a diagonal” is not by itself an explanation.

A circulant’s eigenvalues are the discrete transform of its first column. The wrapped column is the Toeplitz decay ρ^k run up to the halfway point and then the mirror ρ^(n−k) — a sequence with a kink in the middle, and at even n a zero dropped in at exactly n/2 because two diagonals compete for one slot and Strang’s definition declines to choose. The transform of a sequence with a discontinuity has large oscillating components, and at the frequencies where those components exceed the smooth part the eigenvalue goes negative.

The averaged column has no kink: it decays from ρ⁰ towards the middle and back, continuously, because each entry is a weighted blend of the two competing values with the weights themselves varying continuously. Its transform is the transform of a smooth positive sequence.

So the two constructions differ by exactly the treatment of one seam, and the eigenvalue that goes negative is the one belonging to the frequency that seam excites.

The frame above is one decay rate. Whether the sign change is a property of the construction or of that particular rho is what the rest of the slider answers:

Two decay rates, two limits, and the limits are the numbers worth writing down — both of them are comfortably positive, and at neither rho does the wrapped construction fail at any size the figure can draw. The failure starts one step further along.

One size out of five, at the smallest size drawn, is the kind of defect that never shows up in a test suite. Turning the decay rate closer to one makes it show up everywhere:

The limit is exactly (1 − ρ)/(1 + ρ). Five of the six ρ match it to every digit printed — 0.3333, 0.2500, 0.1765, 0.1111, 0.05263 — and the sixth is still climbing towards it at the largest size the figure draws. So the wrapped circulant’s definiteness is not an accident of the sizes anybody happened to test; it has a closed-form limit, and that limit is positive for every ρ < 1.

What is not asymptotic is the approach, and that is where it fails. The size at which λ_min turns positive is 16 or below at ρ ≤ 0.7, then 32, then 64, then 256 — so the closer the decay rate is to one, the longer the preconditioner spends indefinite. At ρ = 0.95 it is indefinite at four of the five sizes drawn, and the limit it is heading for is 0.0257.

And while it is indefinite it makes things worse rather than merely failing to help. At ρ = 0.95 the iteration counts go 111 → 134 at n = 128 and 66 → 109 at n = 64: the preconditioned system takes more steps than the unpreconditioned one. At ρ = 0.9, n = 32 it is 37 → 44. Once λ_min turns positive the same preconditioner is worth a factor of eighteen — 179 → 10 at ρ = 0.95, n = 256 — so the two regimes are not “good” and “less good”; they are opposite signs of the same decision.

That is the whole case for the averaged construction, and it is a case about the approach rather than the limit. Both circulants are positive definite in the limit; only one of them is positive definite at n = 16.

What this settles about the previous essay #

Three things, and they are worth stating separately because only one of them was in doubt.

The measurement stands. 109 steps against an unpreconditioned 66 was correct, is reproducible, and is what the wrapped circulant does at that ρ and n.

The blame moves. It was recorded there as a property of circulant preconditioning, with the verdict asymptotic — a method whose promise holds in a limit and not at the sizes anybody runs. Half of that survives: the promise is asymptotic. The other half does not — the failure was one construction’s, and a different construction of the same kind, at the same sizes, delivers the promise in full.

And the site’s own habit is what found it. The whose-fault-is-it thread is normally about separating the algorithm’s contribution to an error from the problem’s. Here it separates a method’s contribution from a variant’s, which is the same move one level down, and it needed a second construction to be written and measured rather than an argument.

Why the averaged circulant is the minimiser, and why that is checked #

The formula in the second section is stated as the nearest circulant in the Frobenius norm, which is a claim rather than a definition, and this site’s habit is to compute a claim by a second route rather than to quote it.

The derivation is short. The circulants of a given size form a linear subspace of the matrices — closed under addition and scaling, with n free parameters. The Frobenius norm comes from an inner product. The nearest point of a linear subspace in an inner-product norm is the orthogonal projection onto it, and the projection here is an average: entry (i, j) of a circulant is determined by (i − j) mod n, so the entries of A that a single circulant entry has to represent are exactly those whose index difference lies in one residue class, and the least-squares choice is their mean.

The weights (n − j)/n and j/n are then a count rather than a design: of the n entries in residue class j, exactly n − j come from the jth sub-diagonal and j from the (n − j)th super-diagonal.

Two routes are computed and compared. optimalCirculant applies the weighted-average formula; nearestCirculantByFitting sets up an n²-row least-squares problem for the n free entries and hands it to this site’s own Householder QR, knowing nothing about diagonals. They agree to 2.2·10⁻¹⁶, 3.3·10⁻¹⁶ and 1.0·10⁻¹⁵ at three sizes. That is what makes “the minimiser” a measured claim here, and it is what would catch the plausible error in this construction — weights that are right in form and wrong at the ends, which no eyeball on a decaying sequence would see.

What the preconditioned spectrum does, and what it does not #

The step counts have to come from somewhere, and the somewhere is the spectrum of C⁻¹T. Measured across the family:

The lower end barely moves — it is near a half at every ρ and every size from 16 to 64 — and the upper end grows with ρ. So the preconditioned condition number is not constant either; it climbs slowly, and the step count climbs slowly with it. That is the honest account of “O(1)”: not a constant, but a quantity growing so slowly that a factor of sixteen in size costs three iterations, against an unpreconditioned count that grows by a factor of 7.5 over the same range.

The measurement also says which quantity the step count follows, and it is not the one the theorems are stated about. At ρ = 0.95 and n = 64 the averaged circulant clusters nothing within a tenth of one, and takes 9 steps. What it does is keep the whole spectrum away from zero and inside a modest range. Clustering is what makes the asymptotic argument work; boundedness is what makes the finite-size count small, and on this family the second arrives long before the first.

What is left #

The other circulant-like preconditioners. The ω-circulant and skew-circulant families, and the band-Toeplitz preconditioners, are the obvious neighbours; each replaces the wrapping convention with another and each has its own definiteness story.

A non-symmetric Toeplitz system, where conjugate gradients does not apply and the whole apparatus has to be restated for GMRES — at which point the definiteness question becomes a question about the field of values, and the clean sign argument above has no analogue.

And the second dimension, which is the next essay and where the averaged circulant survives and the theorem does not.

An object with the same relation to its data #

A circulant contains n² numbers and is described by n. A Sylvester equation’s coefficient matrix contains n⁴ and is described by 2n², and in both cases forming it is a decision to store what was already known.