Roundoff-error-free factorization algorithms for the exact solution of linear systems

What is it about?

The research encompassed by this paper contributes to the advancement of matrix factorization algorithms, which have long served as the workhorse of optimization software. LU and Cholesky factorizations have become intertwined with linear programming (LP) and mixed-integer programming (MIP) solvers ever since Bartels and Golub published their landmark paper in 1969. Bartels and Golub demonstrated that solving systems of linear equations (SLEs) within the simplex algorithm via LU factorization was computationally superior to the then-popular product form of the inverse approach. In the ensuing decades, LU and Cholesky factorization algorithms have received increased attention and continually improved their efficiency and numerical advantages. A prominent focus of these studies has been to tailor these matrix factorizations to the types of SLEs encountered in various mathematical programming contexts. Based on a long-running series of these and other related advances, many researchers and practitioners consider LP a ``solved problem''. However, there remain important computational issues that contradict this idealistic view. Most notably, roundoff errors intrinsic to floating-point operations may cause commercial optimization solvers to misclassify suboptimal solutions as optimal, infeasible bases as feasible, and infeasible bases as optimal. While individually harmless, roundoff errors may propagate, accumulate, magnify, and thus, render the output of LP solvers egregiously incorrect. Therefore, there is a fundamental need to develop efficient algorithms and robust software which account for and ultimately eliminate roundoff errors when solving LPs. This is especially critical given that LPs (and MIPs) encountered in practice are frequently ill-conditioned, exacerbating the effect of roundoff errors in optimization algorithms. It is also important to highlight that several LP and MIP applications require exact solutions, including, but not limited to, feasibility problems, compiler optimization, and computational-based mathematical proofs. This paper introduces theory and algorithms for solving any rational SLE exactly and efficiently using integer-preserving arithmetic. It performs a series of computational experiments on dense matrices to demonstrate that the proposed algorithms are significantly faster and require less storage than their exact rational arithmetic counterparts, which are currently utilized in state-of-the-art exact LP solvers.

Featured Image

Photo by Nick Fewings on Unsplash

Photo by Nick Fewings on Unsplash

Why is it important?

There are two mainstream approaches for solving LPs exactly: certify and repair and iterative refinement. Related algorithms, such as hybrid branch and bound, have also been developed for solving MIPs exactly. To enable their practical implementation, these approaches rely on a mixture of fixed and unlimited precision; more specifically, they use floating-point arithmetic for the vast majority of operations and sparingly use exact arithmetic for validation purposes. These mixed-precision approaches are categorically superior to full unlimited-precision implementations of the simplex algorithm. Nevertheless, their exact LU factorization subroutines can still occupy up to 90% of the solution time and, thus, are a significant bottleneck for the scalability of exact LP. A sizeable portion of the computational slowdown is tied to the greatest common divisor (GCD) operations required when using exact rational arithmetic to limit growth in the operands' bit-length or encoding size. Despite the GCDs' outsize impact on the run-times of exact factorization algorithms, little attention has been devoted to circumventing these expensive operations. The roundoff-error-free (REF) matrix-factorization framework developed in this research provides an alternative to exact LU factorization based on rational arithmetic. This framework builds upon integer-preserving Gaussian elimination, an exact algorithm for solving SLEs independently discovered by several researchers. The algorithm performs all fundamental operations involved in row reduction---addition, subtraction, multiplication, and division---without using or storing fractional entries. The main contribution of this work is to extend integer-preserving Gaussian elimination into a factorization-based approach and to analyze the theoretical and computational implications of this framework vis-à-vis exact rational arithmetic factorization algorithms currently utilized in state-of-the-art exact LP solvers.

Perspectives