Algorithms for Solving Linear Systems of Equations Exactly and Efficiently

What is it about?

This work develops the roundoff-error-free (REF) factorization framework through which rational systems of linear equations (i.e., Ax=b) can be solved exactly and efficiently by working entirely in integer arithmetic. It consists of the REF LU and REF Cholesky factorizations and REF forward and backward substitution algorithms. Although the paper introduces these tools within the context of linear programming, the algorithms can be implemented within any other context where rational systems of equations must be solved exactly.

Featured Image

Why is it important?

In short, by providing efficient fail-safe mechanisms for validating basic solutions within optimization solvers, the REF factorization framework aims to make significant practical advances for two reasons: (1) solutions yielded by the standard fixed-precision LP and MIP solvers come with certificates (i.e., primal and dual feasibility) that can be validated only approximately within numerical tolerances; and (2) state-of-the-art computationally-exact versions of these solvers implement algorithms that rely on exact rational arithmetic, which involves recurrently performing greatest common divisor (gcd) calculations and other expensive operations (needed to bound the growth in memory that unlimited-precision coefficients occupy).