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 2 essays across one field — 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

Named alongside it

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

Bit lengthExact arithmeticChinese remainder theoremDeterminantFraction-free eliminationHadamard boundLatticeModular arithmeticOutput sizeRational reconstruction

All concepts