Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Kronecker — the series

3 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 03672108144180216024681012eigenvalues in orderλthe closed formmarks: the assembled matrix, decomposeda spectrum nobody computedrows of the matrix216numbers that describe it108λ smallest0.59λ largest11worst |computed − exact|7.1·10⁻¹³the matrix is never neededand neither is its decomposition

    An index that is a pair

    A discretisation on a two-dimensional grid of n points a side has n² unknowns and a matrix with n⁴ entries — 10⁸ at n = 100. What that matrix is instead is two Kronecker products of an n × n matrix, which is 2n² numbers, and nothing has been approximated: assembling it was the mistake.

    part 1 · tensor
  2. 024681012141610⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹index of the singular value at the cutσ ⁄ σ₁eight digits10^-4: 5 Kronecker terms10^-8: 7 Kronecker terms10^-12: 8 Kronecker termsnot closed, and nearly closedrank at the cut8a Kronecker product's1terms at 10⁻⁴5terms at 10⁻⁸7terms a decade0.5the inverse leaves the formatby half a term a decade

    A solve that is d decompositions

    A Kronecker sum is closed under nothing useful — its inverse is not a Kronecker sum and no factorisation of it is one. What it has instead is eigenvectors that are Kronecker products, so a solve with 1,728 unknowns takes one decomposition of a 12 × 12 matrix and nothing else.

    part 2 · tensor
  3. 110¹10²10⁴10⁶10⁸10¹⁰10¹²n, points along one axismultiplicationsa dense factorisationthrough the eigenbasis6 decompositions of an n × nunknowns1.6·10⁴multiplications9.4·10⁵dense factorisation2.5·10¹²fitted exponent7‖Ax − b‖ ⁄ ‖b‖1.8·10⁻¹⁵nothing of size n^dis ever factorised

    Five indices are cheaper than two

    The same 4,096 unknowns cost 1.049·10⁶ multiplications indexed as a 64 × 64 grid and 1.966·10⁵ indexed as six axes of four. The dense factorisation that ignores the indexing costs 4.581·10¹⁰ at every one of them, and the residual improves in the same direction as the cost.

    part 3 · tensor

All series