Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization in Time Proportional to Arithmetic Work
Christopher Lourenco, Adolfo R. Escobedo, Erick Moreno‐Centeno, Timothy A. Davis · SIAM Journal on Matrix Analysis and Applications · 2019
The roundoff-error-free (REF) LU factorization, along with the REF forward and backward substitution algorithms, allows a rational system of linear equations to be solved exactly and efficiently. The REF LU factorization framework has two key properties: all operations are integral, and the size of each entry is bounded polynomially---a bound that rational arithmetic Gaussian elimination achieves only via the use of computationally expensive greatest common divisor operations. This paper develops a sparse version of REF LU, termed the Sparse Left-looking Integer-Preserving (SLIP) LU factorization, which exploits sparsity while maintaining integrality of all operations. In addition, this paper derives a tighter polynomial bound on the size of entries in L and U and shows that the time complexity of SLIP LU is proportional to the cost of the arithmetic work performed. Last, SLIP LU is shown to significantly outperform a modern full-precision rational arithmetic LU factorization approach on a set of real world instances. In all, SLIP LU is a framework to efficiently and exactly solve sparse linear systems.