Numerical Linear Algebra
where the algebra stops being the arithmetic
Theme

The thread: Identical algebra, different arithmetic — page 3

Essays 49 to 72 of the 104 on this theme, in the same order.
10²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)‖x̂ − x‖ / ‖x‖modified, through Qᵀbclassical, either route‖QᵀQ − I‖, modifiedHouseholdermodified, on [A b]κ²uκuforward error at κ = 10⁸Householder4·10⁻⁹modified, through Qᵀb0.13modified, on [A b]2.7·10⁻¹⁰classical840×8, three seeds, against an exact rational solveQ is not orthogonal; x is right Orthogonality, measured

The right-hand side as one more column

Modified Gram–Schmidt's Q is 4.3·10⁻⁹ from orthogonal at κ = 10⁸, and a least-squares solve that multiplies b by it is wrong by 0.13. Hand the same routine b as an extra column instead and the answer is right to 2.7·10⁻¹⁰ — closer than Householder's 4.0·10⁻⁹. Classical Gram–Schmidt gains nothing from the same trick, to the last bit.

 110¹10²10⁵block size bwords movedbest block: b = 10the recursion: no block size126,742 wordsbest block, scanned1.1·10⁵the recursion1.3·10⁵recursion ÷ best1.2M = 144 words; the recursion never reads it1.16× the best of 24 blocks Where the flop count stopped predicting the time

The recursion that was never told the memory

A blocked elimination has to be tuned to its fast memory, and tuned to one memory it costs up to 2.9 times the best at another. A recursive elimination splits the columns in half down to one and reads no memory size at all. On eight fast memories from 36 to 576 words it moves between 0.94 and 1.28 times the words of the best tuned block, with the same 585,200 operations and the same pivots — and on a machine with two caches it beats the block tuned to either cache on six machines of seven.

 08162432404810⁻¹10²10⁵10⁸10¹¹10¹⁴10¹⁷10²⁰degreeκ of the design matrix1/u: past this a double holds nothingmonomialsChebyshevArnoldi on the pointsκ at degree 48monomials1.5·10¹⁷Chebyshev1.6·10⁷Arnoldi on the points1200 two intervals with a gap between themthree bases for one space of polynomials Least squares, and the road not to take

A basis built from the points

A polynomial fit computed in monomials and in an orthogonal basis gives the same curve on exact data, and the valley essay drew the two lying on top of each other. Add 0.1% noise and they separate — by 1.7·10⁻⁵ at degree 40 and 0.004 at degree 48 — because the fitted curve moves with the basis by its condition number times the rounding times the residual. Chebyshev polynomials keep that small only on points spread like their weight; on a sample with a hole in it they reach κ = 1.55·10⁷. A basis orthogonalised against the sample points themselves stays at 1 on every set.

 263850627410⁻⁵10⁻³10⁻¹rows in the linearisation‖g − r‖ on the target setpolynomialrationalequal cost, two basesreach0.06largest size drawn78rational there2·10⁻⁵polynomial there0.0015the ratio73no winner on an easy targetand two orders on a hard one The eigenvalue problem that is not linear

Two approximants and one matrix size

A polynomial approximant linearises to nd rows and a rational one to n(m+1), so the fair contest fixes the matrix and varies the basis. On an easy target set the two are indistinguishable and the ordering flips with the noise; on one that reaches a branch point the rational pulls away by two orders.

 10⁻⁴10⁻³10⁻²10⁻¹100.250.50.751anisotropy εsmoothing factor μpoint + fully-line + fullpoint + semi-y⅓, the one-dimensional answertwo routes, three curvesgap between the repairs2.2·10⁻¹⁶scan against closed form2.2·10⁻¹⁶the dashed curve lies on the solid one beneath itone repair, written two ways Iterating, instead of factorising

Smoothing a whole line at once

Solve every grid line in the strong direction exactly rather than sweeping over it, and the smoothing factor goes from 0.9993 back to 0.3340 — which is the one-dimensional answer, on a problem that is not one-dimensional. The repair replaces one ε in the closed form by a one.

 1357910⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1eigenvalue λamplificationkeptdiscardeda filter on the starting vectormeasured against the polynomial3.9·10⁻¹¹worst kept direction1best discarded direction0.8the roots are the discarded Ritz valuesand the vertical lines are where they sit Eigenvalues, singular values, rank

Restarting is a filter

A restart throws away the Ritz values it does not want and begins again from a new starting vector. Written in the eigenbasis, that vector's components have been multiplied by a polynomial with its roots at the discarded values — measured component by component, and agreeing with the polynomial to rounding.

 6101418222610³10⁴10⁵grid side karithmeticND, totalMD, totalMD, critical pathND, critical pathdashed: the time on unbounded processorsthe same time, bought with more work Sparsity, and what elimination costs

An ordering that buys processors, not time

Nested dissection loses to minimum degree on fill and on total work at every grid either measurement could draw. Read along the elimination tree a parallel factorisation works on, it does not win back the time either: its critical path is within 28 per cent of minimum degree's at every size from 8 to 24 points a side, in both directions, and the tree heights and widest columns are nearly the same. What it wins is the ratio. Its total work over its critical path — the most a factorisation on unbounded processors can speed up by — grows from 2.7 to 4.5 while minimum degree's stays between 2.1 and 2.6.

 110¹123base case, columnswords ÷ the best block's√M − 2 = 10M = 144M = 144base of one1.2panels ≤ 10, worst1.2panels of 123the base case is a block size, rounded to a halvingand it has the block's cliff at √M − 2 Where the flop count stopped predicting the time

The block size a recursion still has

A recursive elimination is sold as having no block size, and every real one switches to plain loops below some width. Swept over that width, the traffic is a staircase with its steps at the halvings of n, and its cliff sits where the blocked elimination's does — the first panel wider than √M − 2 moves 1.53 to 4.47 times the words, on six memories of six. On three caches the innermost decides, and a third cache costs every tuned block up to 14 per cent and the recursion nothing.

 110¹10²10³10⁴10⁵10⁶10¹10²10³10⁴10⁵spread of resistances, largest ÷ smallest possiblecondition number, unit diagonalleast-resistance treebreadth-first treegreatest-resistance treenode equationsspread resistances make the loops easyand the nodes hard Orthogonality, measured

Spread resistances make the loops easy

Scaled to a unit diagonal, the loop equations on the least-resistance tree get easier as a network's resistances spread — from 120 to 5.44 over six decades — and stop depending on the grid's size, while the node equations of the same flow get harder, from 538 to 4.6·10⁴. The spread that ruins the range-space formulation rescues the null-space one, though the loops' density means the work saved is a factor of two, not the factor of nine the iteration counts suggest.

 1357911131510⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1k, where h = 1 − 10⁻ᵏrelative error of 1 − h1 − ‖R⁻ᵀa‖²1 − ‖row of Q₁‖²‖row of Q₂‖²40 × 6k = 12, Cholesky route1.1·10⁻⁴k = 12, thin QR route4.4·10⁻⁴complement, worst k3·10⁻¹⁵one minus a sum of squaresor the sum of the other squares Least squares, and the road not to take

One minus a leverage is a subtraction

Every deletion diagnostic divides by 1 − h, and computing it as one minus a computed leverage loses digits in proportion to 1/(1 − h), however accurate the leverage. The complementary block of a QR factor gives the same number as a sum of squares and loses κ(A)·u instead: every digit on a well-conditioned design, and half the digits the subtraction loses on a design whose far point is what made 1 − h small.

 point · strong in y0.951point · strong in x0.956y-line · strong in y0.037y-line · strong in x0.967semi-y · strong in y0.107semi-y · strong in x0.9661.00 — no convergenceone problem, seen from two sidesy-line, aimed0.037y-line, turned sideways0.97the ratio2631×31 grid, twelve V-cyclesthe direction is in the code, not in the problem Iterating, instead of factorising

Coarsening in one direction only

Leave the smoother alone and halve only the strong direction, and the smoothing factor is 0.3340 — identical to line relaxation's, at every anisotropy and every weight, to twelve digits. The convergence factors are then a factor of three apart, and at 45° both repairs fail outright.

 groundarcs of the treearcs off the treethe loop worst servedleast-resistanceκ(Z)11κ(ZᵀHZ)143κ, unit diagonal9.3nonzeros in Z426longest loop, arcs26worst path ÷ own arc0.97every tree gives a basis of whole numbersthe resistances decide which one to want Orthogonality, measured

The tree the resistances choose

On a network every basic set is a spanning tree and every null-space basis is a set of loops with entries 0 and ±1, so no tree can make Z badly conditioned. The tree with the best-conditioned Z still gives loop equations 4.8 times worse than the tree of least resistance: the basis has to be chosen against the Hessian, and pivoting finds it only when it pivots on the resistances too.

 10¹110¹skew of the starting basisdistance ÷ the distance to the nearest pointthe nearest lattice pointdashes: the skewed basis's orthogonality defectrounding in the skewed basisrounding in the reduced basisthe same three lines of arithmeticskew40defect there40worst, skewed40mean, skewed26mean, reduced1exact share, skewed0one lattice, one targetand two descriptions Exact arithmetic, and what it costs instead

Rounding a coordinate in the wrong basis

The nearest lattice point is found by writing the target in the basis and rounding each coordinate, which is three lines of arithmetic and is wrong. On a basis skewed by forty it lands a mean of 26 times too far and a worst of 40.02 — the basis's own orthogonality defect, to three figures — and the identical three lines on the reduced basis are exact at every target.

 the grid the operator came froman edge is a coupling the matrix calls strongkeptinterpolatedwhat the entries decidedcoupling ratio, x against y0.001strong couplings across x0strong couplings along y110rows kept or dropped whole1111×11 grid, θ = 0.25the coarse grid, from the matrix alone Iterating, instead of factorising

The coarse grid the matrix chooses

Given a tridiagonal matrix and no information about a grid, the coarsening keeps every other point and derives the weights ½, 1, ½ — the operators the geometric method was handed. Given the anisotropic operator, it discovers semi-coarsening, in the right direction, without a coordinate.

 123456110²10⁴10⁶moments Kκ of the block Hankelintegrated in zin (z − c)/ρone division per pointradius6unscaled, K = 62.3·10⁶scaled, K = 61750the factor between1291the ceiling rises by Kand so did the conditioning The eigenvalue problem that is not linear

The conditioning that rises with the ceiling

Higher moments multiply a contour method's ceiling by K and grade its block Hankel over ρ to the 2K, so the two knobs are the same knob. One division per quadrature point separates them, and the measurement of what it is worth grows from twenty to twenty thousand.

 38434853586368110¹10²10³10⁴e, where the skew is 2ᵉ + 12345orthogonality defect of the basis returneda double holds k exactlyan orthogonal basisthe invariant sees none of itfloat, at 2^521float, at 2^531.4float, at 2^701.2·10⁴residue at 2^701.2·10⁴exact, everywhere1determinant, always1every step was unimodularand the answer is 12,345 times worse Exact arithmetic, and what it costs instead

The knob and the rounding

The Lovász parameter is the number a lattice reduction is specified by, and moving it from 0.50 to 0.99 strengthens the proved bound from 16.00 to 1.83, costs 91 per cent more steps, and returns a basis with the same orthogonality defect. The one rounding nobody writes down decides everything: above 2⁵³ the reduction returns a basis 12,345 times worse than it should, with the determinant invariant equal to one throughout.

 the damagewell scaled, nothing done0.9110^±3, nothing done0.095never certified, of 62at 10^±3rows to unit norm0.64rows by right-hand side0.6start at the rows0.43012300.250.50.751rows rescaled by 10ᵏshare that certifiesnothing donestart at the rowsrows to unit normrows by their right-hand sidethe grey line is a well-scaled programme with nothing doneboth equilibrations are flat, and below it The matrix a constraint makes

Two repairs for one symptom

Rescale a quadratic programme's constraint rows over six decades and the crossover that certified its answer at iterate 1.5 first certifies at 69.8, with two of six programmes never certifying at all. Normalising the rows removes the spread completely — the same numbers at 10¹, 10² and 10³ either way. Starting the method at the magnitudes the rows imply repairs the iteration count completely and the identification only halfway. They are two repairs and they fix different halves.

 8×8, κ = 10⁸direction at ε = 10⁻², ‖QᵀQ − I‖1.5·10⁻¹⁵scalar at ε = 10⁻², ‖QᵀQ − I‖0.065direction at ε = 10⁻², residual0.00510⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²relative perturbation εdeparture‖QᵀQ − I‖, scalar‖A − QR‖/‖A‖, scalar‖A − QR‖/‖A‖, direction‖QᵀQ − I‖, directionflat line: a different reflection is still a reflectionsloped line: a non-reflection is not Orthogonality, measured

One number that has to be right

Householder's orthogonality was called structural: a reflection is built from a unit vector, so rounding the vector names a different reflection rather than a broken one. Tested by breaking it, the claim is narrower and sharper. Perturb every component of the reflector by a relative 10⁻², and ‖QᵀQ − I‖ stays at 1.5·10⁻¹⁵ while the factorisation moves to 5·10⁻³. Perturb the one stored scalar by the same amount and ‖QᵀQ − I‖ is 6.5·10⁻². The structure is one degree of freedom, and the departure is four times its relative error.

 5860626466687010⁻¹⁷10⁻¹⁶terms in the dot productmean relative errorthe kernel changes herea constant in a libraryone accumulator3.2·10⁻¹⁷four accumulators2.1·10⁻¹⁷step at the cutoff1.6cutoff64the problem did not changethe loop did The answer that depends on the machine

The length that changes the kernel

A dot product's accuracy steps by a factor of 1.57 between 63 and 64 terms, on vectors drawn identically at both lengths. Nothing about the problem changes there. A library switches from one accumulator to four, at a constant in somebody else's source file.

 05101520253035059118177236295vertices eliminatededges of fill so farminDegree: 71natural: 125reverse: 125random: 160maxDegree: 293fill, by orderingminDegree71natural125reverse125random160maxDegree293edges to start60eliminating a vertex makes a cliqueand the order decides how big The matrix that is a graph

Eliminating a vertex is a graph operation

Gaussian elimination on a Laplacian deletes a vertex and joins its neighbours into a clique with conductances wᵢwⱼ over Σw. The matrix that remains is still a graph — symmetric, zero row sums, nonpositive off the diagonal — and the ordering decides whether the fill is thirty-one edges or four hundred and sixty-five.

 10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹10³10⁵σ — how far the periodic wrap is from singularrelative forward error10⁻¹10⁻²10⁻³10⁻⁴10⁻⁵10⁻⁶10⁻⁷10⁻⁸10⁻⁹10⁻¹⁰10⁻¹¹10⁻¹²periodic correctionκ(C)·uelimination on Tn = 64, median of five answersperiodic correction, σ = 10⁻⁸1.2·10⁻⁴elimination on T, σ = 10⁻⁸1.1·10⁻¹⁴κ(C) at σ = 10⁻⁸4·10⁸κ(T) at σ = 10⁻⁸1712the same matrix T in every columnonly the wrap it is solved through changes Structure, and the solver that cannot see it

The circulant the problem did not contain

A matrix that differs from a circulant in two corner entries can be solved through the circulant, by a transform and a two-by-two correction, and the cost claim is exact. The accuracy claim is not. On tridiag(−1, 2 + σ, −1), whose condition number stops at 1,712, the correction is wrong by 1.2·10⁻⁴ at σ = 10⁻⁸ while elimination is right to 1.1·10⁻¹⁴ — because the periodic neighbour is singular at σ = 0 and the two-by-two system inherits that. Solved by Cramer's rule, as here, the two amplifications multiply; a later measurement found that a pivoted solve of the same two-by-two system removes the second.

 81930415263110²10⁴10⁶10⁸10¹⁰10¹²size of the matrix|rₙₙ| ÷ σₘᵢₙthe two agreec = 0.2c = 0.35c = 0.5no ceilingratio at n = 1021ratio at n = 646.8·10¹⁰interchanges, anywhere0the greedy rule never had a choiceand the gap grows with every row Eigenvalues, singular values, rank

The cheap rank and what it cannot see

Almost nobody computes singular values to decide a rank. The standard substitute is QR with column pivoting, read off the diagonal of R — and there is a triangular matrix on which the greedy rule makes no interchange at all, has no better column available at any step, and reports a matrix eight orders of magnitude further from singular than it is.

 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.

All themes