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.
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.Determinantcomputed by Gaussian elimination left the pivots as literal divisions, so the expression wasNaNwherever 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 thatInnerSimplifiedthen had to grind down.Measured, property only, both arms built from source on one machine:
What is left
Laplace is
O(n!). For a fully symbolic matrix that is not an overhead — the determinant genuinely hasn!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, andO(n^3)work suffices.The ceiling that leaves:
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
Entitydivision notices:(a * b) / astays written as a quotient unless something cancels it. So a Bareiss implementation overEntityhas 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 withboundcheckand a substitution sweep rather than argued.Suggested shape
O(n^3)is the whole pointnalone — a 12×12 with two variables and a 4×4 with sixteen are different problemsNot 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.