Deterministic fast algorithm solves large sparse linear systems accurately
Solving Linear Systems in $\widetilde{O}(mn \log \fracκε)$ Bit Operations
Data Structures and AlgorithmsComputational Complexity
Summary
Solving large systems of linear equations quickly and accurately is important for many computer and engineering tasks. This paper presents a new method that uses fewer computational steps even when the system is large and sparse. The authors improve on previous techniques by applying a clever integer-based approach and mathematical tools to ensure precise solutions. This method works efficiently for systems where numbers have limited size and can handle any desired accuracy.
What this means in practice
- •For scientific computing engineers: Speed up solving large sparse linear systems with guaranteed accuracy for simulations and modeling tasks.
- •For data scientists: Improve the efficiency of numerical solutions in machine learning algorithms that rely on large linear system solves.
Authors
Jonathan A. Kelner
Abstract
We give a deterministic algorithm that solves a nonsingular linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ has $m$ nonzero entries and condition number $κ$, to any relative residual tolerance $0<ε\le1/2$ using $\widetilde{O(}mn\log(κ/ε))$ bit operations for inputs with logarithmically many bits per entry. For sparse, polynomially conditioned systems with $m=\widetilde{O}(n)$, this gives an $\widetilde{O}(n^2)$ algorithm for any inverse-polynomial accuracy, improving on the algorithm of Peng and Vempala, as sharpened by Nie, whose running time in this regime is approximately $O(n^{2.2707})$ with the best current matrix multiplication exponent, and largely closing a gap between the idealized performance of the conjugate gradient method in exact arithmetic and the running time achievable with finite-precision computation that has persisted for over 70 years. The algorithm is surprisingly simple. For integer inputs, we apply Dixon's lifting algorithm to the perturbed system $(A+I/R)x=b$ for a suitable integer $R$. After scaling, the matrix of this system is $RA+I\equiv I\pmod R$, so its modular inverse is trivial, and each lifting step needs only a sparse matrix-vector product with $A$ on $O(\log R)$-bit numbers. Fast rational reconstruction then recovers the exact solution of the perturbed system, which is an $ε$-accurate solution of the original one. Normalization and rounding extend the result to fixed-point and floating-point inputs, with floating-point outputs represented using short integer significands and a common encoded exponent. A computable certificate removes the need for prior knowledge of $κ$.