Quadratic-scale bit complexity for well-conditioned sparse systems
Fix a positive integer $c$. Let $A \in \mathbb{Q}^{n \times n}$ be nonsingular, with $m = \operatorname{nnz}(A)$ nonzero entries and condition number $\kappa_2(A) = \|A\|_2 \|A^{-1}\|_2 \le n^c$, given by the list of its nonzero entries, and let $b \in \mathbb{Q}^n \setminus \{0\}$, every numerator and denominator in the input having at most $c \lceil \log_2(2n) \rceil$ bits. Here $\widetilde O$ hides powers of $\log n$, with constants that may depend on $c$, and cost counts all bit operations, arithmetic included. In exact arithmetic, $n$ iterations of a Krylov method, such as conjugate gradient applied to the normal equations, solve such a system with $\widetilde O(nm)$ arithmetic operations, but the precision this needs grows with the dimension of the Krylov subspace. In finite precision, Peng and Vempala's analysis of a block Krylov method, as improved by Nie, solves such systems with $\widetilde O(m^{(\omega-2)/(\omega-1)} n^2)$ bit operations, where $\omega$ is the exponent of matrix multiplication.
Problem. For each fixed $c$, is there a randomized algorithm that uses $\widetilde O(nm)$ bit operations and, for every such $A$ and $b$, with probability at least $0.99$ outputs a rational vector $\widehat x$ with $$\|\widehat x - A^{-1} b\|_2 \le n^{-c} \|A^{-1} b\|_2?$$
Source: Amsel et al. (2026), Problem 2.10, from the Simons Institute workshop on linear systems and eigenvalue problems (2025); stated in this form, with polynomial conditioning, short rational inputs and relative accuracy n^{-c}, by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- NA — Numerical Analysis
- Keywords
- AIM Open Applied Problems, bit complexity, sparse linear systems
References
@misc{amsel2026,
author = {Amsel, Noah and Baumann, Yves and Beckman, Paul and B{\"u}rgisser, Peter and Cama{\~n}o, Chris and Chen, Tyler and Chow, Edmond and Damle, Anil and Derezinski, Michal and Embree, Mark and Epperly, Ethan N. and Falgout, Robert and Fornace, Mark and Greenbaum, Anne and Greif, Chen and Halikias, Diana and Huang, Zhen and Jarlebring, Elias and Koutis, Yiannis and Kressner, Daniel and Kyng, Rasmus and Liesen, J{\"o}rg and Lok, Jackie and Meyer, Raphael A. and Nakatsukasa, Yuji and Pearce, Kate and Peng, Richard and Persson, David and Rebrova, Eliza and Schneider, Ryan and Shah, Rikhav and Solomonik, Edgar and Srivastava, Nikhil and Townsend, Alex and Webber, Robert J. and Williams, Jess},
title = {Linear Systems and Eigenvalue Problems: Open Questions from a {S}imons Workshop},
year = {2026},
eprint = {2602.05394},
archivePrefix = {arXiv},
note = {Revised August 2026 (v3)},
}
@inproceedings{peng2021,
author = {Peng, Richard and Vempala, Santosh},
title = {Solving Sparse Linear Systems Faster than Matrix Multiplication},
booktitle = {Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)},
publisher = {SIAM},
year = {2021},
pages = {504--521},
doi = {10.1137/1.9781611976465.31},
eprint = {2007.10254},
archivePrefix = {arXiv},
}
@inproceedings{nie2022,
author = {Nie, Zipei},
title = {Matrix anti-concentration inequalities with applications},
booktitle = {Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)},
publisher = {ACM},
year = {2022},
pages = {568--581},
doi = {10.1145/3519935.3520060},
eprint = {2111.05553},
archivePrefix = {arXiv},
}
@misc{aim-sparse-linear-solve-bit-complexity,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Quadratic-scale bit complexity for well-conditioned sparse systems}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/044-sparse-linear-solve-bit-complexity.md},
note = {Entry 044 at commit a153f46, 2026-10-13},
}
Resolution claims
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 …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-15 | Needs verification → Solution claimed | — | Recorded here: arXiv:2609.38101v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00322, "Quadratic-scale bit complexity for well-conditioned sparse systems", clopen.solutions.