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

Two near-zeros cost less than one

Solve a well-conditioned tridiagonal matrix through a nearly singular wrap and the correction's accuracy is not set by how singular the wrap is. At κ = 4·10⁷ one wrap returns the answer to 8.8·10⁻¹¹ — better than κ·u — and another, at κ = 3.8·10⁷, returns it to 3.3·10⁻⁶. The difference is how many of its samples sit near the symbol's zeros. A real wrap lands on a conjugate pair, a rank-two correction absorbs the pair exactly, and its two-by-two system has condition number 1.00.
23 min read 7 figures Whose fault is itTwo routes to a numberMeasured, not assumed

Worth reading first: The matrix that is one row.

The circulant the problem did not contain solved T = tridiag(−1, 2 + σ, −1) through its periodic neighbour by a rank-two correction, and found the answer losing digits in proportion to the square of the neighbour’s condition number. Two amplifications multiplied: the intermediate solve was larger than the answer by about 1/(nσ), and the two-by-two capacitance matrix had condition number exactly 4/(nσ). Moving the two corner entries’ sign — the anti-periodic wrap — moved the wrap’s samples half a step off the symbol’s zero and took all of the loss away.

That leaves a rule that sounds complete: the wrap’s conditioning is the danger, so choose the wrap whose samples keep farthest from the symbol’s zeros. This essay tests it on a symbol with two zeros instead of one, and the rule turns out to be right about which wrap to choose and wrong about why. A nearly singular wrap can cost the correction four orders of magnitude, or nothing at all, at the same condition number.

The correction's forward error against the distance of the twist from the landing twist, three zeros, n = 64Forward error, median of five answers, of the rank-two correction through a twisted wrap of size 64, against how far the twist is from the one that lands a sample exactly on the symbol's zero, from 10⁻⁷ to 10⁻¹·⁵ of a turn, on logarithmic axes. Three symbols: a simple zero landed on at twist 0, where its mirror image is landed on at the same time; a simple zero landed on at 0.3 of a turn, where it is not; and the double zero of 2 − 2cos θ. At 10⁻⁶ of a turn the first two wraps have κ 4.1·10⁷ and 3.8·10⁷; the capacitance matrix has κ 1 and 9.1·10⁵; the forward errors are 8.8·10⁻¹¹ and 3.3·10⁻⁶.-7-6-5-4-3-210⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110²10⁴log₁₀ of the twist's distance from landing, in turnsrelative forward errorsimple zero, landed on at 0simple zero, landed on at 0.3double zero, d = 2n = 64, twist 10⁻⁵ of a turn from landingpair: error, κ(A) = 4.1·10⁶5.4·10⁻¹²single: error, κ(A) = 3.8·10⁶3·10⁻⁸double: error, κ(A) = 4.2·10¹²7515the same condition number of the wrapa different number of modes near zero
Fig. 1 Three symbols, each solved through wraps whose twist is a small distance from the one that lands a sample on a zero. The two simple-zero wraps are matched in condition number at every distance and their errors are four orders apart.

A wrap with a phase on its corners

The periodic and anti-periodic wraps are two points on a circle. Put e^(−iφ) in the top-right corner and e^(iφ) in the bottom-left, where the periodic matrix has 1 and 1, and the result is a Hermitian matrix — complex unless φ is 0 or π — diagonalised by Fourier vectors modulated by e^(iφj/n). Its eigenvalues are the same symbol d − 2cos θ, sampled at θ = (2πk + φ)/n. Varying φ over a turn slides the whole grid of samples along the circle by one sample spacing, and the solve still costs two transforms, a modulation and a demodulation.

Getting the sign of that phase right on each corner is the kind of convention that fails silently: with the phases swapped every eigenvalue still comes out real and of the right size. So the transform solve is checked against the explicit complex matrix, multiplied out entry by entry, at four twists and three sizes — the solve inverts it to a worst relative residual of 3.8·10⁻¹⁴ — and the same product with the phases swapped is required to miss by more than 10⁻³. Both halves hold, which is what licenses reading the rest.

The symbol this essay turns to is d − 2cos θ with d below 2. It is the operator −u″ − ku on an interval: indefinite, with its two zeros at θ = ±θ0\theta_0 where 2cos θ0\theta_0 = d. A twist lands a sample on +θ0+\theta_0 when φ≡nθ0\varphi \equiv n\theta_0 and on −θ0-\theta_0 when φ ≡ −nθ₀, modulo a turn, so there are two landing twists — and they coincide only when nθ₀ is a whole number of half turns.

Two values of d make the two cases. At d = 2cos(10π/64) ≈ 1.76384 and n = 64, θ0\theta_0 is exactly five sample spacings, so the periodic twist lands on +θ0\theta_0 and −θ0\theta_0 at once. At d ≈ 1.73531, θ0\theta_0 is 5.3 spacings, so twist 0.3 of a turn lands on +θ0\theta_0 and twist 0.7 lands on −θ0\theta_0, separately. Call the first a pair and the second a single. Nothing else about the two matrices differs much: T’s condition number is 532 for the pair and 328 for the single.

|1.66294 − 2cos θ| on a logarithmic axis, sampled by a wrap and by the matrix that does not wrapThe modulus of the symbol d − 2cos θ with d = 1.66294 over a whole turn, on a logarithmic axis so that its two zeros, at θ = ±0.589, appear as dips. Marked on it are the 32 eigenvalues of the twisted wrap at θ = (2πk + φ)/n for a twist of 0.01 of a turn, and the 32 eigenvalues of T = tridiag(−1, d, −1) at θ = πj/(n + 1), mirrored. Two of the wrap's samples sit nearer zero than any of T's: the smallest is 0.00218 against T's 0.0196, so the wrap's condition number is 1681 against 186.7.0π/2π3π/22π10⁻³10⁻²10⁻¹1θ|d − 2cos θ|, the modulus of each eigenvaluethe wrap's samplesT's, mirroredthe symboln = 32, d = 1.66294, twist 0.01 turnsmallest |λ| of the wrap0.0022smallest |λ| of T0.02κ of the wrap1681κ(T)187an eigenvalue is the symbol at a samplethe vertical lines are the symbol's zeros
Fig. 2 The pair at n = 32, with the wrap twisted a hundredth of a turn off landing. Two samples dip towards the symbol’s two zeros together, one into each.

The picture shows it at n = 32, where the pair’s zeros are three spacings from zero and the twist is 0.01 of a turn. Two of the wrap’s samples sit nearer zero than any of T’s — both at 2.18·10⁻³, against T’s nearest at 1.96·10⁻² — one in each dip. The wrap’s condition number is 1,681 against T’s 187.

|1.59464 − 2cos θ| on a logarithmic axis, sampled by a wrap and by the matrix that does not wrapThe modulus of the symbol d − 2cos θ with d = 1.59464 over a whole turn, on a logarithmic axis so that its two zeros, at θ = ±0.648, appear as dips. Marked on it are the 32 eigenvalues of the twisted wrap at θ = (2πk + φ)/n for a twist of 0.31 of a turn, and the 32 eigenvalues of T = tridiag(−1, d, −1) at θ = πj/(n + 1), mirrored. One of the wrap's samples sits nearer zero than any of T's: the smallest is 0.00237 against T's 0.0225, so the wrap's condition number is 1513 against 159.1.0π/2π3π/22π10⁻³10⁻²10⁻¹1θ|d − 2cos θ|, the modulus of each eigenvaluethe wrap's samplesT's, mirroredthe symboln = 32, d = 1.59464, twist 0.31 turnsmallest |λ| of the wrap0.0024smallest |λ| of T0.023κ of the wrap1513κ(T)159an eigenvalue is the symbol at a samplethe vertical lines are the symbol's zeros
Fig. 3 The single at the same size, twisted a hundredth of a turn off the twist that lands on +θ0\theta_0. One sample dips; the sample opposite it, near −θ0\theta_0, is a whole 0.4 of a spacing away.

In the single the same twist distance brings one sample to 2.37·10⁻³ and leaves the mirror dip untouched. The wrap’s condition number is 1,513 — within ten per cent of the pair’s. By the rule the previous essay ended on, the two wraps are equally dangerous.

Matched condition numbers, four orders apart

The first figure measures it properly, at n = 64, with five seeded right answers per point and the twist moved from 10⁻⁷ to 10⁻¹·⁵ of a turn away from landing. The wrap’s condition number scales like one over that distance for both simple-zero symbols, and at each distance the two are within seven per cent of each other.

distance from landing κ, pair error, pair κ, single error, single
10⁻⁷ turn 4.07·10⁸ 3.2·10⁻¹⁰ 3.83·10⁸ 7.2·10⁻⁵
10⁻⁶ 4.07·10⁷ 8.8·10⁻¹¹ 3.83·10⁷ 3.3·10⁻⁶
10⁻⁵ 4.07·10⁶ 5.4·10⁻¹² 3.83·10⁶ 3.0·10⁻⁸
10⁻⁴ 4.07·10⁵ 4.1·10⁻¹³ 3.83·10⁵ 1.6·10⁻¹⁰
10⁻³ 4.07·10⁴ 7.6·10⁻¹⁴ 3.83·10⁴ 2.7·10⁻¹²

At 10⁻⁶ of a turn, κ·u is 4.5·10⁻⁹ for the pair and 4.2·10⁻⁹ for the single. The pair’s correction beats that by a factor of fifty. The single’s misses it by a factor of seven hundred and eighty. Between them sits a factor of 37,000, on two base matrices a condition-number reading cannot tell apart, solving two target matrices that elimination handles to 4.4·10⁻¹⁵ and 3.1·10⁻¹⁵.

The third curve is the periodic Laplacian again, d = 2, a double zero at θ = 0. Its condition number grows like the square of one over the distance rather than the first power — 4.15·10⁸ at 10⁻³ of a turn, 4.15·10¹⁰ at 10⁻⁴ — and its error with it: 1.2·10⁻⁴ and 1.1. It behaves like the single, more steeply.

So the condition number of the wrap is not what decides. Something that distinguishes one landed sample from two does.

What the two-by-two system sees

The capacitance matrix is S = I + VᵀA⁻¹U, with U and V the two corner couplings, and it is the one place a rank-two correction can amplify rounding beyond what cancellation already does. Its condition number, drawn against the same distances, separates the three cases completely.

The capacitance matrix's condition number against the distance of the twist from the landing twist, three zeros, n = 64The condition number of the 2 × 2 capacitance matrix S of the rank-two correction through a twisted wrap of size 64, against how far the twist is from the one that lands a sample exactly on the symbol's zero, from 10⁻⁷ to 10⁻¹·⁵ of a turn, on logarithmic axes. Three symbols: a simple zero landed on at twist 0, where its mirror image is landed on at the same time; a simple zero landed on at 0.3 of a turn, where it is not; and the double zero of 2 − 2cos θ. At 10⁻⁶ of a turn the first two wraps have κ 4.1·10⁷ and 3.8·10⁷; the capacitance matrix has κ 1 and 9.1·10⁵; the forward errors are 8.8·10⁻¹¹ and 3.3·10⁻⁶.-7-6-5-4-3-2110¹10²10³10⁴10⁵10⁶10⁷10⁸10⁹10¹⁰10¹¹10¹²log₁₀ of the twist's distance from landing, in turnsκ(S), the capacitance matrixsimple zero, landed on at 0simple zero, landed on at 0.3double zero, d = 2n = 64, twist 10⁻⁵ of a turn from landingpair: κ(S), κ(A) = 4.1·10⁶1single: κ(S), κ(A) = 3.8·10⁶9.1·10⁴double: κ(S), κ(A) = 4.2·10¹²6.4·10¹⁰the same condition number of the wrapa different number of modes near zero
Fig. 4 The capacitance matrix’s condition number for the same three symbols. The pair’s is 1.00 at every distance. The single’s grows like one over the distance, the double zero’s like its square.

For the pair it is 1.00 — to three figures, at every distance from 10⁻⁷ to 10⁻¹·⁵ of a turn. For the single it is 9.07·10⁶ at 10⁻⁷ and falls by ten for each decade: 9.07·10⁵, 9.07·10⁴, 9.07·10³. For the double zero it is 6.4·10⁶ at 10⁻³ and 6.4·10⁸ at 10⁻⁴.

The mechanism is short. Near landing, A−1A^{-1} is dominated by its near-null part: one term λ−\lambda^-¹vvᴴ for each sample close to a zero, with v the corresponding modulated Fourier vector. S is then approximately the identity plus the corner entries of those terms. With one near-null vector — the single, or the double zero’s constant — that is the identity plus a rank-one matrix of size about 1/λ, which is as badly conditioned as a two-by-two matrix can be in proportion to its largest entry. With two near-null vectors and two equally small eigenvalues, S is approximately λ−1\lambda^{-1}(VᵀP)(PᴴU), where P holds the two vectors side by side. Each factor is a two-by-two matrix of corner entries, every one of modulus 1/n1/\sqrt{n} and differing only in phase, and each factor is a multiple of a unitary matrix. Their product is too. A multiple of a unitary matrix has condition number one, however large the multiple.

That is the whole difference. A rank-two correction’s capacitance matrix is well conditioned when the base matrix’s near-null space is two-dimensional and poorly conditioned when it is one-dimensional, and the size of the near-singularity enters only as a scale factor that the solve with S removes exactly.

And what is left once S is harmless

With κ(S) at one, the only amplification left is the last subtraction — the intermediate solve C−C^-¹b is large, and the answer is formed as a difference of large vectors. Divide the pair’s error by that cancellation ratio times u and the result is 1.2, 3.3, 2.0, 1.5 and 2.9 across the first five distances: the error is the cancellation and nothing more. Divide the single’s by the cancellation times κ(S) times u and it is 0.06, 0.27, 0.24, 0.13, 0.22 — the product law of the periodic Laplacian, with the same constant of about a tenth.

That puts the three cases on one line. The forward error is roughly

error  ≈  c⋅∣A−1b∣∣x∣⋅κ(S)⋅u\text{error} \;\approx\; c \cdot \dfrac{|A^{-1}b|}{|x|} \cdot \kappa(S) \cdot u

with c between a tenth and a few, and the capacitance factor is the one that tells a pair from a single. The cancellation factor is not what differs: it is 2.4·10⁵ for the pair and 1.2·10⁵ for the single at 10⁻⁶ of a turn.

The plane survives what its vectors do not measured the same shape of fact from the eigenvector side. Two nearly equal eigenvalues make each eigenvector hopelessly sensitive and the plane they span perfectly well conditioned, because the arithmetic that cannot separate the two directions has no need to. Here the correction does not need to separate the two near-null directions either. It needs to remove the plane they span from the intermediate solves, and a rank-two correction removes a plane in one well-conditioned step. The Laplacian’s one near-null direction is the opposite case: a rank-two correction aimed at a one-dimensional problem spends one of its two dimensions on a direction that is not near-null, and S is left to divide a huge number by a moderate one.

Over a whole turn of twists

The window figures zoom into the last hundredth of a turn before landing. Across the whole turn, sixty-four twists at one sample spacing apart, the picture is simpler and it says how much any of this matters for choosing a wrap.

The rank-two correction through a twisted wrap, against the twist — a simple zero, n = 64Forward error, median of five answers, of solving tridiag(−1, 1.73531, −1) of size 64 through the wrap whose corners carry a phase of φ, for φ over one turn in 64 steps, on a logarithmic vertical axis, with κ(A(φ))·u dashed. The symbol has a simple zero that the twist 0.3 of a turn lands a sample on, and that twist is not drawn. The worst drawn error is 4.6·10⁻¹³ at 0.297 of a turn, where κ(A(φ)) = 1.2·10⁴; the best-conditioned twist, 0 of a turn, is the one farthest from both landing twists. Elimination on T gives 3.1·10⁻¹⁵.00.250.50.75110⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰twist φ, in turnsrelative forward errorκ(A(φ))·uthe correctionκ(T)·un = 64, a simple zero, landed on at 0.3 turnworst drawn error, twist 0.2974.6·10⁻¹³κ of that wrap1.2·10⁴best twist 0: error1.3·10⁻¹⁴elimination on T3.1·10⁻¹⁵one matrix T, sixty-four wrapsa gap in the curve is a wrap that is exactly singular
Fig. 5 The single at sixty-four twists over one turn. The wrap’s condition number rises to 1.2·10⁴ one grid step from each landing twist; the correction’s error lifts off rounding only at those two steps.

For the single the twist grid’s nearest points to the landing twists 0.3 and 0.7 are 0.297 and 0.703, where κ of the wrap is 1.2·10⁴ and the correction returns 4.6·10⁻¹³ and 1.7·10⁻¹³. Everywhere else it is between 6·10⁻¹⁵ and 2·10⁻¹⁴ — none of the sixty-five twists costs more than 10⁻¹². A single simple zero is dangerous in a window about 10⁻³ of a turn wide around each of its two landing twists, and harmless outside it.

The rank-two correction through a twisted wrap, against the twist — a simple zero, n = 64Forward error, median of five answers, of solving tridiag(−1, 1.76384, −1) of size 64 through the wrap whose corners carry a phase of φ, for φ over one turn in 64 steps, on a logarithmic vertical axis, with κ(A(φ))·u dashed. The symbol has a simple zero that the twist 0 of a turn lands a sample on, and that twist is not drawn. The worst drawn error is 1.7·10⁻¹⁴ at 0.203 of a turn, where κ(A(φ)) = 204; the best-conditioned twist, 0.5 of a turn, is the one farthest from both landing twists. Elimination on T gives 4.4·10⁻¹⁵.00.250.50.75110⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰twist φ, in turnsrelative forward errorκ(A(φ))·uthe correctionκ(T)·un = 64, a simple zero, landed on at 0 turnworst drawn error, twist 0.2031.7·10⁻¹⁴κ of that wrap204best twist 0.5: error1.1·10⁻¹⁴elimination on T4.4·10⁻¹⁵one matrix T, sixty-four wrapsa gap in the curve is a wrap that is exactly singular
Fig. 6 The pair over the same turn. κ of the wrap climbs to 2.6·10³ beside the landing twist at zero; the correction does not notice.

For the pair the curve is flat: median 1.2·10⁻¹⁴ over the turn, 1.5·10⁻¹⁴ at one grid step from landing where κ is 2.6·10³, and nothing above 1.7·10⁻¹⁴ anywhere. The window of the table above says it stays that way down to 10⁻⁷ of a turn, where the correction is still at 3.2·10⁻¹⁰ with the wrap at κ = 4·10⁸.

The rank-two correction through a twisted wrap, against the twist — a double zero, n = 64Forward error, median of five answers, of solving tridiag(−1, 2, −1) of size 64 through the wrap whose corners carry a phase of φ, for φ over one turn in 64 steps, on a logarithmic vertical axis, with κ(A(φ))·u dashed. The symbol 2 − 2cos θ has a double zero at θ = 0, so the periodic wrap φ = 0 is singular and is not drawn. The worst drawn error is 7·10⁻⁹ at 0.0156 of a turn, where κ(A(φ)) = 1.7·10⁶; the best-conditioned twist, 0.5 of a turn, is the one farthest from both landing twists. Elimination on T gives 6.3·10⁻¹⁵.00.250.50.75110⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸twist φ, in turnsrelative forward errorκ(A(φ))·uthe correctionκ(T)·un = 64, d = 2, a double zero at θ = 0worst drawn error, twist 0.01567·10⁻⁹κ of that wrap1.7·10⁶best twist 0.5: error4.6·10⁻¹⁴elimination on T6.3·10⁻¹⁵one matrix T, sixty-four wrapsa gap in the curve is a wrap that is exactly singular
Fig. 7 The double zero at d = 2 over the same turn. The periodic twist is exactly singular and is left out; its neighbours cost 7·10⁻⁹, and the loss spreads over a quarter of the turn.

For the Laplacian’s double zero the damage is wide rather than narrow. One grid step from the periodic twist the error is 7.0·10⁻⁹ with κ of the wrap at 1.7·10⁶; two steps away it is 1.6·10⁻¹⁰; four steps away 2.8·10⁻¹¹. Sixteen of the sixty-three twists drawn cost more than 10⁻¹², all within an eighth of a turn of the periodic twist on either side, and the best — anti-periodic, at half a turn — returns 4.6·10⁻¹⁴ with κ = 1,659, three per cent under T’s own 1,712.

The rule for choosing a wrap therefore survives in its practical form: read the symbol’s zeros, compute the landing twists, and take the twist farthest from all of them. The best twist is 0.5 of a turn for the pair and the double zero and 0 for the single, and at each of those the wrap is better conditioned than T — 85 against 532 for the pair, 131 against 328 for the single. What does not survive is the reason. A near-singular wrap is not dangerous in proportion to its condition number; it is dangerous in proportion to how badly the correction’s rank matches the dimension of its near-null space, and only a wrap that matches badly needs to be avoided.

A code can tell which case it is in, for nothing

None of this would matter much if the distinction were only visible in a sweep. It is visible in a single solve, because the number that separates the cases is formed by the correction anyway. S is two by two; its condition number is the ratio of two numbers a code already has — its Frobenius norm and its determinant — and it is 1.00 for the pair and 9·10⁵ for the single at 10⁻⁶ of a turn from landing, and 6·10⁸ for the double zero at 10⁻⁴. A correction that reports κ(S) beside its answer reports which of the three it was.

What a code cannot do with the same information is the thing it would most like to: know the forward error. The cancellation ratio is also computable — ‖A−A^-¹b‖ is the norm of a vector the correction forms, and ‖x‖ the norm of the answer — and the product law says the error is a small multiple of their product times u. But the multiple ranges from 0.06 to 3.3 over the measurements here, a factor of fifty, and nothing inside the solve narrows it. The product is an estimate of the order of magnitude, which is what the condition number is an amplifier says a condition-number estimate ever is, and it is the right order of magnitude in all three cases where κ of the wrap alone is right in one.

The residual against T is the check that does not depend on any of this. It is a three-term stencil, it reads no inverse, and refining against it repaired the periodic Laplacian’s correction wherever the unrefined error was below one. A pair never needs it; a single near its landing twist does; and the capacitance matrix’s condition number is the cheap way to decide which before paying for a residual at all.

Why an indefinite symbol is the ordinary case

The symbols with two zeros are not a construction for the sake of the argument. The Laplacian’s double zero at θ = 0 belongs to a definite operator, and definite operators are the ones every account of circulant solves starts from. An operator with a real shift of the other sign — a wave equation at a fixed frequency, a vibration problem driven below its highest mode, the shifted systems an eigensolver solves at every step — has a symbol that crosses zero, and it crosses at two points placed symmetrically about θ = 0 because the operator is real. Its zeros come in mirror pairs by construction.

So the real wraps, twist 0 and twist π, are the ones that treat the two zeros alike, and the pairing this essay measures is what a real wrap does whenever it lands at all. A complex twist is what breaks the symmetry and produces a single; it is chosen to move the samples, and moving them is what makes the landing, when it happens, a landing on one zero rather than two.

The gap decides the eigenvector is the eigenvalue side of the same symmetry: a symmetric problem’s nearly equal pair is a pair of directions that cannot be told apart, and the object that is well determined is the pair together. The vertex nobody solves for is its one-dimensional counterpart, a singular matrix whose kernel is a single direction that every solve has to remove by some explicit choice. The double zero is that kind; the pair is the other.

The sizes, and what does not move

Both simple-zero comparisons were repeated at n = 16 and n = 256 with the same symbols scaled to the same fraction of the band and the twist 10⁻⁶ of a turn from landing. The pair returns 5.0·10⁻¹¹ at n = 16 with κ of the wrap 1.28·10⁷, and 5.2·10⁻¹¹ at n = 256 with κ = 1.63·10⁸; its capacitance matrix is 1.00 at both. The single returns 1.3·10⁻⁶ and 1.6·10⁻⁶, with κ(S) at 9.1·10⁵ and 9.2·10⁵. A sixteen-fold change of size moves the pair’s error by four per cent while its wrap’s condition number changes by a factor of thirteen, and it moves the single’s κ(S) by one per cent.

The size enters through the near-null eigenvalue and the cancellation, and those two move together, so what is left is a property of the pairing and not of n.

What this rests on, and what it does not claim

Two symbols with simple zeros and one with a double zero, all tridiagonal, at three sizes. The pair is constructed so that θ0\theta_0 is a whole number of spacings; a real wrap lands on a pair exactly when nθ₀ is a whole number of half turns, and otherwise a twist of 0 or π lands on neither.

The claim that S is a multiple of a unitary matrix is an approximation that holds when the two near-null eigenvalues are equally small. At the pair’s landing twist they are — the samples at θ0\theta_0 and −θ0\theta_0 are mirror images — and the measured 1.00 says the approximation is tight. A wrap twisted so that one of the pair’s samples is much nearer its zero than the other would pass continuously from the pair’s behaviour to the single’s, and that interpolation is not drawn.

All errors are medians of five seeded right answers. The constant in the product law varies between 0.06 and 3.3 over the table, and is quoted as a range rather than as a number.

The claim that has to fail

The claim is the rule the Laplacian measurement makes tempting: a correction routed through a nearly singular base matrix loses at least the base matrix’s condition number times the unit roundoff. Fed the pair at n = 64 with the twist 10⁻⁶ of a turn from landing, where κ of the wrap is 4.1·10⁷ and κ·u is 4.5·10⁻⁹, and required to show an error at least that large, it must fail — and it does, at 8.8·10⁻¹¹. The single at the same distance is kept beside it as the control, and it loses 3.3·10⁻⁶, so the refusal is not a statement that corrections are safe. It is a statement that the base matrix’s condition number is the wrong number to read.

A correction cheaper than the problem found that the rank-one formula’s error followed κ of the base matrix at a slope of one, and that is consistent with everything here: a rank-one correction’s capacitance “matrix” is a scalar, a scalar has condition number one, and a rank-one correction facing a one-dimensional near-null space is matched. The circulant that cannot be indefinite and a limit the matrix never reaches are the same field’s reminders that a structured approximation’s worth is decided by which structure is kept, and the condition number is an amplifier the reminder that an amplifier needs something in the direction it amplifies. Here the correction removes that direction before anything is amplified along it.

Still open: rank against dimension, and the wrap in two dimensions

A near-null space larger than the correction. Everything above compared a rank-two correction with near-null spaces of dimension one and two. A pentadiagonal matrix is a circulant plus a rank-four correction, and a symbol with four zeros gives a wrap that can land on four samples at once, or two, or one. Whether the capacitance matrix is well conditioned exactly when the two numbers are equal — and what a near-null space larger than the correction’s rank does, where the correction has no room to remove it — is a measurement the tridiagonal family cannot make.

The pair’s interpolation. A twist that puts one sample of the pair much nearer its zero than the other moves the two near-null eigenvalues apart. The capacitance matrix should pass from κ = 1 to the single’s κ as their ratio grows, and the shape of that passage would say how exactly a code has to arrange a pair before it can rely on it.

Twists along two axes. A two-dimensional operator with fixed edges is a tensor-product wrap plus a correction of rank proportional to an edge, and each axis carries its own twist. The Laplacian’s double zero sits at the origin of both axes, and whether twisting both by half a turn repairs the correction as completely as it does here — or whether the correction’s larger rank finds a pairing on its own — is the question on which the route’s use for grids depends.

Where this goes next

10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹10³10⁵σ — how far the periodic wrap is from singularrelative forward error10⁻¹10⁻²10⁻³10⁻⁴10⁻⁵10⁻⁶10⁻⁷10⁻⁸10⁻⁹10⁻¹⁰10⁻¹¹10⁻¹²periodic correctionκ(C)·uelimination on Tn = 64, median of five answersperiodic correction, σ = 10⁻⁸1.2·10⁻⁴elimination on T, σ = 10⁻⁸1.1·10⁻¹⁴κ(C) at σ = 10⁻⁸4·10⁸κ(T) at σ = 10⁻⁸1712the same matrix T in every columnonly the wrap it is solved through changes The circulant the problem did not contain A matrix that differs from a circulant in two corner entries can be solved through the circulant, by a transform and a two-by-two correction, and the cost claim is exact. The accuracy claim is not. On tridiag(−1, 2 + σ, −1), whose condition number stops at 1,712, the correction is wrong by 1.2·10⁻⁴ at σ = 10⁻⁸ while elimination is right to 1.1·10⁻¹⁴ — because the periodic neighbour is singular at σ = 0, the two-by-two system inherits that, and the two amplifications multiply. the invariant planesolid: beforedashed: aftersame perturbation, two questionsthe vectors turned, radians0.029the plane turned, radians7.6·10⁻⁸what left the plane5.6·10⁻⁸drawn in the unperturbed plane's own basisa radius is not determined; the circle is The plane survives what its vectors do not At a gap of 10⁻⁹ a perturbation of 10⁻⁶ turns the two eigenvectors through half a radian and turns the plane they span through 7.6·10⁻⁸ — a ratio of six million. Ask for the subspace instead of the vectors and a hopeless computation becomes a well-conditioned one, with no change to the arithmetic. 10¹10³10⁵10⁷10⁹10¹¹10¹³10¹⁵10⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1κ₂(A), the matrix that was updatedrelative forward errorSherman–Morrisondirect solve of A + uvᵀone answer, two routesκ of the answer's matrix1κ of the matrix replaced10·10¹³update formula's error2.5·10⁻⁴direct solve's error1.1·10⁻¹⁶the question's condition number is 1at every point on this axis A correction cheaper than the problem Sherman and Morrison's formula updates a solved system for a rank-one change to the matrix, at 4n² operations instead of (2/3)n³. It is exact algebra. On a problem whose updated matrix is the identity — condition number one, the easiest system there is — it returns a forward error of 2.5·10⁻⁴ where a direct solve returns 10⁻¹⁶.

What links here

Computed from the collection, not written here: the essays that point at this one.

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.

CancellationCapacitance matrixCirculant matrixCondition numberDiscrete laplacianForward errorInvariant subspaceNear-null spaceSymbolTwisted circulantWoodbury identity