EXACT SOLUTION OF SPARSE LINEAR SYSTEMS VIA LEFT-LOOKING ROUNDOFF-ERROR-FREE LU FACTORIZATION IN TIME PROPORTIONAL TO ARITHMETIC WORK Academic Article uri icon

abstract

  • 2019 Society for Industrial and Applied Mathematics 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.

published proceedings

  • SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS

author list (cited authors)

  • Lourenco, C., Escobedo, A. R., Moreno-Centeno, E., & Davis, T. A.

citation count

  • 6

complete list of authors

  • Lourenco, Christopher||Escobedo, Adolfo R||Moreno-Centeno, Erick||Davis, Timothy A

publication date

  • January 2019