Near-quadratic solution cost at a prescribed backward error
Work in an exact real arithmetic model in which an algorithm may read every entry of its input and is charged one operation for each arithmetic operation on real numbers, square root, comparison, and independent draw of a standard Gaussian variable or a random bit. For $A \in \mathbb{R}^{n \times n}$, $b \in \mathbb{R}^n$ and $x \ne 0$, the normwise backward error of $x$, with perturbations allowed in $A$ only, is $\|Ax - b\|_2/(\|A\|_2 \|x\|_2)$. Dereziński, Nakatsukasa and Rebrova gave randomized algorithms that reach backward error $\varepsilon$ with probability at least $1 - \delta$ in time $O((n^2 + \log(1/\delta))/\sqrt{\varepsilon})$ when $A$ is positive semidefinite, and in time $O(n^2 \log(n/\delta)/\varepsilon)$ for general $A$.
Problem. Are there a randomized algorithm and absolute constants $C, q > 0$ such that, for every $n \ge 1$, every nonsingular $A \in \mathbb{R}^{n \times n}$ with $\|A\|_2 = 1$, every $b \in \mathbb{R}^n \setminus \{0\}$ and every $0 < \varepsilon < 1/2$, the algorithm uses at most $C n^2 \varepsilon^{-q}$ operations and returns $x \ne 0$ with $$\Pr\left\{\frac{\|Ax - b\|_2}{\|A\|_2 \|x\|_2} \le \varepsilon\right\} \ge 0.99?$$ The condition $\|A\|_2 = 1$ is a promise on the input, $C$ and $q$ may not depend on $n$, $A$, $b$ or $\varepsilon$, and a deterministic algorithm also qualifies.
Source: Dereziński, Nakatsukasa and Rebrova (2026), Section 1, who study in backward error the long-standing question of solving an n × n linear system to relative error ε in O(n² poly(1/ε)) time, and Section 7, which asks whether convergence independent of n can be attained for general systems; in this form (an exact real arithmetic model, ‖A‖₂ = 1, backward error in A only, success probability 0.99), OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Keywords
- backward errors, linear systems, OpenProblemsInNLA, randomized algorithms
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@misc{derezinski2026,
author = {Derezi{\'n}ski, Micha{\l} and Nakatsukasa, Yuji and Rebrova, Elizaveta},
title = {Towards Universal Convergence of Backward Error in Linear System Solvers},
year = {2026},
eprint = {2604.16075},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ie12,
author = {Townsend, Alex},
title = {{IE-12}: Near-quadratic solution cost at a prescribed backward error},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/linear-systems-and-elimination/IE-12/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
We give an explicit randomized algorithm, in an exact-real arithmetic model in which every input entry may be read, for $Ax = b$ with $A \in \mathbb{R}^{n \times n}$, $\|A\|_2 = 1$, $b \ne 0$ and $0 < \varepsilon < 1/2$. Its deterministic worst-case operation count is $O(n^2\varepsilon^{-3})$, with indexed table reads and writes charged one operation each; with probability …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00221, "Near-quadratic solution cost at a prescribed backward error", clopen.solutions.