AngouriMath
FractionFreeDeterminant
Description
Summary
Bareiss' fraction-free elimination: the determinant of a square matrix over an
integral domain, inO(n^3) ring operations and without ever leaving the ring.
integral domain, in
Remarks
produces quotients — and an expression built from them is undefined wherever a pivot
vanishes, at points where the determinant itself is perfectly well defined. That is
what #992 was
about, and why Determinant used Laplace expansion rather
than elimination.
previous pivot, and that division is exact — the quotient is a
determinant of a minor and therefore back in the ring. So the intermediate entries do
not swell the way Gaussian elimination's do, and nothing is ever left as a quotient to
exclude a point.
null rather than a remainder, so a division that does not come out — because the term
ceiling was reached, or because an assumption above is wrong — stops the elimination
instead of producing an answer that is quietly not the determinant. Every caller reads
null as "use another method", never as "there is no determinant".
matrix. Shared rather than written twice, deliberately: a sign convention or an
off-by-one in an elimination is a wrong answer that looks entirely plausible, and one
implementation exercised by two callers is tested by both.
#999
Members
Angouri © 2019-2023 · Project's repo · Site's repo · Octicons · Transparency · 4378 pages online