Fraction-free elimination — where it appears
Named by 4 essays across one field — each of them below, with the objects they name alongside it.
An answer with no error in it
An integer matrix eliminated over the rationals rounds nothing, so the forward error is zero, the residual is the zero vector, and the identity this site is built on has no terms left. The cost does not vanish with the error. It moves into the length of the numbers, where three correct routes differ by four orders of magnitude.
Every intermediate is a minor
Fraction-free elimination divides by the previous pivot at every step and the division is always exact. Not usually, not for these entries — always, because the number being divided is a determinant with that pivot as a factor, which is a theorem and is checked here against the minors themselves.
The answer is longer than the question
An exact solution of an integer system is a vector of fractions, each of them a ratio of two determinants. So the output carries 2n long integers where the input carried n² short ones, and no algorithm can write it down more cheaply — the length of the answer is a floor under every exact solver rather than a property of one.
How many primes the answer needs
Work modulo a word-sized prime and no intermediate can exceed twenty-six bits, whatever the matrix does. The catch is that the answer must be reassembled from several such computations, and the number of them has to be fixed before the first one runs — by a theorem about how large a determinant can be, not by trying more until it settles.
Named alongside it
The objects these essays reach for when they reach for this one.
Bit lengthExact arithmeticHadamard boundDeterminantBackward errorChinese remainder theoremCondition numberCramers ruleExact ground truthIntermediate expression swellMinorModular arithmetic