Numerical Linear Algebra
where the algebra stops being the arithmetic
Structure, and the solver that cannot see it

A perturbation that keeps the symmetry

The smallest perturbation that makes a computed answer exact is the backward error. Ask for the smallest one that also keeps the problem's structure and the number can only go up — and measured on a palindromic quadratic it goes up by 1.17, while the structure the computed spectrum has lost is not in either number.
34 min read 29 figures Whose fault is itMeasured, not assertedAssertions that reject

Worth reading first: A nearby problem of the wrong kind · The exact answer to a nearby problem · A spectrum that comes in reciprocal pairs · The condition number is an amplifier.

A nearby problem of the wrong kind makes an uncomfortable point about the sentence this site is built on. A backward-stable computation returns the exact answer to a nearby problem — and nearby is measured in a norm over all matrices, while the problem posed may live in a much smaller set. A Toeplitz matrix perturbed by a general perturbation is not Toeplitz, so the nearby problem the analysis promises is not a problem of the kind that was asked about, and the promise is worth less than it sounds.

That essay leaves a question open: how much less? If the structured backward error — the smallest perturbation within the structure — were orders of magnitude larger than the unstructured one, then every structured problem on this site would need its analysis redone.

This essay measures it for a structure where the answer is clean, and then finds that the number was not where the damage was.

What a reciprocal pairing is worth: three ways to the small half of a palindromic spectrumA palindromic quadratic of size 6 whose spectrum spreads by two decades for every decade of b. The general solver returns the large eigenvalues to 5.52·10⁻¹⁵ at every stop and the small ones to 1.041·10⁻⁷ at the far end. Taking the reciprocals of the large ones instead returns the small ones to 4.89·10⁻¹⁵ — seven orders, for a division, out of a symmetry the solver discarded. The structure-preserving route, which enforces the pairing exactly, is the worst of the three on the eigenvalues themselves: 6.538·10⁻⁶, because each pair comes from one computed number and both members carry its error. Preserving a symmetry and using one are different acts with different prices.1357910⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴log₁₀ b, the couplingrelative errorsmall half, directstructure-preservingsmall half, by 1/λone divisionlarge half, direct5.5·10⁻¹⁵small half, direct10⁻⁷small half, by 1/λ4.9·10⁻¹⁵structure-preserving6.5·10⁻⁶the structure is not decorationit is where half the accuracy is
Fig. 1 The measurement that motivates the question: a palindromic spectrum whose small half is computed to seven digits and whose structure the computation has quietly lost.

The structure, and the perturbation that keeps it

A palindromic quadratic is Q(λ) = λ²A + λB + Aᵀ with B symmetric — the same matrix at both ends, so the polynomial reads the same backwards, and λ is an eigenvalue exactly when 1/λ is. The family here has A symmetric too, and its whole spectrum is available in closed form.

Given a computed pair (λ, x), the unstructured backward error is Tisseur’s

η = ‖Q(λ)x‖ / ((|λ|²‖A‖ + |λ|‖B‖ + ‖Aᵀ‖)‖x‖),

the smallest perturbation of the three coefficients severally for which the pair is exact. It puts no constraint on the shape of the perturbation, so the matrix it implies is generally neither symmetric nor palindromic.

The structured question asks for the smallest perturbation that keeps both. Rather than estimate it, one is constructed: move B alone, keep it symmetric, and require ΔBx = −r/λ where r = Q(λ)x. The minimum-norm symmetric matrix taking x to a given vector c is

ΔB = (c xᵀ + x cᵀ)/‖x‖² − (xᵀc) x xᵀ/‖x‖⁴,

and Q + ΔQ built from it is palindromic by construction, since only the middle coefficient moved and it stayed symmetric.

That gives an upper bound on the structured backward error, which is the direction that makes the comparison honest: an upper bound on the structured number against the exact unstructured one can only overstate the price of the structure.

Both halves of the construction are checked rather than assumed. ΔB is required to be symmetric to 10⁻¹² relative, and to map x to c to 10⁻⁸ relative — because a “structured backward error” computed from a perturbation that does not actually remove the residual is a number about nothing, and the check costs one matrix–vector product.

The measurement

Twelve eigenpairs, at n = 6 with the spectrum spread over eight decades:

worst ratio     1.41
median ratio    1.17
every pair's unstructured backward error    below 10⁻¹⁵

So respecting the structure costs a factor of 1.41 at worst and 1.17 typically. Not an order of magnitude, not a factor of ten — a factor of about √2, which for a quantity measured on a logarithmic scale is nothing at all.

The direction is not a surprise and the size is. A constrained minimum is at least the unconstrained one, so the ratio cannot be below 1; the finding is that the constraint is nearly inactive. Every pair a general solver returns is exact for a palindromic problem a rounding away, which is what the structure-conscious reader wanted to be told and had no reason to expect.

Which means the backward error is not where the damage is

That result is comfortable and it is also the setup, because the same computation is losing something real.

The spectrum a general solver returns on this problem departs from being closed under λ ↦ 1/λ by 1.0·10⁻⁷ at the far end of the sweep — seven orders above the rounding level — and the small half of the spectrum carries exactly that error. The details are in the polynomial field’s essay, and the point here is the accounting:

  • The backward error is 10⁻¹⁵, structured or not.
  • The reciprocal pairing is out by 10⁻⁷.
  • Nothing in the first number predicts the second.

A backward error measures how far the problem has to move to make the answer exact. It says nothing about whether the answer has the properties the exact answer has. And a symmetry of the spectrum is exactly that kind of property: it is a relation among the computed numbers, not a statement about any one of them, so no per-eigenpair quantity can detect its loss.

Two failures the phrase covers, and they are opposite

Putting this beside its ancestor gives a pair worth keeping.

The Toeplitz case. The nearby problem is not of the right kind, so the promise is weaker than it appears. Structured backward error is the right thing to compute and it can be substantially larger — the condition number of the model prices the matching structured conditioning, and the two together are what a structured analysis needs.

The palindromic case. The nearby problem is of the right kind, at essentially no extra cost, and the analysis is as strong as it looks. And the answer still fails to have a property the exact answer has.

So “does the structure matter?” is two questions wearing one phrase. Whether the perturbation stays in the set is one; whether the answer keeps the set’s consequences is another. The first has a number and here the number is 1.17. The second has no number at all until somebody measures the consequence directly — which for a reciprocal spectrum costs one division per eigenvalue, and is the thing this site would add to a solver’s output if it could add one.

What “structured” has to mean to be checkable

There is a loose way of using the word and a tight one, and the measurement above only means anything under the tight one.

Loosely, a structured backward error is “the smallest perturbation that respects the structure”, which is a variational problem with an infimum that may or may not be attained and which for many structures has no closed form. Tightly, it is a number produced by a construction: here is a perturbation, here is a check that it has the structure, here is a check that it makes the computed pair exact, and here is its norm. The second is an upper bound on the first and it is the only one that can be printed with confidence.

This site has taken the second route before and for the same reason. Proving the answer is in the box is an interval computation whose output is a certificate rather than an estimate — the answer is in this box, and the box was produced by arithmetic that can be re-checked. A constructed perturbation is the same shape of object: a witness rather than a claim, verified by two assertions that would fail if the construction were wrong.

And the assertions are not decorative. The natural first attempt at ΔB — the rank-one c xᵀ/‖x‖² — maps x to c correctly and is not symmetric, so it is a perturbation of a problem that is not palindromic, and its norm is a smaller number about the wrong set. The symmetrised form above costs one more term and the difference between the two is exactly the thing being measured. A gate that checked only the residual would have accepted the wrong one.

The size of the effect, and why √2

A word on why the ratio comes out where it does, since a measured constant with no explanation is half a finding.

The symmetric minimum-norm perturbation with ΔBx = c has Frobenius norm about √2 times ‖c‖/‖x‖ when c is orthogonal to x, and exactly ‖c‖/‖x‖ when c is parallel to it. The residual r of a computed eigenpair is nearly orthogonal to x — it is what is left after the eigen-direction has been removed — so the worst case is the orthogonal one and the ratio is √2 = 1.414. Measured worst: 1.414.

So the constant is not an accident of the family, and it is not a bound that happens to be loose. It is the price of requiring a symmetric perturbation instead of an arbitrary one, in closed form, and it says the constraint costs a factor of at most √2 for any problem of this shape. That is the kind of result worth having: a measured number that turns out to be a theorem, checked on twelve pairs rather than assumed.

Why only B moves

A fair objection: the constructed perturbation moves the middle coefficient and leaves A alone. Might a perturbation that moves A too be smaller?

It might, and the bound would then be tighter, and the measured ratio would fall further towards one — which strengthens the finding rather than weakening it, since the ratio is already 1.17 with a deliberately restricted construction. Moving A is also harder to keep honest: A appears twice, once transposed, so a perturbation ΔA changes the polynomial in two places and the residual it removes is (λ²ΔA + ΔAᵀ)x rather than a single term. That is soluble and it is more machinery than the finding needs.

The general form of the trade is worth stating, because it recurs whenever a structured quantity is computed: an explicit construction gives an upper bound and is checkable; a variational characterisation gives the exact value and is another optimisation problem. When the upper bound already says the constraint is nearly free, the exact value is not worth the second problem.

What this adds to the field

The structure field on this site is a collection of matrices described by fewer numbers than they contain — a circulant, a Toeplitz limit, a Kronecker sum — and its recurring question is what an algorithm ignoring the description gives up.

The answers so far have been about cost: a general solver spends n³ on a problem handed to it in n, which is what the matrix that is one row prices and what a limit the matrix never reaches qualifies. This one is about stability, and it is the first negative result in the collection: on at least one structure, ignoring it costs nothing measurable in the backward error. That is worth having recorded, because the intuition runs the other way and the intuition is what gets acted on.

The positive half is that the loss moved somewhere a backward error cannot see, and that is a better warning than a large number would have been. A large structured backward error would have told a reader to use a structured method. What was found instead tells them to measure the structure of the answer, which is a different and cheaper habit — one division here, one reciprocity check, printed beside the residual that was already being printed.

What a structured analysis is actually for

It is worth ending on what the measurement does not license, because “the structure costs 1.17” could be misread as “structure does not matter”.

A structured backward error answers one question: is the answer exact for a problem of the right kind? Here, yes, at essentially no extra cost. That is a real and useful result — it means a general eigensolver can be used on a palindromic problem without an asterisk in the stability argument, which is not obvious and had to be measured.

It does not answer three others.

Is the computed answer usable? Only if the properties it needs to have survive, and the reciprocal pairing does not.

Is the structured problem better conditioned than the unstructured one? The condition number of the model is about exactly that, and the answer there is often yes by a large factor — which is a reason to think structurally that has nothing to do with backward errors.

And is there a cheaper algorithm? Half the size, in this case, which is the ordinary reason anybody exploits a structure and is untouched by any of this.

So the finding is narrow and worth having: on this structure, one of the four questions has a comfortable answer, and the comfortable answer is the one people quote when they mean the others.

The two numbers, side by side

Ending with the arithmetic in one place, because the essay’s whole argument is a comparison of two quantities that are usually reported as one.

For a computed eigenpair of this palindromic quadratic:

unstructured backward error       below 10⁻¹⁵, every pair
structured backward error         at most 1.41 times that, median 1.17
departure from λλ′ = 1            up to 1.0·10⁻⁷

The first two are within a hair of each other and both are excellent. The third is seven orders worse and is not a backward error at all — it is a property of the set of computed numbers, which no per-pair quantity can express.

The habit that follows is small and general. When a problem has a structure, ask two questions rather than one: whether the nearby problem the analysis promises is of the right kind, and whether the answer has the properties the exact answer has. The first is what a structured backward error measures and it is often reassuring. The second usually has no established quantity attached to it, which is precisely why it is worth constructing one — here, one division per eigenvalue — and printing it beside the residual.

One more thing the construction shows

A small observation from building the perturbation, worth recording because it is the sort of detail that decides whether a structured quantity means anything.

ΔB is required to be symmetric, and the minimum-norm symmetric matrix taking x to c is not the obvious rank-one c xᵀ/‖x‖². The obvious one moves x correctly and is not symmetric, so the “structured” backward error computed from it would be a number about a perturbation the structure forbids — smaller than the truth, and in the flattering direction.

The correct construction has a rank-two form with a correction term, and the difference between the two norms is exactly the factor of up to √2 the essay measures. So the whole finding lives in that correction: without it the ratio would come out at one, the structure would look entirely free, and the number would be wrong.

That is why both properties are asserted rather than assumed. A gate that checked only “does the perturbation remove the residual” accepts the wrong matrix, and the wrong matrix gives a better answer — which is the failure mode this site names most often and the reason the checks in these libraries are written against the thing that must fail rather than the thing that should pass.

At other settings

What a reciprocal pairing is worth: three ways to the small half of a palindromic spectrumA palindromic quadratic of size 3 whose spectrum spreads by two decades for every decade of b. The general solver returns the large eigenvalues to 2.54·10⁻¹⁵ at every stop and the small ones to 3.242·10⁻¹³ at the far end. Taking the reciprocals of the large ones instead returns the small ones to 2.62·10⁻¹⁵ — seven orders, for a division, out of a symmetry the solver discarded. The structure-preserving route, which enforces the pairing exactly, is the worst of the three on the eigenvalues themselves: 5.871·10⁻⁷, because each pair comes from one computed number and both members carry its error. Preserving a symmetry and using one are different acts with different prices.1357910⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴log₁₀ b, the couplingrelative errorsmall half, directstructure-preservingsmall half, by 1/λone divisionlarge half, direct2.5·10⁻¹⁵small half, direct3.2·10⁻¹³small half, by 1/λ2.6·10⁻¹⁵structure-preserving5.9·10⁻⁷the structure is not decorationit is where half the accuracy is
Fig. 2 Three pairs rather than six, and the same ordering of the three routes.
What a reciprocal pairing is worth: three ways to the small half of a palindromic spectrumA palindromic quadratic of size 10 whose spectrum spreads by two decades for every decade of b. The general solver returns the large eigenvalues to 7.31·10⁻¹⁵ at every stop and the small ones to 7.925 at the far end. Taking the reciprocals of the large ones instead returns the small ones to 4.56·10⁻¹⁵ — seven orders, for a division, out of a symmetry the solver discarded. The structure-preserving route, which enforces the pairing exactly, is the worst of the three on the eigenvalues themselves: 2.468·10⁻⁵, because each pair comes from one computed number and both members carry its error. Preserving a symmetry and using one are different acts with different prices.1357910⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴log₁₀ b, the couplingrelative errorsmall half, directstructure-preservingsmall half, by 1/λone divisionlarge half, direct7.3·10⁻¹⁵small half, direct7.9small half, by 1/λ4.6·10⁻¹⁵structure-preserving2.5·10⁻⁵the structure is not decorationit is where half the accuracy is
Fig. 3 And ten.
The 12 eigenvalues of a palindromic quadratic, in 6 pairs whose products are oneλ²A + λB + Aᵀ with A and B symmetric reads the same backwards, so λ is an eigenvalue exactly when 1/λ is. The axis is log₁₀|λ|, the marks are the computed eigenvalues and each arc joins a pair; the vertical line is |λ| = 1, about which the whole picture is symmetric. The spectrum spans 9.56 decades at b = 10⁴. Measured, the general solver's spectrum departs from being closed under λ ↦ 1/λ by 3.27·10⁻⁹, and the structured route's — one symmetric generalised eigenvalue problem of size 6 rather than an unsymmetric one of size 12 — by 2.21·10⁻¹⁶, which is the rounding level and is by construction.-5-3.20611-1.412210.3816782.175573.969460log₁₀ |λ||λ| = 1λλ′ = 1, in the algebrapairs6decades of spectrum9.6pairing error, general3.3·10⁻⁹pairing error, structured2.2·10⁻¹⁶a symmetry the solver never knew aboutand the half of the answer it decides
Fig. 4 The symmetry itself, with each eigenvalue joined to its partner.
The 12 eigenvalues of a palindromic quadratic, in 6 pairs whose products are oneλ²A + λB + Aᵀ with A and B symmetric reads the same backwards, so λ is an eigenvalue exactly when 1/λ is. The axis is log₁₀|λ|, the marks are the computed eigenvalues and each arc joins a pair; the vertical line is |λ| = 1, about which the whole picture is symmetric. The spectrum spans 21.6 decades at b = 10¹⁰. Measured, the general solver's spectrum departs from being closed under λ ↦ 1/λ by 1.04·10⁻⁷, and the structured route's — one symmetric generalised eigenvalue problem of size 6 rather than an unsymmetric one of size 12 — by 2.32·10⁻¹⁶, which is the rounding level and is by construction.-11-7.20611-3.412210.3816784.175577.969460log₁₀ |λ||λ| = 1λλ′ = 1, in the algebrapairs6decades of spectrum22pairing error, general10⁻⁷pairing error, structured2.3·10⁻¹⁶a symmetry the solver never knew aboutand the half of the answer it decides
Fig. 5 And at the spread where the pairing error reaches 10⁻⁷.
The same three schemes on a problem with no layer in itWorst nodal error against the grid size, both axes logarithmic, for a manufactured smooth solution on the identical operator at ε = 0.005. Adding no diffusion gives 0.0016, 4·10⁻⁴, 10·10⁻⁵, falling by four at each refinement. The tuned diffusion gives 0.067, 0.022, 0.0061 — 42 times worse at the coarsest grid, and falling more slowly.10²10⁻⁴10⁻³10⁻²10⁻¹grid points nworst nodal errorupwindtunedcentralthe same tuning, another problemtuned ÷ central at n = 3142tuned ÷ central at n = 12761central's error at the finest grid10·10⁻⁵exact on the problem it was derived fromand harmful on the one beside it
Fig. 6 The essay this one answers, where the nearby problem is not of the right kind.
The two perturbations that make one computed solution exact, on a 12×12 Toeplitz systemA Kac–Murdock–Szegő matrix at ρ = 0.95, solved by Levinson's recursion. Every backward-error claim on this site says the computed answer solves a nearby problem exactly, and the nearby problem is the top matrix: the smallest perturbation of any kind, 2.18·10⁻¹⁷ relative, rank one, and constant along 0.98 of the way to none of its diagonals. The bottom matrix is the smallest perturbation that is itself a symmetric Toeplitz matrix — the same kind of object the problem was posed with — and it is 3.72·10⁻¹², larger by a factor of 1.71·10⁵. Both explain the same computed answer exactly. Only one of them is a problem anybody could have posed.the smallest perturbation of any kind — 2.18·10⁻¹⁷the smallest Toeplitz one — 3.72·10⁻¹²both exact for the same x̂smallest of any kind2.2·10⁻¹⁷smallest Toeplitz one3.7·10⁻¹²the price of the constraint1.7·10⁵diagonal defect, unconstrained0.98an exact answer to a nearby problemof a kind nobody posed
Fig. 7 What shape a general perturbation has, against the shape the structure allows.
Backward error with and without the structure, for Levinson and for elimination, n = 12Both solvers are backward stable on this family by the usual measure: the smallest perturbation of any kind that explains either answer stays below 3.1·10⁻¹⁷ at every ρ, and the two curves are indistinguishable. Insisting the perturbation be a symmetric Toeplitz matrix — the kind of object the problem was posed with — lifts both by orders, and at ρ = 0.999 Levinson's rises by a factor of 2.48·10⁶. Neither number is alarming in absolute terms; what is worth carrying is that the reassuring one is the one that is reported, and the two are not measuring the same thing.10⁻³10⁻²10⁻¹110⁻¹⁹10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹1 − ρbackward errorLevinson, Toeplitzelimination, ToeplitzLevinson, any kindelimination, any kindat ρ = 0.999Levinson, any perturbation3.1·10⁻¹⁷Levinson, Toeplitz only7.6·10⁻¹¹the ratio between them2.5·10⁶diagonal defect of the first0.97the number that is reportedand the number that is asked about
Fig. 8 The backward error a solver actually achieves.
Two perturbation bounds and the error that was measured, on a 8×8 matrix spread over 8 decades of unitsThree curves against the size of an entrywise relative perturbation. The normwise bound κ_∞·ε is a valid bound and sits 4·10⁷ times above the componentwise one cond(A, x)·ε, which is also a bound and is nearly attained by the worst of forty random perturbations at each size.10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1relative size of the entrywise perturbationrelative forward errorκ_∞ · εcond(A,x) · εmeasuredboth bounds holdκ_∞(A)1.9·10⁸cond(A, x)4.8ratio of the bounds4·10⁷both curves above the data are boundsand only one of them is a measurement
Fig. 9 A second measure of nearness, which sees what a norm hides.
The diagonals of T, and what each circulant puts in their place (n = 16, ρ = 0.9)Entry value against the diagonal index. The Toeplitz matrix's own diagonals fall geometrically as ρ^k. The wrapped circulant follows them to the halfway point and then jumps to the far diagonal, discarding what it passed. The averaged one blends the two throughout, weighted by how many entries each contributes — and the result is nearer to T in the Frobenius norm, 0.2112 against 0.2877.0246810121400.250.50.751diagonal indexentryT's diagonalswrappedaveragedtwo routes to one circulantformula against the fit3.3·10⁻¹⁶‖C − T‖/‖T‖, averaged0.21‖C − T‖/‖T‖, wrapped0.29one discards a diagonalthe other weights both
Fig. 10 A structure described by one row, from the field’s first essay.
κ of the ρ = 0.5 Toeplitz family, against the limit it never reachesThe condition number of the n×n section of the Kac–Murdock–Szegő matrix ρ^|i−j| at ρ = 0.5, plotted against the size on logarithmic axes, with Szegő's asymptotic value ((1+ρ)/(1−ρ))² = 9 drawn as a horizontal line. The measured curve climbs towards it from below and reaches 99.9% of it at n = 128.10¹10²10¹size ncondition numberlimit 9measureda limit, as a fraction of itselfreached at n = 1281still to go0.0013κ at n = 8, as a fraction0.83every point is below the line and none of them is on itthe limit is not a value
Fig. 11 A limit a structured matrix approaches and never reaches.
One quadratic eigenvalue problem in 9 systems of units: what the solver reports and what the answer is worthAn overdamped chain of 8 masses, with λ replaced by γμ so that the coefficients become (γ²M, γC, K). That substitution is exact in both directions and divides the spectrum by γ exactly, so the closed form is still available and every error here is measured against it. The backward error of the eigenpair for the LINEARISED MATRIX — the residual a solver's own error analysis is about — is 6.76·10⁻¹⁶ at γ = 1 and 7.59·10⁻¹³ at γ = 108 — it moves by a factor of 1928 while the other two move by 1.68·10¹⁰. The backward error for the QUADRATIC, which is what the person who posed the problem is entitled to, grows by 8.76·10¹⁰ across the same sweep, and the forward error follows it: 7.49·10⁻¹⁴ to 0.00126. Nothing went wrong with the solver at any stop.0246810⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹log₁₀ γ, the change of unitsrelative errorforward errorη, the quadraticη, the linearisationagainst a closed formη(linearisation), worst7.6·10⁻¹³η(quadratic), worst1.2·10⁻⁴forward error, worst0.0013coefficient spread4.2·10¹⁵the solver is right at every stopabout a problem nobody asked
Fig. 12 The unstructured backward error in the field this problem comes from.
The condition number the problem has, and the one the solver's error analysis is written againstThe same eigenvalue of the same overdamped chain of 8 masses, in seven systems of units. Its condition number as an eigenvalue of the QUADRATIC — Tisseur's, with the three coefficient norms in the numerator and yᵀQ′(λ)x in the denominator — is 4.98 at γ = 1 and 4.98 at γ = 10⁶, a spread of 1 over six decades: it cannot move, because a change of units is not a change of problem. Its condition number as an eigenvalue of the LINEARISED MATRIX runs 49.66 to 7.844·10¹¹, a factor of 1.58·10¹⁰. The forward error follows the second one, and the first one is the honest description of the problem — so the substitution has manufactured an ill conditioning that belongs to the algorithm rather than to the question.012345610⁻¹10²10⁵10⁸10¹¹log₁₀ γ, the change of unitscondition numberthe linearisationthe quadraticone problem, two amplifiersκ(quadratic), first5κ(quadratic), last5κ(linearisation), last7.8·10¹¹how far the first moved1the problem is as well conditioned as everand the method is not
Fig. 13 And the conditioning that goes with it.
The 16 real eigenvalues of an overdamped chain, in two groups of 8, with the certificate between themA chain of 8 masses with C = 8K, which is above the critical damping 5.75877 = 1/sin(π/2(n+1)), so the quadratic is hyperbolic and every one of its 16 eigenvalues is real. The vertical line is the μ at which Q(μ) is negative definite — a Cholesky that completes, and the whole proof that the spectrum is real. It also lies in the gap: exactly 8 eigenvalues above it and 8 below, with a gap of 0.6698 between the two groups. One factorisation answers both questions, which is the second thing a boolean would not have carried.-33-28.2505-23.5009-18.7514-14.0018-9.25229-4.502750eigenvalueQ(μ) ≺ 0one Cholesky, two answersabove the certificate8below it8the gap0.67critical β for this n5.8the spectrum is real by classnot by outcome
Fig. 14 A different structure, constraining where the eigenvalues are rather than how they pair.
The two 6×6 matrices of a Sylvester equation, and the 36×36 matrix it meansA and B are 6×6 with 11 nonzeros each. The coefficient matrix of the map X ↦ AX + XB is 36×36 with 96 nonzeros, drawn at the same scale so the ratio is visible rather than quoted. Bartels and Stewart's algorithm never forms it: two Schur reductions and a back-substitution give the same X to 1.7·10⁻¹⁶, and that X satisfies AX + XB = C to 2·10⁻¹⁶.A6×6B6×6I ⊗ A + Bᵀ ⊗ I36×36one equation, two objectsentries in A and B72entries in the coefficient matrix1296two routes, relative gap1.7·10⁻¹⁶‖AX + XB − C‖/‖C‖2·10⁻¹⁶the small squares are the problemand the large one is the notation
Fig. 15 A matrix equation whose structure decides what may be formed.
The 216 eigenvalues of the 3-dimensional Laplacian on 6 points a side, computed against their closed formThe matrix has 216 rows and 46,656 entries, and is a sum of 3 Kronecker products of one 6 × 6 matrix — 108 numbers. Its eigenvalues are every sum of 3 numbers drawn from 4sin²(kπ/2(n+1)), so the whole spectrum is written down before anything runs. The line is that closed form and the marks are what a Jacobi decomposition of the assembled matrix returns; the largest disagreement anywhere is 7.08·10⁻¹³. The smallest eigenvalue is 0.5942 and the largest 11.41, so the condition number is 19.2 — which is the part the structure does not help with.03672108144180216024681012eigenvalues in orderλthe closed formmarks: the assembled matrix, decomposeda spectrum nobody computedrows of the matrix216numbers that describe it108λ smallest0.59λ largest11worst |computed − exact|7.1·10⁻¹³the matrix is never neededand neither is its decomposition
Fig. 16 And a spectrum known before the matrix is assembled.
What a reciprocal pairing is worth: three ways to the small half of a palindromic spectrumA palindromic quadratic of size 6 whose spectrum spreads by two decades for every decade of b. The general solver returns the large eigenvalues to 5.52·10⁻¹⁵ at every stop and the small ones to 1.041·10⁻⁷ at the far end. Taking the reciprocals of the large ones instead returns the small ones to 4.89·10⁻¹⁵ — seven orders, for a division, out of a symmetry the solver discarded. The structure-preserving route, which enforces the pairing exactly, is the worst of the three on the eigenvalues themselves: 6.538·10⁻⁶, because each pair comes from one computed number and both members carry its error. Preserving a symmetry and using one are different acts with different prices.1357910⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴log₁₀ b, the couplingrelative errorsmall half, directstructure-preservingsmall half, by 1/λone divisionlarge half, direct5.5·10⁻¹⁵small half, direct10⁻⁷small half, by 1/λ4.9·10⁻¹⁵structure-preserving6.5·10⁻⁶the structure is not decorationit is where half the accuracy is
Fig. 17 The measurement the structured question is asked about.
The 12 eigenvalues of a palindromic quadratic, in 6 pairs whose products are oneλ²A + λB + Aᵀ with A and B symmetric reads the same backwards, so λ is an eigenvalue exactly when 1/λ is. The axis is log₁₀|λ|, the marks are the computed eigenvalues and each arc joins a pair; the vertical line is |λ| = 1, about which the whole picture is symmetric. The spectrum spans 5.56 decades at b = 100. Measured, the general solver's spectrum departs from being closed under λ ↦ 1/λ by 5.86·10⁻¹³, and the structured route's — one symmetric generalised eigenvalue problem of size 6 rather than an unsymmetric one of size 12 — by 1.88·10⁻¹⁶, which is the rounding level and is by construction.-3-1.87277-0.7455490.3816761.50892.636130log₁₀ |λ||λ| = 1λλ′ = 1, in the algebrapairs6decades of spectrum5.6pairing error, general5.9·10⁻¹³pairing error, structured1.9·10⁻¹⁶a symmetry the solver never knew aboutand the half of the answer it decides
Fig. 18 The symmetry at a narrower spread, where the computed spectrum nearly has it.
The 12 eigenvalues of a palindromic quadratic, in 6 pairs whose products are oneλ²A + λB + Aᵀ with A and B symmetric reads the same backwards, so λ is an eigenvalue exactly when 1/λ is. The axis is log₁₀|λ|, the marks are the computed eigenvalues and each arc joins a pair; the vertical line is |λ| = 1, about which the whole picture is symmetric. The spectrum spans 17.6 decades at b = 10⁸. Measured, the general solver's spectrum departs from being closed under λ ↦ 1/λ by 9.08·10⁻⁸, and the structured route's — one symmetric generalised eigenvalue problem of size 6 rather than an unsymmetric one of size 12 — by 2.16·10⁻¹⁶, which is the rounding level and is by construction.-9-5.87277-2.745550.3816783.50896.636130log₁₀ |λ||λ| = 1λλ′ = 1, in the algebrapairs6decades of spectrum18pairing error, general9.1·10⁻⁸pairing error, structured2.2·10⁻¹⁶a symmetry the solver never knew aboutand the half of the answer it decides
Fig. 19 And at a wider one, where it does not.
How much a perturbation of the right-hand side is amplified, κ = 10⁴The cumulative distribution of the amplification factor over two hundred random perturbation directions, with the condition number marked as the upper limit.110¹10²10³10⁴10⁵00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10000worst found 76206×6, 200 directionsmedian reaches 0.29 of κ
Fig. 20 The amplifier a backward error is multiplied by to give a forward one.
The same three schemes on a problem with no layer in itWorst nodal error against the grid size, both axes logarithmic, for a manufactured smooth solution on the identical operator at ε = 0.001. Adding no diffusion gives 0.0016, 4·10⁻⁴, 10⁻⁴, falling by four at each refinement. The tuned diffusion gives 0.092, 0.043, 0.018 — 57 times worse at the coarsest grid, and falling more slowly.10²10⁻⁴10⁻³10⁻²10⁻¹grid points nworst nodal errorupwindtunedcentralthe same tuning, another problemtuned ÷ central at n = 3157tuned ÷ central at n = 127182central's error at the finest grid10⁻⁴exact on the problem it was derived fromand harmful on the one beside it
Fig. 21 A smaller perturbation of the same kind, on the essay this one answers.
Two perturbation bounds and the error that was measured, on a 12×12 matrix spread over 8 decades of unitsThree curves against the size of an entrywise relative perturbation. The normwise bound κ_∞·ε is a valid bound and sits 3.7·10⁷ times above the componentwise one cond(A, x)·ε, which is also a bound and is nearly attained by the worst of forty random perturbations at each size.10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1relative size of the entrywise perturbationrelative forward errorκ_∞ · εcond(A,x) · εmeasuredboth bounds holdκ_∞(A)3.1·10⁸cond(A, x)8.5ratio of the bounds3.7·10⁷both curves above the data are boundsand only one of them is a measurement
Fig. 22 A componentwise measure, which sees a structure a norm cannot.
The smallest eigenvalue of each circulant, ρ = 0.95Smallest eigenvalue against the matrix size on a linear vertical axis with zero marked. The wrapped circulant runs -0.6548, -0.4258, -0.1730, -0.0128, 0.0242 — negative at the small sizes and crossing zero by n = 256. The averaged one runs 0.0431, 0.0382, 0.0332, 0.0295, 0.0276: falling towards zero and never reaching it.10²0size nsmallest eigenvaluezerowrapped (Strang)averaged (T. Chan)an average of positives is positivewrapped, n = 16-0.65averaged, n = 160.043averaged, n = 2560.028a choice between two diagonals can be negativean average of them cannot
Fig. 23 A structured matrix whose distance to a boundary is the quantity of interest.
Conjugate gradient steps on the ρ = 0.9 Toeplitz familyIteration count against the matrix size, drawn on a logarithmic size axis. Unpreconditioned: 20, 35, 54, 82, 117. With the wrapped circulant: 20, 45, 26, 7, 4. With the averaged one: 7, 9, 10, 10, 9, which is the O(1) the theory promises and the wrapped one does not deliver until its smallest eigenvalue has become positive.10²020406080100120size niterationsno preconditionerwrapped (Strang)averaged (T. Chan)both are circulant approximations‖C − T‖/‖T‖, averaged0.21‖C − T‖/‖T‖, wrapped0.29smallest eigenvalue, wrapped, n = 16-0.4one of them is positive definiteand it is the one that is nearer
Fig. 24 Two structured approximations of one matrix, and what separates them.
The Kronecker spectrum of the inverse of a Kronecker sum on 8 points a sideA Kronecker product B ⊗ C, read as a four-index array and cut between its two index pairs, is exactly rank one. The inverse of T ⊕ T is rank 8 at the same cut, so the format is not closed under inversion — which is why a solve in it goes through the eigenbasis rather than through an inverse. What the spectrum says is that it is nearly closed: the singular values are 1, 0.19, 0.0262, 0.00214 of the first, and the number of Kronecker terms needed runs 3, 5, 6, 7, 8, 8 at 10⁻², 10⁻⁴, 10⁻⁶, 10⁻⁸, 10⁻¹⁰ and 10⁻¹². That is 0.50 terms a decade — the same shape, and nearly the same number, as the 0.554 columns a decade the hierarchy field measures for a kernel block, arrived at from a different direction entirely.024681012141610⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹index of the singular value at the cutσ ⁄ σ₁eight digits10^-4: 5 Kronecker terms10^-8: 7 Kronecker terms10^-12: 8 Kronecker termsnot closed, and nearly closedrank at the cut8a Kronecker product's1terms at 10⁻⁴5terms at 10⁻⁸7terms a decade0.5the inverse leaves the formatby half a term a decade
Fig. 25 A structure that the inverse does not belong to.
κ of the 0.8 kernel on m×m grids, against its two-dimensional limitCondition number against the grid side on a logarithmic vertical axis, with the asymptotic value ((1+ρ)/(1−ρ))⁴ = 6561 drawn as a horizontal line. The measured values are 581, 1196, 1794, 2337, reaching 35.6% of the limit on the largest grid — where the one-dimensional section of the same length reaches far more.4681010³10⁴grid side mκlimit 6561measured κthe symbol multipliesthe limit, from the symbol6561κ at 10×102337share of the limit reached0.36the limit is the square of the one-dimensional oneand it is further away
Fig. 26 And a limit a structured family approaches from inside.
One quadratic eigenvalue problem in 5 systems of units: what the solver reports and what the answer is worthAn overdamped chain of 8 masses, with λ replaced by γμ so that the coefficients become (γ²M, γC, K). That substitution is exact in both directions and divides the spectrum by γ exactly, so the closed form is still available and every error here is measured against it. The backward error of the eigenpair for the LINEARISED MATRIX — the residual a solver's own error analysis is about — is 6.76·10⁻¹⁶ at γ = 1 and 7.81·10⁻¹⁵ at γ = 104 — it moves by a factor of 19.8 while the other two move by 1.14·10⁵. The backward error for the QUADRATIC, which is what the person who posed the problem is entitled to, grows by 1.02·10⁵ across the same sweep, and the forward error follows it: 7.49·10⁻¹⁴ to 8.57·10⁻⁹. Nothing went wrong with the solver at any stop.0123410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹log₁₀ γ, the change of unitsrelative errorforward errorη, the quadraticη, the linearisationagainst a closed formη(linearisation), worst7.8·10⁻¹⁵η(quadratic), worst1.4·10⁻¹⁰forward error, worst8.6·10⁻⁹coefficient spread4.2·10⁷the solver is right at every stopabout a problem nobody asked
Fig. 27 The unstructured backward error, over four decades of units.
What a reciprocal pairing is worth: three ways to the small half of a palindromic spectrumA palindromic quadratic of size 8 whose spectrum spreads by two decades for every decade of b. The general solver returns the large eigenvalues to 4.94·10⁻¹⁵ at every stop and the small ones to 4.533·10⁻⁴ at the far end. Taking the reciprocals of the large ones instead returns the small ones to 2.82·10⁻¹⁵ — seven orders, for a division, out of a symmetry the solver discarded. The structure-preserving route, which enforces the pairing exactly, is the worst of the three on the eigenvalues themselves: 9.185·10⁻⁶, because each pair comes from one computed number and both members carry its error. Preserving a symmetry and using one are different acts with different prices.1357910⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴log₁₀ b, the couplingrelative errorsmall half, directstructure-preservingsmall half, by 1/λone divisionlarge half, direct4.9·10⁻¹⁵small half, direct4.5·10⁻⁴small half, by 1/λ2.8·10⁻¹⁵structure-preserving9.2·10⁻⁶the structure is not decorationit is where half the accuracy is
Fig. 28 Eight pairs, and the same three curves.
The 12 eigenvalues of a palindromic quadratic, in 6 pairs whose products are oneλ²A + λB + Aᵀ with A and B symmetric reads the same backwards, so λ is an eigenvalue exactly when 1/λ is. The axis is log₁₀|λ|, the marks are the computed eigenvalues and each arc joins a pair; the vertical line is |λ| = 1, about which the whole picture is symmetric. The spectrum spans 13.6 decades at b = 10⁶. Measured, the general solver's spectrum departs from being closed under λ ↦ 1/λ by 6.56·10⁻⁸, and the structured route's — one symmetric generalised eigenvalue problem of size 6 rather than an unsymmetric one of size 12 — by 1.78·10⁻¹⁶, which is the rounding level and is by construction.-7-4.53944-2.078880.3816782.842245.30280log₁₀ |λ||λ| = 1λλ′ = 1, in the algebrapairs6decades of spectrum14pairing error, general6.6·10⁻⁸pairing error, structured1.8·10⁻¹⁶a symmetry the solver never knew aboutand the half of the answer it decides
Fig. 29 And the spread at which the pairing error is already 10⁻⁸.

Where this goes next

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. 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. -5-3.20611-1.412210.3816782.175573.969460log₁₀ |λ||λ| = 1λλ′ = 1, in the algebrapairs6decades of spectrum9.6pairing error, general3.3·10⁻⁹pairing error, structured2.2·10⁻¹⁶a symmetry the solver never knew aboutand the half of the answer it decides A spectrum that comes in reciprocal pairs A palindromic quadratic reads the same backwards, so λ is an eigenvalue exactly when 1/λ is. A general solver discards that, computes the large half of the spectrum perfectly and the small half to seven digits — and the small half is a division away from being perfect too.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

Backward errorPalindromic quadraticPerturbationQuadratic eigenvalue problemReciprocal pairStructure preservingStructured backward error