Solving Linear Systems in Õ(mn log κ/ε) Bit Operations
Abstract
We give a deterministic algorithm that solves a nonsingular linear system Ax=b, where A∈ℝn× n has m nonzero entries and condition number κ, to any relative residual tolerance 0<ε≤1/2 using O(̃mnlog(κ/ε)) bit operations for inputs with logarithmically many bits per entry. For sparse, polynomially conditioned systems with m=Õ(n), this gives an Õ(n2) 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(n2.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≡ Ipmod 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 κ.
Related
- On Convergence Behavior of Randomized Kaczmarz-type Methods for Solving Doubly Noisy Linear Systems
- Solving Multiobjective Linear Set Optimization Problems
- WAMS Operations in modern power systems: A median expectation-based state estimation approach for grid resilience towards cyber attacks
- Solving Large-Scale Sparse Linear Complementarity Problems Using a Relaxed Shifted Matrix-Splitting Modulus-Based Iteration Method
- On randomized batch-sampling coordinate descent methods for solving linear least-squares problems
BibTeX
@misc{kelner2026solving,
title = {{Solving Linear Systems in $\widetildeO(mn \log \fracκε)$ Bit Operations}},
author = {Jonathan A. Kelner},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38101},
eprint = {2609.38101},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38101},
}
RIS
TY - UNPB
TI - Solving Linear Systems in Õ(mn log κ/ε) Bit Operations
AU - Jonathan A. Kelner
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.38101
UR - https://arxiv.org/abs/2609.38101
AB - We give a deterministic algorithm that solves a nonsingular linear system Ax=b, where A∈ℝ^n× n has m nonzero entries and condition number κ, to any relative residual tolerance 0<ε≤1/2 using O(̃mnlog(κ/ε)) bit operations for inputs with logarithmically many bits per entry. For sparse, polynomially conditioned systems with m=Õ(n), this gives an Õ(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≡ Ipmod 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 κ.
ER -