Numerical Linear Algebra
where the algebra stops being the arithmetic
Theme

The thread: Exact ground truth — page 4

Essays 73 to 96 of the 181 on this theme, in the same order.
all 2^16 subsets searchedboth minima, one order0.97minimum degree optimal0.82worst fill overshoot1.1worst work overshoot1.111.021.041.0611.041.081.121.16fill ÷ the least filloperations ÷ the leastovershoot squaredon the diagonal: the two overshoots are equalon the upper curve: the arithmetic overshoot is the square Sparsity, and what elimination costs

Two minima that are one minimum

The order that decides the memory found the operation count behaving like the square of the fill, which leaves room for an order with slightly more fill but a shorter heaviest column to do less arithmetic. Searched exactly over every elimination order on forty graphs, that order does not exist: one order attains both minima on thirty-nine of forty, and on the fortieth the least-fill order's arithmetic is 1.0099 times the least. Minimum degree attains both on the same thirty-three graphs and neither on the same seven.

 total inner iterationscold at η = 1e-107016scaled warm start6837unscaled728910⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10³10³.⁵10⁴forcing term ηinner iterationsthe previous stepstarted at zerothe previous step, scaledthree curves within eight per cent of each otherand the unscaled guess is the worst of the three When the problem arrives again

A guess worth two per cent

The previous Newton step looks like a free guess at the next one, and it is worth nothing. Started from it unscaled, the inner solve costs 4 to 61 per cent more than starting from zero, because the guess is 15 to 209 times too large. Scaled by the ratio of the two residual norms it is the right size and halves the starting residual — which buys a constant handful of inner iterations, not a share, because conjugate gradients costs the logarithm of its tolerance.

 48 products, 24 drawsbest share, decay 0.70.45best share, decay 0.950.2worst cost of a third2.800.10.20.30.410⁻³10⁻²10⁻¹share spent on the sketchmedian relative errorthe published thirddecay 0.7decay 0.85decay 0.95large dots: the best split on each curveand the dashed line is the one a library picks Randomised, and the guarantee that changes kind

The split nobody is in a position to choose

Hutch++ spends two thirds of its budget on a sketch and a third on probes, and the third is published as a constant. Swept across six rates of spectral decay at a fixed budget of 48 products, the best share is 0.45 on the fastest and 0.00 on the slowest — sketch nothing at all — and the published third costs between 1.09 and 4.11 times the best error. The decay that decides it is readable from the sketch's own singular values, for products the estimator was going to spend anyway.

 10⁻⁹10⁻⁶10⁻³110³10⁶13212937κ · usignificand bitsκu = 1a bound was provedthe method refusedit never returns a wrong boundlargest κu with a proof0.45smallest κu without one0.89cases refused, of the grid13a refusal is not a wide bound — it is no bound at alland it is the only failure mode here The arithmetic underneath

A bound that is proved

Every error statement in the essays before this one is a measurement of one run. Interval arithmetic makes a different kind of claim — the answer lies in this set, for this input, with no probability attached — and its failure mode is that it returns nothing at all. On a Hilbert system it proves a bound 23 times the error it bounds, and one size later it refuses.

 10³10⁶10⁹10¹²10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹κ(A), identical for both problemsrelative error in the answerthe weak directions in the constraint's null spacethe weak directions in the constraint's own rowsone κ(A), two problemsκ(A), both10¹²κ left, constrained1κ left, free10¹²error, constrained4.7·10⁻¹⁶error, free3·10⁻⁴between them6.4·10¹¹a constraint is informationand κ(A) does not know it arrived Least squares, and the road not to take

The condition number that does not know

Two constrained fits with the same size, the same number of constraints and the same κ(A) to twelve figures. One returns 4.7·10⁻¹⁶ and the other 3.0·10⁻⁴. What separates them is the conditioning of A restricted to the constraint's null space — 1.00 against 10¹² — which every solver computes on the way and none reports.

 unpreconditioneddimension a step1.2best iterate carries24at step20τ = 10⁻³, past the edgedimension a step3.6best iterate carries33its error0.4837111519232731353910⁻¹10⁻⁰.⁵1effective dimensionrelative errorthe arc: dimension 8.0 to 24.0none10⁻⁰.⁵10⁻¹10⁻¹.⁵10⁻²10⁻².⁵10⁻³large dots: each run's own best iteratethe answer sits at one effective dimension Methods that were designed apart

The parameter neither knob is

A preconditioned run has a cutoff and a step count, and neither is the regularisation parameter. The parameter is the effective dimension of the iterate: every cutoff that works puts its own best at 23.7 to 24.3 of it, where the unpreconditioned run's best sits at 23.2, and what the cutoff buys is the rate — 1.27 of it a step with no preconditioner and 3.53 with one. The edge is where a single stride is longer than the distance left.

 an ordering that is theregreedy at n = 764best ordering at n = 72its largest multiplier1456710¹10²matrix size ngrowth factorgreedy, ties forwardsgreedy, ties backwards, ε = 10⁻¹²greedy, ties backwards, ε = 0the best orderingthe best order is 2 3 4 5 6 1 at n = 6one cyclic shift of the rows Elimination, and the swap

The order the greedy rule cannot choose

Wilkinson's matrix is the standard demonstration that partial pivoting's growth bound of 2^(n−1) is attained. It is attained by the row order the greedy rule picks, and not by the matrix: a single cyclic shift of the rows gives growth 2 at every size, with no multiplier above one. At n = 7 that is 64 against 2. And perturbing one entry by 10⁻¹² leaves the good order exactly where it was while putting every tie-break of the greedy rule back on 64.

 40 drawsproducts at target 0.01696deflated277draws inside the target0.810⁻²10⁻¹10⁻²10⁻¹target standard errorrelative error reachedworst draw, no deflationmedian error, no deflationmedian error, deflatedthe grey diagonal is a calibrated rulethe medians are on it and the worst draws are not Randomised, and the guarantee that changes kind

A rule that reads only its own probes

A trace estimator is a mean of independent samples, so its own standard error is estimable from the samples and a stopping rule needs nothing the estimator does not already have. Over forty draws it is calibrated in the middle and not at the edge: at a target relative standard error of 1% the median error reached is 5.3·10⁻³ and the worst of forty is 2.9·10⁻² — three times the target. And the cost of the target is the estimator's own square root: tightening it from 3% to 1% takes the median probe count from 75 to 696.

 what one line doesinner work saved, worst case0.09best case0.27forward error cost, worst263610⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴outer toleranceforward errorerror, with the floorerror, without itinner work, rescaledthe grey diagonal is the residual the test asked forboth runs meet it and one is far more accurate When the problem arrives again

One line that buys a quarter of the run

The adaptive forcing rule has a floor on it that no published statement of the rule carries: do not solve a step to an accuracy the outer loop will not use. Removing it costs 9 to 27 per cent of the whole inner run. Keeping it costs between 23 and 2,600 times the forward error — accuracy the residual test never asked for and both runs satisfy the test either way. The line is a trade between a residual and an error, and which of the two the caller meant decides whether it is a saving.

 10×10, ±6determinant, bits27Hadamard's bound36median slack10024680510152025303540elimination stepbitsHadamard, on the minorsthe intermediatesevery intermediate is a minor of the originalso a bound on the minors bounds the run Exact arithmetic, and what it costs instead

A bound on every intermediate at once

Fraction-free elimination's intermediates are minors of the original, which is a theorem about exactness. It is also a bound: Hadamard's inequality applies to every minor, so one inequality bounds the whole run before it starts. The bound on the k-th step is the one on (k+1)×(k+1) minors, not the one on the whole matrix — and on a 10×10 with entries in ±6 the difference is ten bits, with the run reaching 2.7 bits a step against the bound's 3.4.

 the certificatecertificate, iterate1.5its error1.8·10⁻¹⁴the iterate's own error0.14the tightest μ testμ < 10⁻¹³, iterate15its error1.6·10⁻¹²one attempt ÷ one step0.130246810121410⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹interior-point iterationrelative error returnedμ < 10⁻⁴μ < 10⁻⁶μ < 10⁻⁸μ < 10⁻¹⁰μ < 10⁻¹³the certificatethe iterate it is built fromthe grey line is the certificate's own errorno tolerance on μ reaches it, at any iterate The matrix a constraint makes

A test with no tolerance in it

An interior-point method's own stopping test is a tolerance on μ, and at the tightest it can be set to it stops after 15 iterations with 1.6·10⁻¹². A crossover from the iterate at 1.5 returns a point whose error is 1.8·10⁻¹⁴ — ten times sooner and a hundred times better, from an iterate carrying one correct digit. One attempt costs an eighth of a step, and the guess's own margin says which iterate to spend it on.

 11.522.511.52xyexactly one roota verdict, not a bound‖I − C F′(X)‖0.28width of X0.8width of K(X)0.23strictly inside is a proofand overlapping is nothing at all The arithmetic underneath

Proving the answer is in the box

Every other method here computes a number and estimates how wrong it is. This one returns a verdict: there is exactly one solution in this box, or there is none, or — the honest third outcome — nothing can be said. Two of the three are proofs about infinitely many points from finitely many operations.

 10¹10³10⁵10⁷10⁹10¹¹10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1κ(A), the conditioning of the fitrelative error in the answerthe saddle-point route, in floating pointdashes: forming AᵀA, then solving exactlythe method of weighting, τ = 10⁸the null-space routethe reference was a methodκ(A)10¹¹κ of what is left4.9·10⁶null space1.9·10⁻⁹saddle point4.6·10⁻⁴forming AᵀA alone3.4·10⁻⁴weighting3·10⁻⁹the damage is in the formingand not in the solving Least squares, and the road not to take

The reference was a method

The optimality conditions of a constrained fit contain AᵀA, so solving them is the road that squares the problem wearing a block structure. At κ(A) = 10¹¹ the route that never forms a cross-product returns 1.89·10⁻⁹ and the route that does returns 4.64·10⁻⁴ — and forming AᵀA and then solving it in exact rationals returns 3.45·10⁻⁴, so nearly all of the loss happens before any elimination begins.

 20 matricespeak, every rule29the determinant's own length29area, smallest ÷ natural0.9602468051015202530elimination stepbits, longest entrythe determinant: 29 bitsswap only on a zerolargest pivotsmallest nonzero pivotthree orders, three sequences of minorsand one last entry they all arrive at Exact arithmetic, and what it costs instead

Three orders and one last entry

Over the integers there is no stability to pivot for, so a fraction-free elimination swaps rows only when the pivot is zero. Choosing a pivot for length instead does change the sequence of minors — the smallest-nonzero rule makes seven exchanges where the natural order makes none and keeps the profile two bits lower through the middle. It cannot change the peak. The last entry of the elimination is the determinant, and the determinant does not know what order it was computed in.

 051015202530354010⁻⁴10⁻³10⁻²10⁻¹110¹rank of the basiserror, and what the rule readsprobe × 7.98largest probetrue error, Frobeniustrue error, spectralσₖ₊₁, the floorgeometric 0.8, one run, ten probesoptimal rank for ε = 0.111basis reaches ε at rank15probe below ε at rank20published estimate below ε at rank34ε = 0.1the dotted line across is ε = 0.1each rule stops where its curve crosses it Randomised, and the guarantee that changes kind

The rank a certificate charges

A randomised range finder can choose its own rank: grow the basis a column at a time and stop when ten fresh probes all come back short. With the published safety factor it never stopped early in any draw measured, and on a matrix whose singular values fall by 0.8 a step it stopped at rank 30 for a tolerance the best rank-11 approximation already meets. The nineteen extra columns are three separate prices — four for building the basis from random vectors, five because a probe reads more than the spectral norm, and ten for the constant — and the spectrum decides which of them dominates.

 10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶050100150200250relative residual tolerance of every solveinner steps over twenty membersprevious answerline, last twoparabola, last threea straight path, twenty members, drift 0.02tolerance 10⁻⁶: previous answer62tolerance 10⁻⁶: line11tolerance 10⁻⁶: parabola17tolerance 10⁻¹⁰: previous answer160tolerance 10⁻¹⁰: line12tolerance 10⁻¹⁰: parabola14tolerance 10⁻¹⁴: previous answer261tolerance 10⁻¹⁴: line17tolerance 10⁻¹⁴: parabola23tighter to the lefteach point is a whole run of twenty When the problem arrives again

A straight path has nothing for a parabola to fit

The line through the last two answers beat the parabola through the last three on a drifting sequence, and the reason offered was that the parabola amplifies the stored answers' error. Tightening the solve tolerance from 10⁻⁶ to 10⁻¹⁴ should have reversed that, and it does not: the line needs 7 to 18 inner steps over twenty members at every tolerance and the parabola 14 to 23. The sequence's roots move along a straight line, so the line is exact and there is nothing else to fit. Bend the path by a part in ten thousand and the parabola wins below 10⁻⁹, by 105 steps to 75 at 10⁻¹⁴.

 1220283644526068768492100101214161820grid points nrelative error against the continuous signal, per centsampled kernel, hatsintegrated, hatsintegrated, splinespline, no λ1% noise per sample, median of sixteen drawssampled kernel, hats: 16 points0.18integrated, hats: 16 points0.16integrated, spline: 16 points0.16sampled kernel, hats: 96 points0.14integrated, hats: 96 points0.14integrated, spline: 96 points0.14spline, no λ, its best grid0.15dotted: the 96-point answerevery point is a grid with its own λ Regularisation, and the answer that is chosen

The grid on which the discretisation stops mattering

Without regularisation, integrating the blur's kernel against cubic splines beat sampling it at 0.1% noise and lost to it at 1%. Give each discretisation its own best λ on every grid and the difference shrinks to nothing where grids are fine — 0.17, 0.28 and 0.20 per cent apart on 96 points at the three noise levels, with every discretisation choosing the same λ — and stays at 17 to 18 per cent on 16 points. The choice between them is a choice of how coarse a grid can be: at 0.1% noise the integrated discretisations reach the fine-grid answer on 26 points and the sampled one needs 40.

 where each run leaves the arcnarrow blur, directions33the collection's blur, directions22wide blur, directions15the answer's own dimensionnarrow blur32the collection's blur23wide blur1501020300123456directions the preconditioner divideseffective dimension a stepnarrow blurthe collection's blurwide blurrings: the first cutoff past which most of the run misses the arcthey sit at three different strides Methods that were designed apart

A count that marks the edge and not the pace

The number of directions a truncated preconditioner divides is counted for free when it is built, and it was proposed as a stand-in for the stride it buys. On three blurs it is not one — the runs leave the answer at strides of 5.71, 3.44 and 2.41. What the count does predict is the edge: on all three blurs, at two noise levels, a run stops landing on the answer's path within five per cent of the point where the count reaches the answer's own effective dimension. And the halved cutoff rule, measured on one blur, crosses that line on the narrowest.

 00.250.50.75100.250.50.751xuexactcentral differencesupwindthe oscillation is exact‖Ax − b‖/‖b‖ for the central answer4.6·10⁻¹⁸values outside [0, 1]16worst excursion0.52the dashed lines are 0 and 1, which the equation guaranteesno solver was involved Iterating, instead of factorising

The stencil that is not symmetric

Past a cell Péclet number of exactly one — measured by bisection at 1.0000000000000002 — the central-difference solution of a convection–diffusion problem oscillates from point to point and leaves the interval the equation guarantees, at 16 of 31 grid points. It is the exact solution of its own linear system, to 4.6·10⁻¹⁸. No solver was involved.

 grey: proved empty · filled: proved to contain exactly one roota covered squareboxes proved empty42boxes proved unique2undecided0operator evaluations87every rectangle carries a proofand the two crosshairs are where the roots are The arithmetic underneath

Where the box is cut

A branch-and-bound with an interval operator settles a whole square — two roots proved unique, forty-two regions proved empty, nothing left undecided, in 87 evaluations. Move the roots so one lands on the first bisection and it proves nothing at all, at any depth. Cutting at 0.485 instead of 0.5 finds both, in a quarter of the work.

 57911131517192110⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹vertices of the complete graphrelative sizethe algorithm is not the problemsizes counted18worst relative error9.4·10⁻¹⁵first wrong at n =16digits in the answer17spacing of doubles there8largest integer a double holds9·10¹⁵the elimination stays at the rounding levelthe format runs out The matrix that is a graph

A count that comes out of a determinant

The number of spanning trees of a graph is the determinant of its grounded Laplacian, so it is a whole number known in advance. The elimination that computes it is backward stable at every size — and from sixteen vertices the answer is wrong, because the count has seventeen digits and a binary64 has sixteen.

 010203040run, by bend then tolerancesteps beyond the better fixed degreestraightbend 10⁻⁵bend 10⁻⁴bend 0.001bend 0.01bend 0.1● second difference ■ residual at both ○ wrong fixed degreethirty runs: steps beyond the better degreesecond difference: runs matching the better degree, of 3026second difference: worst excess, steps5residual at both: runs matching the better degree, of 3029residual at both: extra residuals, in steps4.5wrong fixed degree: worst excess, steps35zero is the better degree, known in advanceeach group of five is one bend When the problem arrives again

The degree the history chooses

A sequence of solves can start each member from the line through its last two answers or the parabola through its last three, and which is better depends on how much its path bends — which a code does not know. Over thirty runs of bend and tolerance, always taking the line costs 456 inner steps more than the better choice; always taking the parabola costs 33. A free rule reading the stored answers closes that to 11. A rule that evaluates the residual at both starts picks the better one on 29 runs of 30, and pays 135 steps for the evaluations.

 on 96 pointsno breakpoint0.12two jumps0.05doubled knots0.13one box0.013the box on fewer points16 points0.0526 points0.02248 points0.00710203040506070809010010⁻²10⁻¹.⁵10⁻¹grid pointsrelative error, best λno breakpointtwo jumpsdoubled knotsone boxevery reading spends the same n unknownsand is given its own best λ on each grid Regularisation, and the answer that is chosen

A corner the penalty can afford

Every smooth reading of the deconvolution's grid needed about forty points and then stopped improving, and the step was the suspect. Give the step one coefficient of its own and forty-eight points reach an error of 0.0070 at 0.1% noise, against 0.118 for the best smooth reading on ninety-six — the step was most of the error. But the same step given two coefficients recovers half as well, and given a doubled node at each edge it recovers worse than no breakpoint at all, while representing the signal to 0.07%. What decides is what the penalty is charged for the corner, and whether the data can say where it is.

 4 numbers, coefficients to 30found relations72with a gap of a digit or more54accidents56accidents with that gap05101520253001234decimal digits the numbers are scaled togap, in digitsexact relation foundnot a relationthe room a relation hashorizontal: a gap of one digitdashed vertical: the digits a double has Exact arithmetic, and what it costs instead

The room a relation has to stand out

A lattice search for an integer relation returns its shortest vector, and the proposal was to return the gap to the next one as well, so a caller could tell a relation from an accident. Measured, the gap is a certificate with a budget: the digits the numbers really have, shared among all but one of them, less the size of the relation. A found relation's gap sits half a digit under that budget, accidents stay near zero, and a one-digit gap vouches for 81 of 96 relations among three numbers and for 1 of 35 among six. The test numbers the proposal came from turned out to have relations of their own.

All themes