Numerical Linear Algebra
where the algebra stops being the arithmetic
The answer that depends on the machine

The variation that comes with a seed

A randomised low-rank approximation's error moves by 31% between draws and by 10⁻¹⁵ between partitionings of one draw. In the one field on this site whose answer already comes as a band, the machine is inside the width of the line — and it is still there.
28 min read 21 figures Measured, not assertedTwo routes to a numberWhose fault is it

Worth reading first: The same program, twice · A bound that holds with probability · The dimension does not appear.

This field has spent sixteen essays showing that a computation’s answer is not a single number. The randomised field got there first, by a different route and on purpose.

A bound that holds with probability is where this site’s guarantee changes kind: a randomised low-rank approximation’s error is a draw, its bound holds with a probability rather than always, and every figure in that field draws a band rather than a line. A reader of it is already accustomed to an answer that varies between runs, and to recording a seed so it does not.

So the question this essay exists for: how do the two variations compare?

The draw moves the answer by a third; the machine moves it by a roundingA randomised rank-8 approximation of a 120 × 60 matrix, at five rates of spectral decay. The upper curve is the relative spread of the error over eight seeds; the lower is its spread over seven partitionings of one seed's reduction. The first runs from 0.0626 to 0.31 and the second from 9.82·10⁻¹⁶ to 2.83·10⁻¹⁵: at least 4.4·10¹³ between them. The machine's contribution is not zero — four to seven of the seven partitionings return distinct values at every rate — it is simply inside the width of a line the method draws for a reason it announces. This is the one field on the site where the fifth author is already dominated, and it is dominated by the one source of variation that comes with a seed attached.00.10.20.30.40.50.60.70.80.9110⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹decay rate of the spectrumrelative spread of the rank-k errorthe seedthe machinetwo kinds of variationseeds drawn8partitionings7seed spread0.31machine spread9.8·10⁻¹⁶ratio3.1·10¹⁴one of these is recordedand it is the large one
Fig. 1 A randomised rank-8 approximation of a 120 × 60 matrix at five rates of spectral decay. The upper curve is the spread of the error over eight seeds; the lower is its spread over seven partitionings of one seed’s reduction.

The draw moves the answer by up to 31%. The machine moves it by about 10⁻¹⁵. Between them, at every decay rate measured, at least 4.4·10¹³.

Reading the figure

Five spectra, from a geometric decay of 0.7 per index — fast, so a rank-8 approximation is nearly exact — to 0.94, which is slow enough that eight directions capture little of the matrix.

The upper curve is not monotone, and the shape is worth a sentence. At a fast decay the leading subspace is so dominant that any random sketch finds it and the draw matters little: 6.3%. At a slow decay everything is nearly equally important, so a sketch that misses one direction has missed something no larger than what it caught: 9.4%. In between, at 0.82, the matrix has a leading subspace that a sketch can either find or miss, and the draw matters most: 31%.

The lower curve is flat at about 10⁻¹⁵ across all five, which is what a quantity made of roundings does when the problem changes and the precision does not.

The comforting reading, and its limit

The comforting reading is the correct one and it should be stated first. In this field the fifth author is already dominated. A practitioner who reports a randomised method’s error as a band across seeds is reporting a band whose width is fourteen orders larger than anything a thread count contributes, so the machine’s disagreement is invisible inside a figure that was already honest about being a distribution.

That is a genuine limit on the field this essay sits in. Not every computation needs an order-independent reduction, and the ones whose answer is already a distribution need it least.

The limit of the comfort is the word dominated. The machine’s contribution is not zero: at every decay rate, four to seven of the seven partitionings return distinct values. It is small, and small is not the same as absent, and the difference matters in exactly one place — a comparison.

What the seed does and does not fix

The practice of recording a seed is a reproducibility practice, and it is worth being precise about which reproducibility it buys.

A seed fixes the draw: the sketch matrix Ω is a deterministic function of it, so two machines given the same seed sample the same subspace and pursue the same approximation. That removes the 31%, which is the large term, and it is why the practice exists.

It does not fix the arithmetic. Y = AΩ is a matrix product, which is a set of inner products, which is a set of reductions — so two machines given the same seed compute slightly different Y, take the QR of slightly different matrices, and return slightly different answers. The seed is upstream of the randomness and the reduction is downstream of it.

So seeded is not deterministic, and a test asserting bitwise equality of a seeded randomised routine’s output will fail on a machine with a different thread count, for a reason that has nothing to do with the seed. That is a specific and avoidable confusion: the failure looks like a broken seed and is not one.

The other randomised methods, and where they sit

The measurement is on a randomised SVD, and the field has three other constructions whose position on this scale is worth predicting — and, where the site has already measured the first term, stating.

A sketch-and-solve least squares. Its error is dominated by the sketch’s distortion, which is a draw and is per cents — what a sketch costs in accuracy measures it. Same picture: the draw is enormous compared with the machine.

A sketch-and-precondition solve. Here the draw affects only the preconditioner, and the answer is computed by an iteration to a tolerance, so the seed’s influence on the final answer is nearly nil — it changes the number of iterations rather than the result. That inverts the ratio: the seed’s contribution to the answer is small and the machine’s is what a stopping test is a race measures, which is not small. The two randomised methods sit at opposite ends of this essay’s figure, for a reason that is about where the randomness enters rather than about randomness.

A Hutchinson trace estimator. The probe is a draw and the variance across probes is the field’s whole subject — counting what cannot be looked at prices it. The reduction inside zᵀAz has κ = 42 by the census, so the machine’s term is tiny. Same picture again.

The pattern: when the randomness decides the answer, it dominates; when it decides only the route to an answer, it does not, and the machine is back. That is a more useful classification than randomised or deterministic, and it is not one the literature’s vocabulary makes easy to state.

Why the two are so far apart

The mechanism is worth a paragraph because the ratio is enormous and it is not a coincidence.

The seed’s variation is first order in the sampling. A different Ω samples a different subspace, and how good a random subspace is at capturing the leading directions varies by an amount the Halko–Martinsson–Tropp analysis puts at a constant factor — per cents, for the oversampling used here, which is what the upper curve measures.

The machine’s variation is first order in the rounding. A different partitioning perturbs Y in its last bits, the subspace it spans moves by a relative u/gap, and the resulting error moves by about that.

One is a statement about geometry and the other about arithmetic, and their ratio is roughly (a per cent) ÷ u ≈ 10¹⁴. Nothing about the problem chooses that ratio; it is what separates a deliberate approximation from a rounding, which is the same separation the fifth author puts between the fourth author and the fifth. An approximation somebody typed is large; a rounding the machine committed is not.

The rank sweeps the gap and does not close it

The drag runs the rank from 4 to 16 and the upper curve falls: a larger rank leaves less for the draw to get wrong, because the approximation is closer to the optimum and the variance of a near-optimal thing is smaller. The lower curve does not move, because it is a property of the arithmetic rather than of the approximation.

So the gap narrows with the rank and stays enormous. There is no rank at which they meet on a problem of this size, and the honest form of that claim is that the two quantities have different mechanisms rather than a law relating them — a much larger problem, or a much better conditioned sketch, could close the gap further, and this measurement does not say by how much.

What a probabilistic bound has to say about it

The randomised field’s guarantee is a bound that holds with a probability, and it is fair to ask whether that framework already covers the machine’s term.

It does not, and the reason is the one a bound every answer satisfies gives for the deterministic case, in probabilistic clothing. The Halko–Martinsson–Tropp bound is a statement about the distribution of the error over draws of Ω, with the arithmetic assumed exact. Every partitioning of a fixed draw satisfies it, because they all differ from the exact-arithmetic answer for that draw by 10⁻¹⁵ and the bound has per cents of room. So the bound covers the machine’s variation the way a motorway covers a bicycle: completely, and without being about it.

What would be needed to cover it properly is a bound over the joint distribution of the draw and the implementation, and nobody has written one because the second has no distribution anybody has described. The scheduler is not a random variable with a known law; it is a fact about an afternoon.

Which is worth stating because it closes a loop with the field’s first essay. There, the classical error bound could not identify an ordering because it contained no term for the order. Here, the probabilistic bound cannot either, for the same reason — and the probabilistic framework, which exists precisely to talk about answers that vary, still has nothing to say about the one source of variation nobody chose.

What had to change to measure it

A note on the instrument, because the measurement needed one thing this site did not have.

Every routine here takes an arithmetic context — the object that decides how a number is rounded, which is how precision as the knob puts the mantissa on a slider. The randomised routine did not: it computed its two matrix products in binary64, hard-coded, because until this field existed there was no reason for them to be anything else.

Threading the context through was three lines, and the interesting part is what it revealed about the one below it. The site’s matrix product accumulates its inner products in a loop rather than calling the context’s own inner product, and the two are the same arithmetic written twice — so the product could not be given a divided reduction without either duplicating it or noticing that the loop and the context’s dot compute the identical sequence of operations.

They do, exactly, for every context this site has. So the product now uses the context’s inner product when the context declares itself divided, and the loop otherwise, and every figure written before this draws the same picture. That is the shape of change this collection’s rules ask for: the fix goes where the gap is, it is opt-in so nothing existing moves, and the reason is written down where the branch is.

Where it would matter

Two cases, and naming them keeps the essay from being purely reassuring.

A rank decision from the sketch. If the singular values the randomised method returns are compared with a threshold, the comparison is the one a rank that depends on the thread count measures, and the machine’s 10⁻¹⁶ can decide it. But so can the seed’s 31%, and by far more — so the honest diagnosis there is that a rank read from a randomised approximation is a draw before it is a machine-dependent quantity, and the repair is more oversampling or a different method rather than a summation policy.

A comparison against a stored answer. A test suite that stores the output of a seeded randomised routine and compares bitwise will fail, and this is the case worth watching for, because everything about the setup says it should not. The seed is recorded, the algorithm is deterministic given the seed, and the answers still differ — which is exactly the sequence that produces an afternoon spent looking for a bug in the random number generator. What a regression test can ask for is the general answer: compare against a measured tolerance, not against bits.

What a band should be a band over

One recommendation, and it is a change to a habit rather than to any code.

A randomised method’s figure is a band across seeds because the seed is the acknowledged source of variation. This measurement says there is a second one, fourteen orders smaller, and the useful consequence is not that the band should be widened — it should not; the second term is invisible inside the first — but that the band’s definition should say what it is a band over.

The error over eight draws and the error over eight runs are different statements, and on a parallel machine the second contains the first plus a term nobody mentioned. They agree to fourteen digits here and they would not agree on a computation whose reductions are worse conditioned than a sketch’s — a randomised method applied to a residual, say, or a stochastic trace estimator on a badly scaled matrix, where the vector that hides it’s census puts the reduction at the dangerous end.

So the habit worth having is the one this site already applies to everything else: say which quantity was varied. A band over seeds is a statement about the method. A band over runs is a statement about the method and the machine, and only the second is what a reader reproducing the figure will get.

The reading for the rest of the field

This essay is the field’s own boundary, and boundaries are worth stating as clearly as claims.

Where an answer is already a distribution, the machine is not the interesting term. Randomised methods, Monte Carlo, stochastic rounding, anything whose figure is a band. Report the band, record the seed, and do not spend three operations an element on a term that is fourteen orders below the one already being reported.

Where an answer is supposed to be a number, it is. A solve, a factorisation, a rank, a definiteness verdict. Those are the fifteen essays before this one.

And the way to tell the two situations apart is not the algorithm’s name — it is whether the computation draws anything. A method that consults a random number generator has a variation it announces. A method that does not has one it does not, and the whole of this field is about the second.

One line

A seed fixes which random matrix was drawn and not how its products were summed, so a seeded randomised method is reproducible in the term that matters by a factor of 10¹⁴ and irreproducible in the term that a bitwise test reads.

At other settings

The draw moves the answer by a third; the machine moves it by a roundingA randomised rank-4 approximation of a 120 × 60 matrix, at five rates of spectral decay. The upper curve is the relative spread of the error over eight seeds; the lower is its spread over seven partitionings of one seed's reduction. The first runs from 0.0278 to 0.121 and the second from 7.32·10⁻¹⁶ to 2.51·10⁻¹⁵: at least 1.8·10¹³ between them. The machine's contribution is not zero — four to seven of the seven partitionings return distinct values at every rate — it is simply inside the width of a line the method draws for a reason it announces. This is the one field on the site where the fifth author is already dominated, and it is dominated by the one source of variation that comes with a seed attached.00.10.20.30.40.50.60.70.80.9110⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹decay rate of the spectrumrelative spread of the rank-k errorthe seedthe machinetwo kinds of variationseeds drawn8partitionings7seed spread0.12machine spread7.3·10⁻¹⁶ratio1.6·10¹⁴one of these is recordedand it is the large one
Fig. 2 At rank 4, where the draw has more to get wrong and the gap is widest.
The draw moves the answer by a third; the machine moves it by a roundingA randomised rank-16 approximation of a 120 × 60 matrix, at five rates of spectral decay. The upper curve is the relative spread of the error over eight seeds; the lower is its spread over seven partitionings of one seed's reduction. The first runs from 0.0566 to 0.484 and the second from 1.49·10⁻¹⁵ to 4.94·10⁻¹⁵: at least 1.1·10¹³ between them. The machine's contribution is not zero — four to seven of the seven partitionings return distinct values at every rate — it is simply inside the width of a line the method draws for a reason it announces. This is the one field on the site where the fifth author is already dominated, and it is dominated by the one source of variation that comes with a seed attached.00.10.20.30.40.50.60.70.80.9110⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹decay rate of the spectrumrelative spread of the rank-k errorthe seedthe machinetwo kinds of variationseeds drawn8partitionings7seed spread0.44machine spread3.3·10⁻¹⁵ratio1.4·10¹⁴one of these is recordedand it is the large one
Fig. 3 And at 16, where it is narrowest and still thirteen orders.
The randomised SVD against the optimum it cannot beatA semi-logarithmic plot of approximation error against target rank. A shaded band shows the spread across seeds, a solid line the optimal error from the exact singular values, and a dashed line the published probabilistic bound well above both.04812162010⁻¹10⁻⁰.⁵1target rank k‖A − A_k‖₂published boundrandomisedσₖ₊₁, optimalhow far apart the three areworst seed spread1.6bound / median at k = 125.9median / optimum at k = 121.960×60, 6 seeds, oversampling p = 5band is best to worst
Fig. 4 The band the randomised field already draws, for a reason it announces.
What extra columns buy a construction that never sees the matrix, over five seedsThe band is the range across five seeds and the line is their mean; the flat lower line is the best representation of rank 8 there is, which a decomposition of every block would find. With no oversampling the construction is 11.6 times behind it and the spread across seeds is 44 per cent of the mean. Eight extra columns bring it to 3.0× and the spread to 12 per cent. Both halves matter and only one of them is visible in a single run: what oversampling buys is a better answer and a more predictable one, and a figure drawn from one seed would have shown the first and hidden the second. No draw is ever better than the flat line, which is the check that the comparison is honest — a sample cannot beat the decomposition it is approximating.048121610⁻⁸10⁻⁷10⁻⁶10⁻⁵extra columns in the sample, p‖A − A_H‖ ⁄ ‖A‖the best rank-8 representationfive draws, mean and rangea band, not a lineexcess at p = 012excess at p = 83spread at p = 00.44spread at p = 80.12the optimum of this rank7.8·10⁻⁸one seed shows the meanand five show the risk
Fig. 5 What buys the width of that band down.
The same 4096 numbers, added up 26 ways, 21 different answersEach dot is one reduction of one vector of 4096 binary64 numbers whose summation condition number is 1.01·10⁸: the vector is cut into p contiguous pieces, each piece summed left to right, and the pieces combined in a tree. The vertical position is the distance from the exactly rounded sum, relative. Filled dots are the static split a fixed thread count gives; open dots are unequal splits, which is what a work-stealing scheduler produces at the same p. 21 of the 26 runs returned distinct values, spanning 1.55·10⁻¹³ — 2.3·10⁷ ulps of the answer. The dashed line is the classical bound γ₍ₙ₋₁₎Σ|xᵢ|, which every one of them satisfies with 2.58·10⁴ to spare, and which is the same number for all of them: it contains n and Σ|xᵢ| and nothing about the order.110¹10⁻¹¹10⁻⁸10⁻⁵pieces the vector was divided intodistance from the exact sum, relativethe published boundκ · uone vector, one algorithmdistinct answers21runs26spread, in ulps2.3·10⁷κ of the sum10⁸bound ÷ worst error2.6·10⁴nobody chose pand no answer is the answer
Fig. 6 The variation this field is about, on a computation that draws nothing.
What the runs disagree by, and what the bound says they mightOver ten decades of summation condition number, on vectors of 2048 numbers: the measured spread between seven partitioned reductions of the same vector, the quantity κu, and the classical error bound γ₍ₙ₋₁₎Σ|xᵢ| relative to the sum. The measured spread and κu are one curve times a constant — the ratio runs from 0.253 to 0.258 across the whole sweep, a spread of 1.021 while both quantities move by ten orders. The bound sits 7932 to 8100 above the disagreement and is identical for every ordering, which is what makes it useless for the question a reader actually has: not how wrong is this, but will the next run say the same.10²10⁴10⁶10⁸10¹⁰10¹²10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹κ of the sumrelative sizethe boundκ · umeasured spreadtwo curves and one constantspread ÷ κu, low0.25spread ÷ κu, high0.26bound ÷ spread, low7932decades swept10the spread is computablethe bound cannot see the order
Fig. 7 Its size, which is the lower curve of the hero figure in a different setting.
The summation condition number of six inner products this site already computesκ = Σ|xᵢ| ÷ |Σxᵢ| for six reductions taken from computations elsewhere on this site, at 64 terms: an orthogonality check between two columns of a Q, one component of a residual b − Ax on an ill-conditioned system, a nearly degenerate 2 × 2 determinant, a Hutchinson trace probe zᵀAz, a residual norm rᵀr, and a curvature pᵀAp. The range is 1 to 1.01·10¹⁷. The two at the safe end are sums of squares, where no term can cancel another; the three above 10¹⁰ are the orthogonality check, the residual and the determinant — which is to say every quantity a stopping test, an orthogonality test or an orientation test is written in. The reductions that are reproducible are the ones nobody makes a decision from.κ of the suma component of b − Ax1.01·10¹⁷ad − bc, near-degenerate3.6·10¹⁶qᵢᵀqⱼ, an orthogonality check7.39·10¹⁵pᵀAp, a curvature409zᵀAz, a trace probe41.8rᵀr, a residual norm1measured, not assumedhighest10¹⁷lowest1above 10¹⁰3terms64sums of squares are safeand nobody decides anything from one
Fig. 8 Which reductions inside a sketch would be worth a policy.
Six ways to add up a vector, priced against what they returnBinary64 operations per element on the horizontal axis and relative error on the vertical, for one vector of 2,048 numbers with a summation condition number of 1.05·10⁶. Filled markers are the policies whose answer does not depend on the order the terms arrive in; open markers are the ones whose answer does. The cheapest order-independent policy costs 3 operations an element — a divide, a round and an add — and is 2.29·10⁻⁷ wrong; the most accurate policy here is pre-rounded, two passes at 7. Nothing sits in the bottom left. The cost of an answer that is the same on every machine is between three and twelve times the cost of an answer that is not, and the two-pass pre-rounded policy is the one worth knowing about: seven operations, order-independent, and accurate.02468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸binary64 operations per elementrelative errorruntime orderfixed partitionpre-rounded, one passpre-rounded, two passescompensated (Kahan)exact accumulationwhat determinism costsreproducible policies3cheapest, ops/element3its error2.3·10⁻⁷two passes10⁻¹⁷ordinary, 8 pieces2.7·10⁻¹¹nothing is cheap and exactthe middle of the figure is the answer
Fig. 9 And what one costs, for the cases where it is worth it.
The numerical rank of one matrix is 10, 12, or somewhere betweenSingular values of one 60 × 14 matrix whose spectrum falls by a fixed factor per index, so there is no gap anywhere and the threshold decides the rank. Each curve is the same matrix, its Gram matrix formed with the inner products summed in a different number of pieces. The curves lie on top of each other for the first several values and separate below about 7.3·10⁻¹³, which is where forming AᵀA has put the rounding. The dashed line is the threshold, σ₁ · 10⁻¹⁴. Counting the values above it gives 12 at p = 1, 12 at p = 2, 12 at p = 4, 10 at p = 8, 10 at p = 16, 11 at p = 32, 11 at p = 60 — the rank of one matrix, as a function of how many workers were available. Not a digit of an answer: the number of columns a model built from this matrix would have.13579111310⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹index ksingular valueσ₁ · 10⁻¹⁴, the thresholdone matrix, three rankspartitionings7lowest rank10highest rank12threshold7.3·10⁻¹⁴σ₁7.3the curves separate in the noiseand the threshold is drawn through it
Fig. 10 A rank decision that the machine can move.
The smallest defect a regression test can catch, on a machine that will not repeat itselfA 150 × 150 system with κ = 10⁴, solved by conjugate gradients to 10⁻¹⁰ on six partitionings. The shaded band is how far the answer moves across those six when nothing at all is wrong: 3.24·10⁻¹², relative. Each pair of dots is one defect — a single entry of the matrix changed by a relative δ, an assembly slip or a stale coefficient — solved on the same six machines, showing its nearest and furthest run. A defect is catchable only when its nearest run clears the band, because a test whose threshold sits inside the band fails a correct build. Everything at or below 10⁻¹³ overlaps and is invisible; 10⁻¹² is the smallest that separates, at 4.61·10⁻¹². So the tolerance exists, it is bracketed between 3.24·10⁻¹² and 4.61·10⁻¹² — a factor of 1.42 — and it is neither zero nor the 10⁻⁸ that usually gets typed.-15-13-11-910⁻¹³10⁻¹¹10⁻⁹10⁻⁷log₁₀ of the defect, relative to the entry it sits inhow far the answer movedthe machine, on its owna tolerance with two sidesmachine band3.2·10⁻¹²smallest caught10⁻¹²its nearest run4.6·10⁻¹²defects hidden3window, factor1.4below the band nothing is visibleand above it everything is
Fig. 11 The test that fails on a seeded routine for a reason that is not the seed.
One system, one tolerance, and 11 different amounts of workConjugate gradients on a 200 × 200 symmetric positive definite matrix with κ = 10⁴, stopped when the relative residual falls below 10⁻¹⁰, run at each of 13 partition counts. The only thing that differs between the runs is how many pieces the two global inner products were summed in — which on a real machine is the number of workers. Iteration counts run from 674 to 690, 11 of them distinct, a spread of 2.4% of the work. Every run converged and every answer is right to the accuracy asked for; the forward errors span 6.31·10⁻¹¹ to 1.08·10⁻¹⁰, a factor of 1.72. What differs is not a digit at the end of an answer — it is the bill, and it is an integer.110¹670673676679682685688691694pieces the inner products were summed initerations to the tolerance674, the cheapest run690, the dearestthe same solve, pricedpartitionings run13distinct counts11spread, per cent2.4best forward error6.3·10⁻¹¹worst1.1·10⁻¹⁰one matrix, one toleranceand the cost is the machine's
Fig. 12 A computation with no draw in it at all.
160 single-probe estimates of one 40×40 trace, from the two standard probe distributionsTwo clouds of points, each one estimate of the trace from one random vector. Both are centred on the true value of 171.14 — the estimator has no bias at all — and the dashed bands are the standard deviation each distribution is known in closed form to have: 59.14 for the ±1 probe and 72.01 for the normal one. Measured over these draws they come out 56.68 and 68.57.027548110813544119.306194.613269.919345.226420.532drawzᵀAz from one probenormal±1two routes to one spreadthe trace171±1 spread, predicted59±1 spread, measured57normal ÷ ±11.2no bias in either cloudand one of them is narrower for a reason
Fig. 13 Another deliberate draw, where the choice of probe is the decision.
Two trace estimators against their budget, on a 80×80 matrix whose spectrum decays at 0.85Two curves of relative error against the number of products with A, both axes logarithmic, as medians over 32 seeds. Hutchinson's fitted exponent is -0.54 and Hutch++'s is -2.55. The deflation changes the exponent rather than the constant, which is what makes it worth two thirds of the budget.10¹10²10⁻⁴10⁻³10⁻²10⁻¹1products with Arelative errorHutchinsonHutch++measured at equal costfitted rate, Hutchinson-0.54fitted rate, Hutch++-2.5error at 96, Hutchinson0.024error at 96, Hutch++4.4·10⁻⁴both axes count products with Aso the sketch is paid for in the picture
Fig. 14 And the rate at which averaging over draws buys it down.
What a rank-10 approximation can achieve, by spectrumA semi-logarithmic plot of singular value against index for three spectra — geometric decay, algebraic decay, and flat — with the rank-ten approximation error marked on each.1112131415110⁻³10⁻²10⁻¹1index jσⱼσ11geometric, 0.85ʲalgebraic, j^−1.00flatmeasured, and equal to σ₁₁rank-10 error, geometric0.2rank-10 error, algebraic0.091rank-10 error, flat160×60, spectrum chosen rather than the entriesthe matrix decides, not the method
Fig. 15 The decay the hero figure’s horizontal axis sweeps.
Error of the best rank-k approximation to a 12×12 matrixApproximation error against k on a logarithmic axis, with the measured error and the next singular value drawn as separate curves lying exactly on top of one another.123456789101110⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1rank k of the approximation‖A − Aₖ‖measured, 2-normσₖ₊₁, from theorymeasured, Frobeniusthe first two agreeto 2·10⁻⁸worst |‖A−Aₖ‖₂ − σₖ₊₁| / σₖ₊₁2·10⁻⁸worst Frobenius discrepancy2·10⁻⁸κ = 10⁹; 30 random rank-3 matrices, none closerthe error is σₖ₊₁
Fig. 16 The approximation being measured.
Backward and forward error against the condition numberA log–log plot over twelve decades of condition number. The backward error is a flat line at ten to the minus sixteen; the forward error rises in proportion to the condition number.110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)relative errorforward errorbackward errorpredicted: κ · u8×8, 20 seeds per κ; dashed is the worstthe problem worsens, not the method
Fig. 17 The distinction that survives both kinds of variation.
The exact solution of a 13×13 Hilbert system beside the computed oneTwo columns of numbers: the exact answer, which is the integers one to thirteen, and the answer double-precision elimination returns, with the number of correct digits beside each.H13 x = b, b formed exactly so that x = (1, 2, …, 13)12345678910111213exact1.00002.00003.00133.97865.18864.993010.46720.048921.2657-2.575319.21478.906013.5113computed6.6 correct digits4.8 correct digits3.4 correct digits2.3 correct digits1.4 correct digit0.8 correct digitno correct digitsno correct digitsno correct digitsno correct digitsno correct digits0.6 correct digit1.4 correct digitbackward error2.2·10⁻¹⁷κ = 1.7·10¹⁸The algorithm solved a neighbouring problem perfectly. That problem's answer is this one.right-hand side built in BigInt rationalsthe truth is known
Fig. 18 The standing that makes a spread a measurement.
Five summation policies, 400 permutations each, and how many answers each returnedThe same 1,024 numbers, summation condition number 10⁸, presented in 400 different orders. The bar is the number of distinct binary64 values the policy returned; the figure beside it is the worst relative error it made. A single accumulator returns 303 values and eight pieces return 72; Kahan's compensated loop is the most accurate of the three at 4.96·10⁻¹⁰ and still returns 119. Pre-rounded summation returns one value, at an error of 4.91·10⁻⁶ — four orders worse than the compensated loop and the same on every machine. Exact accumulation returns one value and the right one. The comparison is bitwise because the claim is bitwise: a tolerance here would pass everything.distinct answersone accumulator303eight pieces72compensated119pre-rounded1exact1worst error 1.17·10⁻⁸worst error 4.61·10⁻⁹worst error 4.96·10⁻¹⁰worst error 4.91·10⁻⁶worst error 0bitwise, or not at allpermutations400one accumulator303pre-rounded1its error4.9·10⁻⁶compensated error5·10⁻¹⁰accuracy and agreement are different propertiesand the accurate one is not the agreed one
Fig. 19 The property a seed does not buy.
The error of a reduction is a walk, and the number of pieces changes which walkRunning error of two reductions of the same 2048 numbers, against how many terms have been consumed: one accumulator, and 8 pieces combined at the end. Each is the distance between what the arithmetic has accumulated so far and the exact sum of the same terms, carried in a compensated pair so the instrument does not round. The two separate within the first few terms and never meet again, ending at 7.56·10⁻¹⁴ and 2.41·10⁻¹⁴. The mechanism is in the horizontal axis: a rounding is committed at every partial sum and its size is that partial sum's spacing, and this vector's running total reaches 32.1 on the way to an answer of 1.63·10⁻⁵. Dividing the work shortens each walk, so the mean error over eight vectors falls from 4.78·10⁻¹⁴ at one piece to 8.14·10⁻¹⁵ at sixty-four: more workers is more accurate, which is the opposite of what the word *parallel* suggests here.051210241536204810⁻¹⁷10⁻¹⁴terms consumederror accumulated so farone accumulator8 piecesthe steps are the partial sumspeak partial sum32the answer1.6·10⁻⁵error, one piece7.6·10⁻¹⁴error, 8 pieces2.4·10⁻¹⁴mean at p = 648.1·10⁻¹⁵the walk sets the sizeand nothing sets the value
Fig. 20 The mechanism behind the lower curve.
Forward error of a 6×6 Hilbert solve at eight precisionsA bar for each significand width from 12 to 53 bits showing the relative error in the computed solution, with the condition number times the unit roundoff marked as a prediction.κ = 1.5·10⁷ · the exact answer is (1, 2, …, 6)12 bits3.316 bits0.8620 bits4.324 bits0.09330 bits7.6·10⁻⁴36 bits6.2·10⁻⁶43 bits2·10⁻⁷53 bits4.5·10⁻¹¹dashed: κ · unit roundoffone matrix, eight arithmeticsmeasured against a known answer
Fig. 21 The knob that moves the lower curve and not the upper one.

Where this goes next

04812162010⁻¹10⁻⁰.⁵1target rank k‖A − A_k‖₂published boundrandomisedσₖ₊₁, optimalhow far apart the three areworst seed spread1.6bound / median at k = 125.9median / optimum at k = 121.960×60, 6 seeds, oversampling p = 5band is best to worst A bound that holds with probability Every other guarantee on this site is deterministic. The randomised low-rank approximation offers one that holds with a probability, the seed changes the answer, and the honest figure is a band rather than a line. 110¹10⁻¹¹10⁻⁸10⁻⁵pieces the vector was divided intodistance from the exact sum, relativethe published boundκ · uone vector, one algorithmdistinct answers21runs26spread, in ulps2.3·10⁷κ of the sum10⁸bound ÷ worst error2.6·10⁴nobody chose pand no answer is the answer The same program, twice One vector of 4,096 numbers, one summation algorithm, one precision, twenty-six runs — and twenty-one different answers. Nothing in the program chose between them, every one of them satisfies the textbook bound, and the exactly rounded answer is not among them. 02468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²binary64 operations per elementrelative errorruntime orderfixed partitionpre-rounded, one passpre-rounded, two passescompensated (Kahan)exact accumulationwhat determinism costsreproducible policies3cheapest, ops/element3its error0.0024two passes10⁻¹⁷ordinary, 8 pieces3.6·10⁻⁷nothing is cheap and exactthe middle of the figure is the answer Accuracy and agreement are different properties The most accurate policy on this site's summation figure returns 119 different answers, and the one that returns a single answer is four orders less accurate. Neither property implies the other, and the vocabulary has one word for both.

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.

Bitwise reproducibilityOversamplingProbabilistic boundsRandomised SVDReduction orderRun-to-run variationSeeded generatorSketching