Summary
Add an exact linear system solver that uses BigRational arithmetic (behind the exact feature flag) to produce provably correct solutions for small dense systems.
Current State
la-stack provides Lu::solve_vec() using f64 arithmetic, which can produce incorrect results for ill-conditioned systems. The exact module already has bareiss_det() implementing fraction-free Gaussian elimination in BigRational — the infrastructure for exact arithmetic is already in place.
Proposed Changes
Add a method such as Matrix::solve_exact(b: Vector<D>) -> Result<[BigRational; D], LaError> (or lu_exact() returning a factorization with an exact solve method) that:
- Converts f64 entries to exact
BigRational (lossless, since every finite f64 is exactly representable as a rational)
- Performs Gaussian elimination with partial pivoting in
BigRational arithmetic
- Solves via back-substitution in
BigRational
- Returns the exact rational solution (callers can convert to f64 as needed)
A fast f64 filter (similar to det_sign_exact) could short-circuit when the LU solution is well-conditioned (e.g., small residual relative to the solution norm).
Benefits
- Exact circumcenter computation: The primary consumer (delaunay) computes circumcenters by solving
Ax = b via LU. For near-degenerate simplices, the f64 solution can be wildly wrong. An exact solve would give provably correct circumcenters.
- Consistent with existing exact API: Follows the same pattern as
det_sign_exact() — fast f64 filter with exact fallback.
- Enables robust geometric computations in any downstream crate.
Implementation Notes
- Gate behind
#[cfg(feature = "exact")] like det_sign_exact
- Reuse the existing
f64_to_bigrational() conversion utility
- Consider whether to expose the raw
BigRational result or also provide a convenience method that converts back to f64
Co-Authored-By: Oz oz-agent@warp.dev
Summary
Add an exact linear system solver that uses
BigRationalarithmetic (behind theexactfeature flag) to produce provably correct solutions for small dense systems.Current State
la-stack provides
Lu::solve_vec()using f64 arithmetic, which can produce incorrect results for ill-conditioned systems. Theexactmodule already hasbareiss_det()implementing fraction-free Gaussian elimination inBigRational— the infrastructure for exact arithmetic is already in place.Proposed Changes
Add a method such as
Matrix::solve_exact(b: Vector<D>) -> Result<[BigRational; D], LaError>(orlu_exact()returning a factorization with an exact solve method) that:BigRational(lossless, since every finite f64 is exactly representable as a rational)BigRationalarithmeticBigRationalA fast f64 filter (similar to
det_sign_exact) could short-circuit when the LU solution is well-conditioned (e.g., small residual relative to the solution norm).Benefits
Ax = bvia LU. For near-degenerate simplices, the f64 solution can be wildly wrong. An exact solve would give provably correct circumcenters.det_sign_exact()— fast f64 filter with exact fallback.Implementation Notes
#[cfg(feature = "exact")]likedet_sign_exactf64_to_bigrational()conversion utilityBigRationalresult or also provide a convenience method that converts back to f64Co-Authored-By: Oz oz-agent@warp.dev