Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Cramers rule — where it appears

The identity that the i-th entry of the solution of Ax = b is the determinant of A with its i-th column replaced by b, divided by the determinant of A. Read as an algorithm it is a bad one; read as a statement about the answer it says every entry has a denominator dividing det A, and so bounds how long an exact solution is.

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

3456789101110²10³nbitsthe answerthe question · det Abits in, bits outn11question484answer729det A33widest part37the answer is the floorand no route writes it down more cheaply

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.

exact · Exact cost 2^18modulus, as a power of twoa lattice with one short vectornumerator355denominator1132·max(n, d)², bits18first recovered at18moduli tried42below the bound there are two answersand the algorithm cannot prefer one

A fraction recovered from one remainder

A solution over the rationals can be computed modulo a prime power and then recovered — the residue determines the fraction uniquely, but only once the modulus is twice the square of the fraction's longer part. Below that there is no partial credit: the algorithm returns a different fraction with the same residue, and it is a perfectly good one.

exact · Modular lift at σ = 10⁻⁸Cramer's rule1.2·10⁻⁴pivoted2.9·10⁻¹⁰elimination on T1.1·10⁻¹⁴cancellation × u1.7·10⁻¹⁰-10-9-8-7-6-5-4-3-210⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1σ, as a power of tenforward errorCramer's rulepivotedcancellation × uelimination on Tleft: σ small, the wrap nearly singularthe pivoted solve follows the cancellation

The correction lost to its own two-by-two solve

Solving a band matrix through a circulant and a small correction was measured losing the answer to 10⁻⁴ where elimination kept it to 10⁻¹⁴, and a wrap that landed one sample on a zero was measured costing four orders more than one that landed a pair. Both measurements solved the two-by-two correction system by Cramer's rule. Solved with a row interchange, the corrected solve on the same matrix loses 2.9·10⁻¹⁰ — the cancellation, and nothing multiplied onto it — and the single landing costs what the pair costs. The loss was in the determinant.

structure · Circulant

Named alongside it

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

Bit lengthDeterminantExact arithmeticBackward errorCapacitance matrixChinese remainder theoremCirculant matrixCondition numberFraction-free eliminationHadamard boundIterative refinementLattice

All concepts