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

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

Matrix factorization algorithms are susceptible to the accumulation of roundoff errors inherent in floating point computations, which can affect the behavior of optimization solvers and the validity of their outputs. Although egregiously erroneous outcomes are admittedly infrequent, their non-negligible plausibility detracts from the implicit trust placed on mathematical programming software. This research helps to address this very important issue. It is important to highlight that the results of this paper led to the subsequent development of the SParse EXact (SPEX) software package. The SPEX software package implements the sparse left-looking integer-preserving (SLIP) LU factorization (an adaptation of the REF LU factorization to the sparse case). The SPEX package was built into commercial-quality code and is available in C and through a MATLAB interface. This software package is exceptionally robust; all code has undergone 100% test coverage and is accompanied by scaffolding code to test loop invariants and data sanity. The work is encapsulated by a paper by C. Lourenco, J. Chen, E. Moreno-Centeno, and T. Davis published in ACM TOMS in 2022, and the code has been inducted in the Collected Algorithms of the ACM (Algorithm 1XXX).

Adolfo R Escobedo
Arizona State University

Read the Original

This page is a summary of: Solution of Dense Linear Systems via Roundoff-Error-Free Factorization Algorithms, ACM Transactions on Mathematical Software, August 2018, ACM (Association for Computing Machinery), DOI: 10.1145/3199571.
You can read the full text:

Read

Contributors

The following have contributed to this page