Skip to content

A fraction-free elimination (Bareiss) would raise the determinant's practical size ceiling from 10x10 #999

Description

@Rafael-SOWNet

Split out of #992 / #998, which fixes the correctness half and names this as the part it deliberately does not do.

Where things stand after #998

Matrix.Determinant computed by Gaussian elimination left the pivots as literal divisions, so the expression was NaN wherever a pivot vanished. #998 replaces it with Laplace expansion, which never divides and so needs no condition. That is a strict improvement on both axes — the returned expression is smaller at every size, and numeric matrices got much faster, because the elimination built a symbolic quotient that InnerSimplified then had to grind down.

Measured, property only, both arms built from source on one machine:

entries Gaussian complexity Laplace complexity Gaussian, numeric Laplace, numeric
2×2 13 9
3×3 79 37
4×4 443 163
5×5 2461 833
6×6 13673 5021 164 ms 126 ms
7×7 35173
8×8 over 120 s 358 ms
10×10 over 120 s 4478 ms
11×11 over 240 s over 240 s

What is left

Laplace is O(n!). For a fully symbolic matrix that is not an overhead — the determinant genuinely has n! terms, so it is the size of the answer, and no algorithm returns it smaller in expanded form. For a numeric or mostly-numeric matrix it is pure waste: the answer is one number, and O(n^3) work suffices.

The ceiling that leaves:

  • numeric: 10×10 returns in 4.5 s, 11×11 does not return in 4 minutes
  • symbolic: 7×7 returns in 142 ms with 35173 nodes; beyond that the answer itself is the problem

The algorithm

Bareiss' fraction-free elimination is O(n^3) and every division it performs is exact — the divisor provably divides the dividend, so over an integral domain the intermediate entries stay in the ring and no condition is ever introduced. That is the property #992 was actually about; the current elimination's fault was not that it divides but that its divisions do not cancel.

The wrinkle for AngouriMath is that exactness is a fact about the ring, not something Entity division notices: (a * b) / a stays written as a quotient unless something cancels it. So a Bareiss implementation over Entity has to reduce at each step and be measured, not assumed, to come out condition-free. That is exactly the sort of thing that should be checked with boundcheck and a substitution sweep rather than argued.

Suggested shape

  • Bareiss for the numeric and low-symbol cases, where O(n^3) is the whole point
  • Laplace kept for the small fully symbolic cases, where it is already optimal and returns in milliseconds
  • the switch decided by something measured, not by n alone — a 12×12 with two variables and a 4×4 with sixteen are different problems

Not urgent: #998 already makes every size that previously worked work better, and adds three usable sizes on top. This is about extending the range, not repairing it.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions