Bareiss Fraction-Free Elimination

Concept Overview

Gaussian elimination typically introduces fractions when eliminating variables. This can lead to severe numerical instability in floating-point arithmetic or require expensive rational number arithmetic. The Bareiss algorithm is a fraction-free variant of Gaussian elimination that ensures all intermediate entries in the matrix remain exact integers (provided the initial matrix contains integers).

The algorithm works by using the pivots to perform exact divisions. Specifically, at elimination stage k, the elements are updated using the rule: M_i,j = (M_k,k · M_i,j - M_i,k · M_k,j) / M_k-1,k-1. The division by the previous pivot M_k-1,k-1 is guaranteed to be an exact division, leaving no remainder.

Worked Example

Consider evaluating the determinant of the "Dense" matrix preset using the Bareiss algorithm.

Matrix Evaluation Steps:

Initial Matrix:
```
[[2, 1, 3], [4, 3, 1], [6, 5, 2]]
```
Stage 1 (k=0):
The pivot is M_0,0 = 2. The previous pivot is assumed to be 1.
We update row 1:
M_1,1 = (2 · 3 - 4 · 1) / 1 = 2
M_1,2 = (2 · 1 - 4 · 3) / 1 = -10
We update row 2:
M_2,1 = (2 · 5 - 6 · 1) / 1 = 4
M_2,2 = (2 · 2 - 6 · 3) / 1 = -14
```
[[2, 1, 3], [0, 2, -10], [0, 4, -14]]
```
Stage 2 (k=1):
The pivot is M_1,1 = 2. The previous pivot is M_0,0 = 2.
We update row 2:
M_2,2 = (2 · -14 - 4 · -10) / 2 = (-28 + 40) / 2 = 12 / 2 = 6
```
[[2, 1, 3], [0, 2, -10], [0, 0, 6]]
```
Result:
The elimination is complete. The determinant is the final entry M_2,2 = 6. There were 0 row swaps, so the sign remains positive.

Experiment

To see how the algorithm behaves with different inputs, visit the Bareiss Fraction-Free Elimination module.

Select the Dense matrix from the Matrix dropdown. Observe that the Final stored entry is 6 and the Determinant is 6.
Change the Matrix to Row swap. The algorithm must swap the first and second rows because the first pivot is zero. This changes the sign of the determinant to negative, so the final entry -16 is multiplied by -1 to give a Determinant of 16.
Select the Singular matrix. A pivot column cannot be found, which immediately identifies the determinant as 0 and the matrix as singular.
Select Larger entries. Notice how the Maximum stored magnitude grows up to 26, larger than the initial entries or final determinant.

Limitations

The Bareiss algorithm is designed for integer matrices. While it avoids fractions, intermediate values can still grow substantially. The bit length of the entries grows linearly with the size of the matrix, meaning that for very large matrices, arbitrary-precision integers (BigInts) are required to avoid integer overflow.

If a pivot column is entirely zero at stage k, the matrix is singular, and the algorithm must stop or skip the column (if computing a row echelon form rather than just a determinant). Division by zero is undefined, so a missing pivot must not be used as the previous pivot for the next stage.

References

The algorithm and its proof of exact division can be found in the documentation for Flint (Fast Library for Number Theory), which implements fraction-free methods for dense matrices over rings.

Fraction-Free Linear Algebra Algorithms- Details the exact division mechanism and tracks the bounds of the intermediate sizes.

Bareiss Fraction-Free Elimination