Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization in Time Proportional to Arithmetic Work
Abstract
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 the 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 for efficiently and exactly solving sparse linear systems.
Subject
Computational Linear AlgebraRoundoff errors
Exact Algorithms
Sparse Exact Linear Algebra
Sparse Exact Linear Systems
LU Factorization
Sparse Exact LU Factorization
Department
Computer Science and EngineeringIndustrial and Systems Engineering
Collections
Citation
The following license files are associated with this item:
Except where otherwise noted, this item's
license is described as
Attribution-NonCommercial-NoDerivatives 4.0 International
Related items
Showing items related by title, author, creator and subject.
-
Groger, Susan May (Texas A&M University, 1988)Not available
-
Feiring, Bruce Robert (Texas A&M University. Libraries, 1979)In this dissertation, the problem of optimizing a nonlinear objective function subject to linear and/or nonlinear constraints is considered. When the constraints are nonlinear, it is particularly advantageous to transform ...
-
Rousseau, Cecil Clyde (Texas A&M University. Libraries, 1968)We investigate the usefulness of a perturbation theory which starts from exactly localized states. We find that for various single particle problems, the ground-state energy as a function of the effective coupling strength ...