Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Tensor train — where it appears

A tensor written as a chain of three-index cores, one per index, so that each entry is a product of small matrices. Its ranks are those of the reshapes that cut the index list, and its storage is linear in the number of indices rather than exponential.

Named by 7 essays across 3 fields — each of them below, with the objects they name alongside it.

123456710¹10²10³10⁴10⁵number of indicesnumbersentries: 6^dstored: 4n(d − 1)exponential against linearentries at d = 64.7·10⁴numbers stored120ratio389slope against d24‖T − Tₜₜ‖ ⁄ ‖T‖1.4·10⁻¹⁵one line is n^dthe other is a constant per index

The format that does not notice the dimension

A Tucker core is r^d numbers, so the format that repaired the definition still cannot go past five indices. Cutting between the indices rather than across them gives d − 1 ranks instead of d, storage linear in the number of indices, and a family whose ranks are two everywhere by an addition formula.

tensor · Tensor train chain · cheapest1.51·10⁴chain · greedy5.06·10⁴chain · dearest5.13·10⁸train-inner · cheapest3344train-inner · greedy1.51·10⁴train-inner · dearest6.58·10⁹als-step · cheapest1.05·10⁵als-step · greedy1.13·10⁵als-step · dearest1.13·10⁵multiply-adds, on a logarithmic scaleone value, many priceschain, best ⁄ worst3.4·10⁴train, best ⁄ worst2·10⁶als step, best ⁄ worst1.1worst greedy excess4.5no answer changesand the price does

The order the products are taken in

The sparsity field's first essay says the elimination order decides the memory. This is the same sentence about arithmetic: a contraction of several tensors over shared indices has one value and many evaluation orders, and on the inner product of two trains they differ by a factor of two million.

cost · Contraction 15913172110¹10⁶10¹¹10¹⁶10²¹10²⁶number of indicesnumbers storedthe tensor: n^dthe core: r^d + dnrthe train: (d − 2)nr² + 2nrthe curse, movedentries at d = 2010²⁶core1.1·10¹²train5920core ⁄ train1.9·10⁸entries ⁄ core9.5·10¹³the definition is repairedthe size is not

A compression of 10¹⁴ that still does not fit

A Tucker core of a twenty-index array at rank four is 1.1·10¹² numbers against the tensor's 1.05·10²⁶ — a compression by a factor of 9.5·10¹³ that is still nearly nine terabytes. The ratio is not the verdict. The verdict is a ceiling, and the ceiling is a number of indices.

tensor · Multilinear rank -13-11-9-7-5-3-102468log₁₀ of the accuracy asked forlargest train rank0.30 of rank per decadea cost that is typed inentries216stored at 10⁻²90stored at 10⁻¹²288rank per decade0.3worst error ⁄ tolerance0.83the storage is chosena constant of rank a decade

The digit that costs more than the tensor

Ask a three-index reciprocal tensor on six points a side for seven digits and its train is 288 numbers against 216 entries. The break-even rank is n − 1 at all four grids measured, and a train that reaches it fits with exactly n numbers to spare.

tensor · Tensor train 10¹10²110¹rank of the trains at the moment of evaluationcost ÷ the cost of this rank's own best ordereach rank's own best orderthe order compiled at rank 4, carriedthe smallest-result rule, recomputedthe cheapest-product rule, recomputedone plan, eight rankscompiled at rank4worst carried8carried at rank 2568fresh rule at 2562.9carried at rank 21fresh rule at 21.1the search was exhaustiveand the dimensions moved

The plan that was right at rank four

An evaluation order is chosen once and paid for thousands of times, and the dimensions it was chosen at are not the dimensions it runs at. Compiled at rank four and run at rank 256 it costs 8.01 times the order that rank deserves; compiled at 256 and run at 2 it costs 301 times. A one-line rule recomputed on arrival costs 2.92 and 1.11.

cost · Contraction 081624324010⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²conjugate gradient steprelative residualabove, on their own scale: rank asked 5, rank kept 3solid: the budgeted residual · light: no budgetbudget 3rank asked for5rank kept3residual, budgeted3.8·10⁻⁴residual, unbudgeted1.6·10⁻¹⁴numbers stored150the step asks for moreat every step

An iterate that must be made smaller

Applying a Kronecker-sum operator to a low-rank iterate multiplies its ranks by d and adding two of them adds their ranks, so a solver in a compressed format cannot keep what it produces. Every step is followed by a truncation — and whether that truncation is a floor on the residual depends on the right-hand side rather than on the truncation.

iterative · Low-rank iteration 012345678910⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹rank budgetresidual the run stalls atb with no structure at allb constant: the answer is a traintwo ladders, one truncationstructured, rank 10.12structured, rank 45.5·10⁻⁶structured, rank 85.9·10⁻¹⁴unstructured, rank 10.97unstructured, rank 80.47the floor is not the truncation'sit is the answer's

A run that is over at step five

A conjugate gradient whose every iterate is cut to a rank budget reaches the floor that budget allows at step 5, 36, 42 or 59, and then does nothing for the rest of the run. Four times the iterations move the floor by a factor of 1.8, and past the answer's own rank they move it the wrong way.

iterative · Low-rank iteration

Named alongside it

The objects these essays reach for when they reach for this one.

Low-rank approximationCurse of dimensionalityTruncationUnfoldingConjugate gradientsContraction orderElimination orderExact ground truthFlop countHigher-order SVDKronecker sumKrylov subspace

All concepts