A threshold the matrix does not set

A comparison of routes to the singular values of a graded matrix produces two numbers, and they are almost always read as one. The first is how accurate the routes that work are. The second is how much grading the route that does not work survives before it stops returning anything. The essay that measured the flatness put both on one axis — the number of decades the spectrum is graded over — and found one of them flat at the unit roundoff and the other leaving the picture at about ten decades.

One axis cannot separate two dependences. Held at a fixed grading and varied in n instead, that essay found the good routes’ error rising by about a factor of four over a factor of five in size, which is the n·u constant the relative-accuracy theorems carry. It could not ask the same question of the crossing, because the crossing is a point on the grading axis and the grading was the quantity being held fixed.

The question matters because of who has to answer it. A caller deciding whether to form BᵀB has no reference answer, cannot sweep the grading, and knows two things about the problem in front of them: roughly how large it is, and roughly how far apart the ends of its spectrum are. If the failure point is a property of the matrix’s size, the first of those decides. If it is a property of the arithmetic, the second does, and the size is irrelevant.

Both dependences are measurable at once, against a reference that was not computed by any of the routes being judged, and the answer is the opposite way round from the intuition that a larger problem is a harder one.

The size moves the constant of the routes that hold #

The statistic to take from each drawing is the worst relative error one-sided Jacobi commits anywhere on the sweep — over all eight matrices, not on one of them. That is the quantity a caller is exposed to, because a caller who knew which grading their matrix had would not need the sweep.

At n = 4 it is 7.05·10⁻¹⁶, which is 6.35 units of roundoff. The zero-shift sweep’s worst over the same eight matrices is 6.04·10⁻¹⁶, or 5.44u. Both are within a factor of two of the arithmetic’s own granularity, and neither moves as the grading opens from 1.8 decades to 49.7.

The claim about that flatness is a claim about the grading only, and it survives every drawing here. What it does not settle is the height of the flat line, which is where the size enters.

Treble the matrix and the line rises. At n = 12 one-sided Jacobi’s worst over the sweep is 1.55·10⁻¹⁵, or 13.92u, and the zero-shift sweep’s is 1.77·10⁻¹⁵, or 15.91u. The line is still flat — the largest and smallest readings on it differ by a factor of 3.6 across forty-six decades of grading, and what trend there is runs the wrong way for difficulty, from 1.55·10⁻¹⁵ at 3.3 decades down to 4.34·10⁻¹⁶ at 49.7 — and it now sits fourteen times the unit roundoff rather than six.

That last clause is the whole comparison in one reading. The constant went up by a factor of two and the failure point did not move at all.

The failure point stays where it was #

Every drawing reports the first grading at which the BᵀB route’s worst relative error passes 10⁻⁶. Across the five sizes those readings are 9.93, 10.54, 10.54, 10.84 and 9.93 decades — a spread of nine per cent over a threefold range of n, and no ordering in it: the largest reading is at n = 10 and the two smallest are at the two ends.

The values at those points are 1.00, 55.4, 14.5, 1.00 and 2.02. A relative error of exactly one means the routine returned zero, which is the shape this comparison has named before: the route stops returning a wrong number and starts returning no number.

Those five values are not ordered and they are not meant to be. Past the crossing the route is returning a number that has nothing in common with the answer, and how large that number happens to be is a fact about which rounding survived rather than about how much worse the matrix got. Fifty-five at n = 6 and one at n = 4 are the same failure, and the second is the more complete of the two, since a relative error of exactly one is a value returned as zero. What the readings do agree on is where the failure starts, and that is the quantity the whole comparison is about.

The bracket is the honest form of the reading, because a crossing measured on eight points is a point somewhere between two of them. Taking the last grading at which BᵀB is still below 10⁻⁶ and the first at which it is above gives [5.42, 9.93] at n = 4, [4.52, 10.54] at n = 6, [4.21, 10.54] at n = 8, [5.42, 10.84] at n = 10 and [6.62, 9.93] at n = 12. Five brackets, and every one of them contains eight decades.

Eight is not a fitted number. It is half of what the format has: the sixteen decades a double carries are 15.95 of them, and half of that is 7.98.

Reading the five drawings together: the constant of the routes that never fail runs 6.35u, 9.76u, 13.34u, 17.01u and 13.92u, rising by a factor of 2.68 from n = 4 to n = 10 and falling back at n = 12. The failure point of the route that does fail runs 9.93, 10.54, 10.54, 10.84 and 9.93 decades. One of those sequences is about the matrix and one is about the arithmetic, and the sequence about the matrix is the one attached to the routes that get the right answer.

The n = 12 reading is off the trend and is worth naming rather than smoothing. Each of these is a maximum over eight matrices, and a maximum of a quantity that is itself a rounding is not a smooth function of anything. Four points rising and one falling back is what a noisy maximum does; what would contradict the reading is a fall of the same size as the rise, and 13.92u against 6.35u is not that.

The constant that grows is the theorem’s own hypothesis #

There is a second measurement that says which quantity the rising line belongs to, and it is not a fit.

The relative-accuracy theorems are hypotheses on κ(X), where A = D·X with D diagonal and every row of X of unit norm — the number the essay about the second family showed is decisive and is not κ(A). Along this graded family κ(X) is constant in the grading, which is what makes the flat lines flat. It is not constant in n. It reads 3.372, 4.273, 4.892, 5.332 and 5.653 at n = 4, 6, 8, 10 and 12.

Dividing the measured worst error by u·κ(X) gives 1.88, 2.29, 2.73, 3.19 and 2.46 for one-sided Jacobi and 1.61, 2.13, 2.01, 1.84 and 2.82 for the zero-shift sweep. Ten numbers between 1.6 and 3.2, across a threefold range of n and two different algorithms. The growth in the constant is the growth in the hypothesis, and the residual multiple is between one and two rotations’ worth of rounding.

That is a stronger statement than “linear in n”. What grows with the size is not a mysterious algorithmic constant; it is the conditioning that remains after the grading has been divided out, measured on the part of the matrix a diagonal cannot reach — and that part gets slightly worse as the matrix gets longer, because a longer bidiagonal has more rows to be nearly dependent in.

None of this touches the BᵀB route, because that route has no such theorem. Squaring is not an algorithm with a hypothesis that can fail; it is an operation that discards information before any algorithm sees the matrix.

Where the threshold comes from, and why it is not the matrix’s #

The prediction is one line and needs nothing measured. Forming BᵀB squares the spectrum, so the smallest singular value becomes the smallest eigenvalue of a matrix whose largest is σ₁². An addition loses everything below u times the largest term, so σ_min is gone from the sum when σ_min²/σ₁² falls below u — that is, when κ(B)² reaches 1/u. In binary64 that is κ = 9.49·10⁷, and along this family the condition number is very nearly 10 to the power of the grading: log₁₀ κ divided by the decades reads between 1.026 and 1.028 at ten decades of grading at every one of the five sizes, falling towards 1.016 by sixteen. So the count says 7.8 decades, whatever n is, and n does not appear anywhere in it.

This is the same inequality the Hankel essay writes as a floor at σ₁√u, read on the other axis. A value is lost when it falls below σ₁√u; a spectrum has lost its smallest value when κ exceeds 1/√u; those are one statement said twice.

The two readings are worth putting side by side, because they disagree about how sharp the law is and the reason is the axis rather than the law. That essay measures the constant in front of the floor and finds it running from 0.20 to 4.1 across model sizes and degrees — a factor of twenty, an order of magnitude either side of one, which is what a square-root law can promise. A factor of twenty in a floor is 1.3 decades on the grading axis, since the floor sits under a square root and the grading is the logarithm of κ. The window measured here is 0.6 decades, less than half of it — not because the law is sharper, but because this family is graded by construction, so the quantity the floor is stated relative to is the thing being swept rather than a property of a model that has to be fitted.

The mechanism is the cancellation that the road that squares the problem prices in the least-squares setting, arriving at a spectrum instead of a solution. What is new is not that the squaring costs half the format. It is that half the format is a quantity the format supplies and the matrix does not, so a caller who knows only the size of their problem knows nothing about it, and a caller who knows only its spectral span knows all of it.

What the sweep can resolve, and what it cannot #

The five readings agree to nine per cent, and that agreement is worth less than it looks, because the family the sweep is drawn on is quantised. A grading is an integer number of bits per row, so the available gradings are multiples of (n − 1)·log₁₀2 decades: 0.90 apart at n = 4 and 3.31 apart at n = 12. The readings 9.93 and 10.54 are grid points, not measurements of a continuous crossing, and at n = 12 one grid step is a third of the answer.

So the sweep is re-run on the finest grid each size allows, with the criterion sharpened from 10⁻⁶ to the loss itself — the first grading at which the route’s relative error reaches one, meaning not a single correct digit of the smallest singular value. The brackets tighten to (8.13, 9.03] at n = 4, (7.53, 9.03] at n = 6, (8.43, 10.54] at n = 8, (8.13, 10.84] at n = 10 and (6.62, 9.93] at n = 12.

Their intersection is (8.43, 9.03]: a window six tenths of a decade wide that every size shares. Whatever the crossing depends on, it does not depend on n strongly enough to move outside a window narrower than a single grid step at every one of the five sizes.

The prediction of 7.8 decades sits just below that window rather than inside it. The count assumes σ_min is lost the moment it falls under u times the largest term, and in practice the eigensolver holds some of it for between six tenths and one and a quarter decades longer. A rule of thumb that is under a decade conservative is the right kind of wrong for a decision rule: it says do not form this product slightly before the product actually fails, and never afterwards.

The 10⁻⁶ criterion drawn on the figures is a different question and gives a different answer. On the fine grid its brackets are (5.42, 6.32], (6.02, 7.53], (4.21, 6.32], (5.42, 8.13] and (6.62, 9.93], and those do not share a common point — the onset of damage arrives earlier at n = 4 than at n = 12. Onset and loss are not the same event, and a comparison that quotes one and reasons about the other has substituted a diagnostic for the quantity the diagnostic was standing in for.

The gap is also smaller than it looks, and reading it as evidence would be reading the family’s grid. The n = 4 bracket ends at 6.32 decades and the n = 12 bracket begins at 6.62, so the two miss each other by three tenths of a decade — less than a tenth of one grid step at n = 12, whose matrices come 3.31 decades apart. There is no member of the family between them to measure, at either size. So the onset criterion does not establish an n-dependence; it establishes that the family cannot be sampled finely enough to rule one out, which is a weaker statement about a coarser instrument, and it is why the loss criterion is the one the argument rests on.

Both criteria agree about where on the spectrum the damage is. At every size and every grading drawn here the worst relative error the squaring route commits is the error on the smallest singular value, never on a value in the middle — the sequence at n = 12 and ten decades runs 3.5·10⁻¹⁶, 8.1·10⁻¹⁶, 1.0·10⁻¹⁴ and on down to 2.4·10⁻² and 2.0 at the last two. The route does not degrade; it eats the spectrum from the bottom, one value at a time, and the crossing is the moment the bottom one is finished.

The instrument stops before the claim does #

The n-axis here runs from 4 to 12, and that bound belongs to the reference rather than to the result.

Every error above is measured against a Sturm bisection in BigInt rationals: a count of sign changes in a recurrence with one division per row and no square roots, bisected on a shift until the value is known to sixty bits of its own size. It is the exact answer this collection insists on whenever two floating-point routes would otherwise be adjudicating each other, and it is not free. One reference at thirty decades costs twenty-one times as much at n = 12 as at n = 4, and a hundred times as much at n = 20 — near enough the cube of the size, because the rationals grow in length as well as in number. A single drawing needs eight of them.

The figure refuses n = 20 outright. That refusal is the correct behaviour and it is also the honest statement of what has been established: five sizes over a threefold range, with the crossing not moving and the constant rising by a factor of 2.7. Whether the crossing is still at eight decades at n = 10,000 is not measured here and cannot be, because the reference that makes the measurement a measurement stops existing.

What can be said about that regime is what the prediction says, and the prediction contains no n. The part of it that would break at large n is the other half — the constant, which grows with κ(X). On the extrapolation the earlier essay makes, a matrix of ten thousand rows would put the routes that hold at 10⁻¹² rather than 10⁻¹⁶ while the squaring route was still failing at eight decades. The gap between them would be four orders narrower and still twelve orders wide, which is why the comparison survives the size and the absolute claim does not.

What follows for a caller with no reference answer #

The point of separating the two dependences is that they lead to different advice, and only one of them is advice a caller can act on before running anything.

Do not size the risk by the size of the matrix. In the readings drawn here the 4×4 loses its smallest singular value at exactly the grading the 12×12 does — 9.93 decades on both — and earlier than the 6×6, the 8×8 and the 10×10. Anything that treats forming a Gram matrix as safe on small problems is using the wrong variable.

Size it by the span, against half the format’s decades. The quantity to compare is an estimate of κ, and 1/√u is 9.49·10⁷ in binary64. That is a comparison a caller can make from a condition estimate costing four or five products with a factorisation already to hand — with the caveat that essay is about, which is that an estimate can be fooled and this decision rests on it.

And make sure it is the right κ. The number in the prediction is the ordinary spectral condition number, the one a change of units moves, and not Skeel’s componentwise number, which a row scaling leaves exactly where it was. Two defensible condition numbers of one matrix will not both answer this question, and the essay that separates them says which is which. The invariant one is the better description of the matrix and the wrong instrument here, because the quantity being predicted is not invariant either: the squaring damages a spectrum, and a spectrum is exactly what a diagonal scaling moves.

The threshold moves with the format and with nothing else. In binary32 half the decades is 3.6 rather than 8, so a spectrum spanning four decades — utterly ordinary — is past it. In binary128 it is about 17. That is the only variable in the rule, and it is a compile-time constant.

And past the threshold the failure is visible from inside. Two of the five crossings drawn here report a relative error of exactly 1.00, which is a smallest singular value returned as exactly zero by a matrix that is not rank-deficient — a signal available without any reference answer at all. The other three report 55.4, 14.5 and 2.02, which are not signals: a wrong number of ordinary size looks exactly like a right one, and that is the half of the crossing a caller cannot see.

And the decision is only about the small end. The largest singular values come back to 10⁻¹⁶ from every route at every grading and every size drawn here, so a norm is safe, a truncation is safe, and the error of a best rank-k approximation is unaffected. What is not safe is any quantity with a small singular value in a denominator, which includes every condition number and every rank decision made on a ratio.

The refusal #

The assertion is fed a rational Sturm bisection asked for at a size it cannot afford, at n = 20, and required to decline.

It is the refusal that bounds this essay’s own axis, and it declines the most tempting substitution available: to keep the n-axis going by dropping the exact reference and comparing the routes to each other. That would produce a picture with the same shape and no content, because the crossing is precisely the grading at which one route’s answer stops being an answer, and a comparison against another floating-point route cannot tell an answer that is wrong from an answer that is absent. Deciding that a computed quantity has become zero is a decision that needs a reference, and refusing to draw the case where none exists is the same discipline as refusing to draw a comparison over a range where the thing being compared does not differ.