Cholesky factorisation — where it appears
Named by 18 essays across 3 fields — each of them below, with the objects they name alongside it.
The problem that arrives again
A hundred and thirty essays have solved a system once and measured how wrong the answer was. Almost no computation is shaped like that. A solve is one step of an outer loop, its answer is an input rather than a deliverable, and four quantities treated here as accuracy requirements turn out to be assets with a shelf life.
A factorisation kept past its date
One Cholesky factor can serve five members of a drifting sequence and save 44 per cent of the work. Kept for twenty it does not lose accuracy — it stops converging altogether. The optimum and the cliff are four members apart, both move with the drift, and a rule written in a ratio the iteration has already computed finds them without being told what the drift is.
Where the drift lands
The standing rule for when a preconditioner has gone stale is to rebuild it once the matrix has changed by more than some fraction of itself. Two drifts of exactly the same relative size cost 19 iterations and 5 on the same matrix, and the quantity that separates them is not in the rule at all — the perturbation is divided by the eigenvalue it lands on.
What a rebuild is worth
One sequence, one drift, one preconditioner — and six different right answers, because the cheapest rebuild period depends on what a rebuild cost to build and on nothing else. The optimum walks from every member to every twelfth as the setup gets dearer, and the free rule that reads the iteration count beats it in the middle of that range and loses at both ends.
Stable once, and three thousand times
A sliding window adds a row and removes one at every step and never looks at the data again. No single step of it amplifies by more than 2.72, no downdate fails, and after three thousand steps the triangular factor in memory is 3.9·10⁻¹⁴ from the matrix it is supposed to be a factor of — six hundred times growth from a per-step bound that says nothing about chains.
A matrix that is definite on one machine
Two hundred Gram matrices, two conforming builds, and twenty-six of them get different answers to "is this positive definite". The exact verdict, from determinants in BigInt rationals, says the fused build is right nine times and the other one seventeen.
The penalty for keeping it is a ratio
A kept incomplete Cholesky costs 40 iterations against a rebuilt one's 10 on 64 unknowns, and 55 against 17 on 256. Across six grids the difference between the two rises by 27 per cent and the ratio between them falls by 19. Neither quantity is free of the problem's size, and the one a policy is paid in is the one that transfers worse.
The rounding that was not the problem
A rank-k block plus a rank-k block is a rank-2k block, exactly, so every arithmetic in this format truncates after every addition. A Cholesky performed inside it does ninety-eight of those and its residual is 1.14·10⁻⁹ against a representation error of 1.40·10⁻⁹ — the roundings cost nothing measurable.
A knob calibrated in residuals
A formatted Cholesky has two numbers in it and only one of them is an accuracy. Across twelve trees — three sizes by four leaf sizes — the leaf moves the truncation count from 0 to 258 and moves the ranks of the blocks not at all, while the residual follows the tolerance at slopes between 1.022 and 1.046 and sits at about a tenth of it throughout.
The repair the drift did not need
A sliding window's carried Cholesky factor drifts 3.9·10⁻¹⁴ from its data, and multiplying by κ(AᵀA) predicts eight lost digits in the coefficients, a stream conditioned at 10¹² losing the answer, and a periodic refresh of the factor as the default repair. Measured against coefficients computed exactly in rationals, all three come out differently. On a stream made ill-conditioned by scaling, the conditioning never reaches the coefficients. On a collinear stream, a freshly recomputed factor is as wrong as the drifted one. And one correction from the window's own rows reaches Householder's accuracy for a fraction of a refresh's cost.
The count that is not the budget
A Cholesky performed inside a low-rank format truncates 0, 2, 10, 34 and 98 times as the leaf falls from 128 to 8, and those five integers are the same at every accuracy from 10⁻¹² to 10⁻². Across all ten decades the factorisation's residual stays below the representation's own error at a ratio between 0.81 and 1.00 — with two entries that read 1.83 and 1.78, and neither of them is accumulation.
A warm start is degree zero
The previous answer used as the next member's starting point costs 160 inner steps over twenty members. The line through the last two answers costs 12 — a factor of thirteen, for three vector operations and no extra storage. The parabola through the last three costs 26, which is worse than the line and better than the point.
The order a batch arrives in
Sixteen problems over a parameter, solved in the order the loop produced them, cost a median of 1.54 times what the same sixteen cost sorted, and 2.80 times at the worst shuffling. A nearest-neighbour path computed from the parameter values alone recovers the sorted cost exactly, at every drift and every shuffle.
A straight path has nothing for a parabola to fit
The line through the last two answers beat the parabola through the last three on a drifting sequence, and the reason offered was that the parabola amplifies the stored answers' error. Tightening the solve tolerance from 10⁻⁶ to 10⁻¹⁴ should have reversed that, and it does not: the line needs 7 to 18 inner steps over twenty members at every tolerance and the parabola 14 to 23. The sequence's roots move along a straight line, so the line is exact and there is nothing else to fit. Bend the path by a part in ten thousand and the parabola wins below 10⁻⁹, by 105 steps to 75 at 10⁻¹⁴.
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.
The answer the last window left
A sliding window that corrects its least-squares answer at every step could start each correction from the previous step's corrected answer instead of from a fresh solve: the two windows share all but one row. On a stream with any noise in it, that start is three orders worse. The window's exact answer moves by 0.79 of itself in one step at κ(A) = 3·10⁶, a fresh seminormal solve is wrong by only 1.8·10⁻⁴, and one correction contracts either start by the same factor — so the fresh start ends at 2.2·10⁻⁸ and the carried one at 3.7·10⁻⁵. Only on data that agree exactly does carrying win.
A fit wins where the steps were few
The line through the last two answers of a sequence of solves amplifies their stored error by √5, and the parabola through the last three by √19. A least-squares line through five amplifies it by 1.05 and a parabola through six by 1.79, and on a straight path both beat their interpolants at every tolerance: 12 inner steps against 17 at 10⁻¹⁴. On a bent path they lose, by exactly the ratio of their truncation constants, and they lose in the runs that cost a hundred steps rather than ten. Over thirty runs no fitted start beats the parabola through three, and the best of eight starts chosen per run saves 58 steps out of 1,212.
The step the two rows owe
A sliding least-squares window can start each step's correction from a fresh solve or from the answer it already has. The answer it has is three orders worse on noisy data, because the exact answer moves by most of itself in a step. The proposal was a start that moves too: the previous answer plus the change the entering and leaving rows imply, two triangular solves from the factor the window keeps. Its start lands exactly where one correction of the carried answer lands — the update is that correction, computed from two rows instead of twenty-four — and one correction after it ends 2.9 to 440 times below the fresh start at κ(A) = 3·10⁶, and level with the carried answer when the data agree exactly.
Named alongside it
The objects these essays reach for when they reach for this one.
Warm startFlop countExact ground truthNewton iterationBackward errorCondition numberPreconditioningStopping criterionCondition squaringExtrapolationLow-rank updateConjugate gradients