Roundoff-Error-Free Solution to Sparse Linear System: Low-Rank Modification

Abstract

When solving the system of equations Ax = b with finite precision arithmetic, it is well known that x can be computed more efficiently and numerically stably via the application of the factorization of A, rather than by direct computation of A−1. In many applications, once the factorization of A is computed and Ax = b is solved, it is quite common to solve a modified system A¯x¯ = . For example, in each iteration of the simplex method (one of the popular linear programming solvers), A¯ is constructed by replacing one column of A. To summarize, there are two major types of (elementary) modifications on matrix A among different applications: 1) column replacement in forms of either a single column (or row) replacement for an unsymmetric matrix, or a symmetric column and row replacement for a symmetric matrix; 2) rank-1 update/downdate in forms of either A¯ = A + σwvT for an unsymmetric matrix, or A¯ = A + σwwT for a symmetric matrix, with σ > 0 for update and σ < 0 for downdate, w and v being vectors with appropriate dimension. Other types of modifications can be constructed as sequence/combination of these two modifications.

Recently, a series of algorithms have been developed to obtain the exact LU or Cholesky factorization based on integer-preserving Gaussian elimination and, subsequently, the exact solution for the given system of equations. This dissertation derives a new set of algorithms to efficiently update the exact LU or Cholesky factorization due to either column replacement or rank-1 update/downdate on the original sparse matrix.

Moreover, a software package named SPEX (meaning SParse EXact) is implemented and fully tested for exactly solving sparse linear systems. This dissertation will go over some important features of this software package. This software is of commercial quality and can be found at https://github.com/clouren/SPEX, or https://github.com/DrTimothyAldenDavis/SuiteSparse.

To illustrate the performance of the SPEX library, especially, the core user-callable functions for sparse exact factorization updates, we implement simplified exact linear programming solvers based on the SPEX library. Experimental results are obtained for real-world linear programming problems, which show that updating these exact factorizations can be typically 10x to 100x faster than (re-)factorizing the matrices from scratch.

Finally, the dissertation investigates the GraphBLAS library to summarize methods to improve the performance of GraphBLAS-based algorithms and to provide potential direction of improvement for GraphBLAS.