arXiv preprint ·
Solving Linear Systems in $\widetilde{O}(mn \log \fracκε)$ Bit Operations
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $κ$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
CI-PINN: Causal Integral Physics-Informed Neural Network for Solving Evolution Equations
High-accuracy simulation of Picard HMC, part I: Gaussian cloud correction
Into the danger zone: stable extrapolation in high-dimensional function and operator learning
Minimax rates for learning spectral Barron functions by deep ReLU neural networks
Hybrid Joint-Selective Optimization: Reduced-Space Levenberg-Marquardt Refinement of Low-Dimensional Parameters of Interest
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.