Exactly Solving Sparse Rational Linear Systems via Roundoff-Error-Free Cholesky Factorizations
Loading...
Date
2022
Journal Title
Journal ISSN
Volume Title
Publisher
SIAM
Abstract
Exactly solving sparse symmetric positive definite (SPD) linear systems is a key problem in mathematics, engineering, and computer science. This paper derives two new sparse roundoff-error-free (REF) Cholesky factorization algorithms that exactly solve sparse SPD linear systems 𝐴𝑥=𝑏, where 𝐴∈ℚ𝑛𝑥𝑛 and 𝑥,𝑏∈𝑄𝑛𝑥𝑝. The key properties of these factorizations are that (1) they exclusively use integer-arithmetic and (2) in the bit-complexity model, they solve the linear system 𝐴𝑥=𝑏 in time proportional to the cost of the integer-arithmetic operations. Namely, the overhead related to data structures and ancillary operations (those not strictly required to perform the factorization) is subsumed by the cost of the integer arithmetic operations that are essential/intrinsic to the factorization. Notably, to date, our algorithms are the only exact algorithm for solving SPD linear systems with this asymptotically efficient complexity bound. Computationally, we show that the novel factorizations are faster than both sparse rational-arithmetic LDL and sparse exact LU factorization. Altogether, the derived sparse REF Cholesky factorizations present a framework to solve any rational SPD linear system exactly and efficiently.
Description
Keywords
Computational Linear Algebra, Sparse Exact Linear Algebra, Sparse Exact Linear Systems, Exact Algorithms, Sparse Exact Cholesky Factorization, Sparse Exact Matrix Factorizations
Citation
Christopher Lourenco and Erick Moreno-Centeno (2022) Exactly Solving Sparse Rational Linear Systems via Roundoff-Error-Free Cholesky Factorizations. SIAM Journal on Matrix Analysis and Applications 43(1):439-463