The full text of this item is not available at this time because the student has placed this item under an embargo for a period of time. The Libraries are not authorized to provide a copy of this work during the embargo period, even for Texas A&M users with NetID.
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.
Subject
sparse factorization updateslow-rank modification
integer-preserving Gaussian elimination
sparse linear systems
sparse matrix algorithms
full precision
exact solution
roundoff errors
exact matrix factorization
linear program
simplex
Citation
Chen, Jinhao (2022). Roundoff-Error-Free Solution to Sparse Linear System: Low-Rank Modification. Doctoral dissertation, Texas A&M University. Available electronically from https : / /hdl .handle .net /1969 .1 /198004.