Numerical Linear Algebra
where the algebra stops being the arithmetic
Theme

The thread: Measured, not assumed — page 14

Essays 313 to 336 of the 545 on this theme, in the same order.
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.

 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.

 110¹-101pieces the inner product was summed inqᵢᵀqⱼ ÷ 2.78·10⁻¹⁷the true valuethe norm and its partsdistinct values5of runs10pairs with no fixed sign125of pairs1128κ of this inner product1.1·10¹⁷‖QᵀQ − I‖ moves by1the aggregate is stableand no entry of it is The answer that depends on the machine

An inner product with no fixed sign

‖QᵀQ − I‖ is how this site turns "orthogonal" into a number, and across ten partitionings it moves by 2.4%. The entries it is built from are not so lucky: 125 of the 1,128 off-diagonal pairs take both signs, and one of them takes five different values including zero.

 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.

 22.539343.078693.618034.157384.6967210⁻¹110¹10²stiffness damping βoverdamping marginβ* = 3.23607two routes to a boundaryclosed form β*3.2by certificate3.2difference4.7·10⁻¹³bisection steps44a factorisation that completesand a sine, agreeing to twelve digits The eigenvalue problem that is not linear

A class a longer chain takes away

Symmetry survives a bigger problem. Hyperbolicity does not. The damping that certifies a chain of seven masses is refused by a chain of eight, the damping the class demands grows like the length without bound, and the certificate has to be earned again at every size — which costs one Cholesky, and the alternative is a proof quietly inherited from a smaller problem.

 darker is smaller: 10⁻¹⁰, 10⁻⁶, 10⁻³, 10⁻¹one spectrum, two matricesspectral radius0.8reach of the 10⁻³ level1.3eigenvalues, all at0.8the circle is |z| = 1and every eigenvalue is well inside it Eigenvalues, singular values, rank

The eigenvalues that are not there

For a normal matrix the resolvent norm is exactly one over the distance to the nearest eigenvalue, so a picture of it carries nothing the spectrum did not. Move one entry above the diagonal and the region a perturbation of 10⁻⁸ can put an eigenvalue into stops being a disc and reaches out past the unit circle, while every eigenvalue stays at 0.8.

 the problem you posedA = H12b = A·(1, 2, …, 12)the problem it answered exactlyA + δA, b + δb‖δ‖ / ‖A‖ = 1.8·10⁻¹⁷the answer you wantedx = (1, 2, …, 12), exactlythe answer you gotx̂, wrong by 0.02 relativebackward error 1.8·10⁻¹⁷forward error 0.02κ = 1.8·10¹⁶κ · η = 0.33, and the measured forward error is 0.02.The algorithm is not at fault. The problem is.H12, LU with partial pivotingresidual and error differ Two errors, and whose fault they are

The fifth author

Four authors of a wrong answer have been named already and each is a statement about one computation. The fifth is not: it is what separates two computations that are both correct, it is a backward error of measurable size, and no residual, bound or condition number contains it.

 00.10.20.30.40.50.6pairings priced, on a logarithmic axisshare of networks whose optimum was missed10²316wide earlywide lateconstant 1constant 16constant widthswide earlywide late7 tensors, 60 networks: optimum foundconstant 1 [1 1 1 1 1 1]30constant 4 [4 4 4 4 4 4]30constant 16 [16 16 16 16 16 16]53wide early [16 8 4 2 1 1]27wide late [1 1 2 4 8 16]37lower and further left is bettera schedule is a width for each level Where the flop count stopped predicting the time

Widen the beam where the ranking is right

A beam that is wide at its first pairings and narrow at its last looks like the right shape, since the early commitments are the damaging ones. Measured, it is worse than no beam: at nine tensors a width of 16, 8, 4, 2 and then 1 prices 742 pairings and has a median of 1.263 against width 1's 1.062 for 120. The reverse shape — width 1 early, doubling to 16 at the end — prices 78 pairings on seven tensors and finds the exhaustive order on 37 of 60 networks, against 30 for a constant width of 4 at 161. A beam should be wide where cost so far is nearly the whole cost.

 10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³r½ recorded during one factorisationnoise that halves the growthT 6, h 0.3: 75T 9, h 0.3: 910T 12, h 0.3: 11000T 15, h 0.3: 1.3·10⁵T 12, h 0.25: 11000T 12, h 0.2: 11000T 9, h 0.15: 910measured ÷ predicted, shooting matricessmallest ratio0.92largest ratio2.4Wilkinson: recorded r½0Wilkinson: noise that halves it10⁻¹⁶one factorisation, one extra comparison a stepdashed: a factor of three either way Elimination, and the swap

A margin the factorisation records

Partial pivoting finds the second-largest candidate in every column it scans, and throws it away. Keep it, divide the gap by the growth reached at that step, and take the smallest over the steps before half the final growth has arrived. That one number, recorded by the factorisation that is already running, predicts the dense noise that halves the growth to within a factor of 0.92 to 2.4 on shooting matrices whose growth runs from 75 to 1.3·10⁵ and whose fragility spans three and a half decades — and on Wilkinson's matrix it is exactly zero.

 0123401020304050z, the effective noise ratiotrials mirrored, %1 thin: 1 × 1 model2 thin: 2 × 2 model3 thin: 3 × 3 modelper cent mirrored at z = 0.7, 600 trialsn = 3, 1 thin, 20 points9.7n = 5, 1 thin, 20 points13n = 10, 1 thin, 40 points12n = 5, 2 thin, 20 points23n = 10, 2 thin, 40 points24n = 8, 3 thin, 40 points32points: measured in n dimensionslines: a k × k determinant, no n in it Orthogonality, measured

A mirror decided in the thin directions

In n dimensions the nearest orthogonal matrix to a noisy alignment is still sometimes a reflection, and the rate at which it is does not depend on n. Three, five and ten dimensions with one thin direction mirror alike; two thin directions mirror like each other in five dimensions and in ten. The rate is the chance that a k × k matrix built from the k thin directions has a negative determinant — 21.7 per cent at a noise ratio of 0.7 for k = 2, measured at 23.0 — and it is well above k independent coin flips. With two or more thin directions the determinant correction still fires, and it no longer rescues the rotation: the answer is eleven noise-widths off whether or not it was mirrored.

 111315171921232510⁻¹110¹sketch width l, for rank 10‖(I − QQᵀ)A‖ ÷ σ₁₁GaussianHadamardone nonzero a rowthree nonzeros a rowcoherent, geometric 0.8, width 20, twenty seedsGaussian: median 0.41, worst0.78Hadamard: median 0.37, worst0.94one nonzero a row: median 3.3, worst7.1three nonzeros a row: median 0.41, worst0.99solid: median · dashed: worst of twentybelow one: better than the best rank-10 error Randomised, and the guarantee that changes kind

A sketch that finds the columns it can see

A sparse sketch with one nonzero in each row is twenty times cheaper to apply than a Gaussian one, and on a matrix whose important directions are spread across its columns it finds the same range: a median error of 0.45 against 0.43. Put the same ten directions into ten particular columns and it is eight times worse — 3.33 against 0.41, with a worst draw of 7.1 — because two important columns hashed to one bucket are one direction. Three nonzeros a row repair it at a sixth of the Gaussian's cost, and a randomised Hadamard transform never had the problem.

 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.

 edge of the numerical rangespectrum, -3.49zero37.9-0.986-3.496.59unstable one-sided models, of nineteen placements051015-3-2-1.5-1-0.500.511.522.53cond 1.4·10⁶cond 112t, the rescaling exponent — the k-th state is multiplied by γ to the power tk; t = 1 symmetrisesorder 1order 2order 3order 6the transfer function is the same at every tonly the inner product changes Reduction, and what a model is for

A certificate written in coordinates

Every one-sided reduced model of the convection–diffusion system was stable, because its poles cannot leave the numerical range and the range sat in the left half plane. Rescale the state by a diagonal matrix and nothing about the system changes — not its eigenvalues, not its transfer function, not one pole of any two-sided model — but the numerical range moves. At Péclet 40 a rescaling with condition number 260 pushes its edge to +6.6 and ten placements of nineteen return unstable one-sided models. Projecting in the inner product of a Lyapunov solution puts the certificate back in any coordinates.

 80 matrices, τ = 0.1, ties to the largestno column search, median fill244one column136every column109share of the gain at one column0.804896144192240columns the search may look atmedian fill123468121624allno column search at allmedian fillmedian growthworst growth — see the captionthe fill is the quantity the width buysthe worst case is the draw Sparsity, and what elimination costs

How few columns the search needs

A full row-and-column pivot search is quadratic in the active submatrix at every step, and no library performs one. Looking at a single sparsest column takes the median fill from 244 to 136 where the full search reaches 109 — four fifths of the benefit for a linear scan — and that share is 79, 83, 80, 89 and 92 per cent across five thresholds. The worst growth appears to favour the narrow search by a factor of six, and on the next draw it favours the wide one by two.

 1357911131510⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1k, where h = 1 − 10⁻ᵏrelative error of 1 − hsubtractwith a correction stepcorrection kept as a pairfrom the reflectors40 × 6k = 12, subtracting1.1·10⁻⁴k = 12, with a correction1.1·10⁻⁴k = 12, from the reflectors3·10⁻¹⁵reflector operations900dashed: a unit of roundoff over the divisorthree routes sit on it and one does not Least squares, and the road not to take

The factor a sparse code keeps anyway

Every deletion diagnostic divides by one minus a leverage, and computing it as a subtraction loses a digit for every decade the leverage is from one. The route that does not subtract needs the orthogonal factor, which a sparse factorisation is supposed not to have. Three repairs that avoid it all fail at exactly a unit of roundoff over the divisor — and the fourth, which reaches the orthogonal factor through the Householder vectors a sparse code keeps in order to solve anything at all, returns the same bits as a stored factor in 900 operations.

 n = 512, ε = 10⁻⁸operations over stored numbers2cheapest leaf, arithmetic alone16cheapest leaf at 0 a block16097194291388485leaf sizeoperations per unknown48163264the arithmetic aloneand the blocks it reacheslarge dot: the cheapest leaf at this chargethe lower curve is the storage curve doubled Neither sparse nor dense

A second objective that is the first one doubled

Counting the operations a hierarchical product does was supposed to give the leaf size a second optimum, somewhere other than where the storage puts it. The count is 160,128, 139,904, 135,936, 155,136 and 216,064 against stored totals of 80,064, 69,952, 67,968, 77,568 and 108,032 — twice each, at every leaf, exactly. The two objectives cannot disagree, and what separates the leaf that stores least from the leaf that runs fastest is a charge of about 139 operations for reaching a block at all.

 falls through a half, % of the answerfast, truncated96exact, shifted105fast, shifted66the answer's own dimensionblur 2.5 points wide2300.250.50.7511.251.500.20.40.60.81the preconditioner's own dimension ÷ the answer'sshare of the run on the arcfast, truncatedexact, shiftedfast, shifteddashed: as much dimension as the answer carrieshorizontal: half the run on the arc Methods that were designed apart

The shift had an edge, and the approximation moved it

A fast-transform preconditioner made invertible by a shift was recorded as never reaching the unpreconditioned floor, and predicted to sit off the answer's path at every shift. At a large shift it sits on the path and reaches the floor to a tenth of a per cent. It has an edge like the truncated one — but on the exact operator that edge is where the shift's own effective dimension reaches the answer's, 1.02 to 1.05 of it on six problems, and on the fast approximation it arrives at 0.49 to 0.77. The difference is sixteen samples at the ends of the signal, where the approximation is wrong and a shift divides the error by α.

 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.

 at σ = 10⁻⁸Cramer's rule1.2·10⁻⁴pivoted2.9·10⁻¹⁰elimination on T1.1·10⁻¹⁴cancellation × u1.7·10⁻¹⁰-10-9-8-7-6-5-4-3-210⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1σ, as a power of tenforward errorCramer's rulepivotedcancellation × uelimination on Tleft: σ small, the wrap nearly singularthe pivoted solve follows the cancellation Structure, and the solver that cannot see it

The correction lost to its own two-by-two solve

Solving a band matrix through a circulant and a small correction was measured losing the answer to 10⁻⁴ where elimination kept it to 10⁻¹⁴, and a wrap that landed one sample on a zero was measured costing four orders more than one that landed a pair. Both measurements solved the two-by-two correction system by Cramer's rule. Solved with a row interchange, the corrected solve on the same matrix loses 2.9·10⁻¹⁰ — the cancellation, and nothing multiplied onto it — and the single landing costs what the pair costs. The loss was in the determinant.

 at rank threelowest across tensors1highest across tensors1at rank fourlowest across tensors0.056highest across tensors0.25234500.20.40.60.81rank fittedagreement among the starts that reach itsix planted tensorsdashed: the true rankeach line one tensor, fitted at ranks two to fivefive starting points at every rank When the index is a tuple

The rank a sweep can vouch for

To decide a tensor's rank, fit it at one rank after another and stop where something changes. Three things can be read off each rank's fits — the error, how nearly parallel the terms are, and whether fits from different starting points agree — and over six planted rank-three tensors at four noise levels they decide it 24, 12 and 15 times out of 24; the ratio of consecutive errors, which needs nothing, decides it 24 times. The error is right every time and has to be told the noise level. The collinearity is a coin toss. Agreement among starts is never wrong and, under noise, cannot decide on nine of the twenty-four — and the rank past the answer, where every decision is made, costs ten times the answer.

 00.250.50.75100.51xuexact & tunedupwindcentralone of these is exacttuned, worst nodal error2.4·10⁻¹⁷upwind, worst nodal error0.14central, points outside [0, 1]16exact at every nodeand only at the nodes Iterating, instead of factorising

The diffusion that makes the answer exact

Upwinding adds h/2 of artificial diffusion. Central differencing adds none. Add ε·ξ·Pe with ξ = coth(Pe) − 1/Pe and the computed solution is the exact one at every grid point, to 2.4·10⁻¹⁷ — at every Péclet number, on the problem it was derived from and on no other.

 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 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 whose answer already comes as a band, the machine is inside the width of the line — and it is still there.

 a triangle and a square, joinedK₂,₃ with a pendant edge1234560123456indexeigenvaluethe same, and not the samevertices each6edges each7spanning trees12spectra differ by5.3·10⁻¹⁵highest degree, left4highest degree, right3one has a trianglethe other is bipartite The matrix that is a graph

The spectrum is not the graph

Two graphs on six vertices with the same Laplacian characteristic polynomial — as integer polynomials, not to fourteen digits. One contains a triangle; the other is bipartite. Every method in this field that reads only the spectrum is answering about the class.

All themes