fractionfreeLU.hpp File Reference

FF_LUComputation — Bareiss-style fraction-free LU over an integral domain. More...

#include "mat.hpp"

Go to the source code of this file.

Classes
class	FF_LUComputation
	LU decomposition over a domain using fraction-free Gaussian elimination. More...

Detailed Description

FF_LUComputation — Bareiss-style fraction-free LU over an integral domain.

Note

AI-generated documentation. Verify against the source before relying on it.

Declares FF_LUComputation, a private-constructor class that runs Bareiss's algorithm on a MutableMatrix whose base ring R is asserted to be an integral domain. The Bareiss update M[i, j] := (M[i, j] M[k, k] - M[i, k] M[k, j]) / lastpivot is guaranteed to produce an exact ring element (with no remainder) whenever R is a domain, so every intermediate value stays in R without a detour through the fraction field. For matrices with polynomial coefficients this can be orders of magnitude faster than ordinary LU plus fraction simplification.

The class tracks the column permutation it applied (col_perm), the previous pivot (lastpivot, used as the Bareiss denominator), the current pivot, and a per-step need_div flag indicating whether the division should run (the first step does not). After completion M carries the LU factors packed in the standard compact form (strictly-below for L, on-and-above for U) and the determinant is the final pivot up to the sign of the column permutation. M2 reaches this path via LUdecomposition over polynomial coefficient rings and via the DET_BAREISS strategy in det.hpp.

See also

det.hpp

mat.hpp

Definition in file fractionfreeLU.hpp.