Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Hierarchical solve — the series

3 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 567891010⁴10⁵10⁶10⁷10⁸10⁹log₂ nmultiplicationsdense factorisation, n³⁄3the recursion, countedwhere the format starts payingratio at n = 641.5ratio at n = 5120.16exponent, first doubling2.1exponent, last doubling1.7backward error1.4·10⁻¹⁰cheaper is a sizenot a property

    Where the format starts paying

    A hierarchical solve costs 1.48 times a dense factorisation at 64 unknowns and 0.16 times it at 512. The crossover is between 64 and 128, it walks right when the accuracy is tightened, and the exponent between consecutive sizes is 2.13, 1.93, 1.74 — falling towards one and never arriving.

    part 1 · cost
  2. -9-7-5-3-1110⁵10⁶10⁷log₁₀ ε of the preconditionermultiplications for the whole solveno preconditioner: 41 stepsiteration count, rescaledmultiplications spenttwo curves, opposite waysκ21steps, no preconditioner41cheapest ε0.5its rank1tightest ⁄ cheapest2.4the count is what is printedand the cost is what is spent

    The accuracy worth paying for

    Used as a preconditioner, a hierarchical representation gets better at every accuracy — the iteration count falls monotonically all the way to the tightest tolerance. The total work does not. Its minimum sits at a rank-one preconditioner on an easy problem and six decades further along on a hard one.

    part 2 · hierarchy
  3. 10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹relative compression error, chosen‖x − x*‖ ⁄ ‖x*‖κ × the chosen backward errorthe error in the answerboth factors known firstκ21chosen at 10⁻⁸1.4·10⁻⁹predicted forward2.9·10⁻⁸measured forward1.6·10⁻⁹bound ⁄ measured26the amplifier, used forwardsfor once

    The knob that moved two things

    Decide how many digits the answer needs, divide by the condition number, and compress to that. It is the one rule licensed in advance here, and its two factors are not the independent inputs it reads as: the partition's leaf moves neither of them and moves the answer by nearly a factor of three, and the only knob here that raises κ halves the ranks while it does so.

    part 3 · hierarchy

All series