Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Toeplitz matrix — where it appears

A matrix constant along each diagonal, described by 2n − 1 numbers and having no zero entries to exploit. Its structure buys an exact spectrum in the limit and a solve in n log n; what it does not buy is a well-conditioned problem, which is the half usually left out.

Named by 11 essays across one field — each of them below, with the objects they name alongside it.

10¹10²10²size ncondition numberlimit 81measureda limit, as a fraction of itselfreached at n = 1280.99still to go0.011κ at n = 8, as a fraction0.52every point is below the line and none of them is on itthe limit is not a value

A limit the matrix never reaches

Szegő's theorem gives a Toeplitz family's condition number in closed form — ((1+ρ)/(1−ρ))², which is 81 at ρ = 0.8. The 8×8 section reaches 52% of it, the 128×128 reaches 98.9%, and none of them ever arrives. A statement about a family is not a statement about the matrix in front of you.

structure · Toeplitz 10²110¹10²size niterations to 10⁻¹⁰λₘᵢₙ(C) changes signno preconditionerStrang's circulantthe preconditioner's own spectrumλₘᵢₙ(C) at n = 16-0.4λₘᵢₙ(C) at n = 32-0.14λₘᵢₙ(C) at n = 640.016λₘᵢₙ(C) at n = 1280.051λₘᵢₙ(C) at n = 2560.053left of the line the repair costs stepsright of it, the count stops counting n

A preconditioner that changes sign

Strang's circulant preconditioner takes Toeplitz conjugate gradients from 179 steps to 10 at n = 256. At n = 64 on the same family it takes 66 steps to 109 — worse than doing nothing. Between those rows the preconditioner's smallest eigenvalue crosses zero, and nothing in the published account of the method mentions that it can be negative.

structure · Preconditioning 10²110¹10²size niterations to 10⁻¹⁰λₘᵢₙ(C) changes signno preconditionerStrang's circulantthe preconditioner's own spectrumλₘᵢₙ(C) at n = 16-0.4λₘᵢₙ(C) at n = 32-0.14λₘᵢₙ(C) at n = 640.016λₘᵢₙ(C) at n = 1280.051λₘᵢₙ(C) at n = 2560.053left of the line the repair costs stepsright of it, the count stops counting n

The circulant that cannot be indefinite

The previous essay found a preconditioner taking 117 steps against an unpreconditioned 59, because its smallest eigenvalue was −0.173. Average the two diagonals instead of choosing between them and the count is 7, 8, 9, 10, 10 across a factor of sixteen in size.

structure · Toeplitz 10²020406080100120unknownsiterations2D, no preconditioner2D, preconditioned1D, preconditionedone construction, two dimensions2D steps at 16 unknowns102D steps at 100 unknowns211D steps at 100 unknowns10the same averaging, the same transformand a count that no longer stops growing

Two dimensions, and the cluster that thins

The same kernel, the same averaging, the same transform — applied along two axes instead of one. In one dimension the preconditioned step count is 7, 10, 10, 10; on square grids with the same unknown counts it is 10, 18, 20, 21, and the share of the spectrum near one falls from 56% to 17%.

structure · Toeplitz the smallest perturbation of any kind — 1.89·10⁻¹⁷the smallest Toeplitz one — 2.65·10⁻¹³both exact for the same x̂smallest of any kind1.9·10⁻¹⁷smallest Toeplitz one2.7·10⁻¹³the price of the constraint1.4·10⁴diagonal defect, unconstrained0.97an exact answer to a nearby problemof a kind nobody posed

A nearby problem of the wrong kind

A good algorithm returns the exact answer to a nearby problem. A hundred and eighteen essays have measured the distance and not one has asked what the nearby problem looks like. On a Toeplitz system it is a rank-one matrix that is constant along none of its diagonals — and the smallest one that is Toeplitz is two and a half million times larger.

structure · Structured backward error 110¹10²10³10⁻¹⁸10⁻¹⁴10⁻¹⁰10⁻⁶10⁻²10²10⁶numbers that describe the matrixcondition number, and backward errordensetoeplitzsymmetricρ aloneno such problemcondition numberbackward errorone matrix, four descriptionsκ, all n² entries7.9·10⁴as one number, ρ62backward error, unconstrained2·10⁻¹⁷as a symmetric Toeplitz matrix5.6·10⁻¹²fewer numbers, better conditionedand no nearby problem left

The condition number of the model

Describe a 40×40 Toeplitz matrix by its 1,600 entries and its condition number is 78,800. Describe it by the one number it actually contains and the condition number is 61.9. The three decades in between are not an approximation or a bound — they are what κ has been over-stating, and the drop is not where the linear algebra is.

structure · Structured backward error 10²02040size niterationsno preconditionerwrapped (Strang)averaged (T. Chan)both are circulant approximations‖C − T‖/‖T‖, averaged0.22‖C − T‖/‖T‖, wrapped0.23smallest eigenvalue, wrapped, n = 160.23one of them is positive definiteand it is the one that is nearer

A speedup with a ceiling of its own

At ρ = 0.5 the averaged circulant takes 5 conjugate gradient steps at n = 512 against an unpreconditioned 30 — and that 30 is where the unpreconditioned count stops. It reads 29, 28, 30, 30 at n = 64 to 512 and then 29, 28, 26, 27, 25 at every doubling out to 16,384, because κ has reached 99.9% of Szegő's limit and the count has nothing left to grow with.

structure · Preconditioning 357911110¹grid side meigenvalue of C⁻¹Awithin ½ of onethe cluster grows like the sidem = 4: inside of 169m = 6: inside of 3611m = 8: inside of 6413m = 10: inside of 10017the cluster grows with the sideand the spectrum with the area

Four orders of conditioning, and four steps

On a 10×10 grid the two-dimensional kernel's condition number runs from 62 at ρ = 0.5 to 818,561 at ρ = 0.98. The preconditioned step count over the same range runs 18, 21, 21, 22, 21, 19, 18, and the count of eigenvalues the preconditioner actually brings within half a unit of one does not move at all — it is 9, 11, 13, 17 at every correlation the figure will draw.

structure · Toeplitz 10⁻³10⁻²10⁻¹110⁻¹⁹10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹1 − ρbackward errorLevinson, Toeplitzelimination, ToeplitzLevinson, any kindelimination, any kindat ρ = 0.999Levinson, any perturbation2.9·10⁻¹⁷Levinson, Toeplitz only6·10⁻¹²the ratio between them2·10⁵diagonal defect of the first0.97the number that is reportedand the number that is asked about

The number that cannot rank them

Levinson and Gaussian elimination are indistinguishable on the backward error a library reports — every one of ninety-six measurements between 1.16·10⁻¹⁷ and 5.73·10⁻¹⁷. The structured backward error separates them by up to a hundredfold, in whichever direction the point happens to give. Only the forward error ranks them, and only because this family's exact answer is known.

structure · Structured backward error change in the preconditioned countseparable, circulant, 0.5 → 0.980isotropic, circulant, 0.5 → 0.98190.50.60.70.80.910306090120150180correlation ρconjugate gradient stepsSeparable, no preconditionerSeparable, circulantIsotropic, no preconditionerIsotropic, circulantdashed: no preconditionerthe flat count belonged to the separable kernel

The staircase a separable kernel builds

A block-circulant preconditioner took 18, 21, 22, 21, 19 and 18 steps on a 10 × 10 Toeplitz-block-Toeplitz system as the correlation rose from 0.5 to 0.98 and the unpreconditioned count rose from 43 to 178 — the parameter that makes the problem hard was the one the solver did not notice. That kernel factorises. The isotropic kernel with the same correlation along each axis does not, and on it the preconditioned count climbs 17, 22, 27, 29, 33, 36, while the preconditioner buys a factor of 1.4 where it bought ten. The reason is the spectrum's shape: a product of two one-dimensional spectra is a staircase of ten treads, and a kernel that is not a product gives a ramp of thirty-eight.

structure · Toeplitz size n163264128(L + s)²1 stepκu 1.2·10⁻¹²1 stepκu 1.9·10⁻¹¹1 stepκu 3.1·10⁻¹⁰1 stepκu 4.9·10⁻⁹(L + s)³1 stepκu 1.2·10⁻¹⁰1 stepκu 7.9·10⁻⁹1 stepκu 5.1·10⁻⁷1 stepκu 3.2·10⁻⁵(L + s)⁴1 stepκu 1.3·10⁻⁸1 stepκu 3.3·10⁻⁶2 stepsκu 8.4·10⁻⁴no first solveκu 2.2·10⁻¹(L + s)⁵3 stepsκu 1.3·10⁻⁶3 stepsκu 1.4·10⁻³no first solveκu 1.4·10⁰no first solveκu 1.4·10³(L + s)⁶3 stepsκu 1.3·10⁻⁴no first solveκu 5.6·10⁻¹no first solveκu 2.3·10³no first solveκu 9.5·10⁶κu: the wrap's condition number times the unit roundoffsteps are not a function of κu

Where one step stops being enough

One step of iterative refinement took the squared Laplacian's circulant-wrap solve to elimination's accuracy at every size, and the account was that each step multiplies the error by the wrap's condition number times the rounding, so one step suffices while that product is small. Raised to higher powers, the band tests the account and half of it holds: each step does contract by about κ(wrap)·u. The other half fails. The fifth power at sixteen points needs three steps with κ(wrap)·u near 10⁻⁶, where the third power at 128 points needs one with thirty times more, because the first solve starts up to a thousand times further from the answer than κ(wrap)·u says.

structure · Circulant

Named alongside it

The objects these essays reach for when they reach for this one.

Condition numberCirculant preconditionerClustered spectrumConjugate gradientsPreconditioningAsymptotic analysisExact inverseSymbolBackward errorCirculant matrixDiscrete fourier transformStructured perturbation

All concepts