Lourenco, Christopher J. (2020-06). Efficient Algorithms for the Exact Solution of Sparse Linear Systems in Time Proportional to Arithmetic Work. Doctoral Dissertation.
Thesis
Obtaining the exact rational solution of sparse systems of linear equations (SLEs), Ax =b, is a fundamental problem in mathematics, engineering, and computer science. The two most common tools used to solve these sparse linear systems are LU and Cholesky factorizations. However, despite the widespread use of these factorization algorithms, there are numerous documented cases where roundoff errors, accrued during the construction and implementation of these factorizations in floating-point arithmetic, may cause commercial solvers to produce erroneous solutions. Indeed, through a phenomenon referred to as the snowball effect, roundoff errors may propagate, accumulate, and magnify, ultimately rendering the output of linear solvers egregiously incorrect. To remedy these inaccuracies, this dissertation derives a new set of algorithms to efficiently obtain the exact solution of sparse SLEs. First, we present the Sparse Left-looking Integer-Preserving (SLIP) LU factorization, a factorization algorithm which exactly solves unsymmetric sparse SLEs. In addition, we derive the left-looking and up-looking integer-preserving Cholesky factorization algorithms for exactly solving SPD SLEs. Each of these factorization algorithms has two key properties: (1) all operations are integral, thus, no roundoff errors are accrued during the construction and implementation of these factorizations and (2) each of these factorizations solve the linear system Ax = b in time proportional to arithmetic work--to date, the only exact factorization algorithms with this asymptotically efficient bound. Next, we derive the weighted approximate minimum fill (WAMF) algorithm, a graph based algorithm which preorders the matrix A in order to reduce the total work required in the ensuing factorization. WAMF modifies the widely used minimum degree heuristic in order to account for both the sparsity of the input matrix as well as the bit-length of its entries. Altogether, this dissertation presents a framework to exactly solve sparse linear systems in an efficient manner. Specifically, we computationally show that each of these integer-preserving factorizations dramatically outperforms its rational-arithmetic counterpart. We benchmark the accuracy of MATLAB sparse backslash, illustrating that exact algorithms are necessary for about 5% of real world instances. In addition, we show that using the WAMF algorithm as a preordering for each factorization outperforms using the state-of-the-art COLAMD and AMD preorderings on unsymmetric and SPD matrices, respectively. Finally, we implement all of these algorithms into ANSI C and make the software available to the general community at https://github.com/clouren. Notably, the SLIP LU factorization package is commercial quality software, and is distributed as a component of SuiteSparse, one of the world's largest and most widely implemented software packages for solving sparse linear systems.
