A cubic-time Schur algorithm using logarithmic precision
Work in the usual relative-error floating-point model, with an exponent range large enough that overflow and underflow do not occur, and let $\|\cdot\|_2$ be the spectral norm. Banks, Garza-Vargas, Kulkarni and Srivastava gave a randomized algorithm that, given $A \in \mathbb{C}^{n \times n}$ with $\|A\|_2 \le 1$ and $\delta > 0$, computes with high probability an invertible $V$ and a diagonal $D$ with $\|A - VDV^{-1}\|_2 \le \delta$ in nearly matrix multiplication time, using $O(\log^4(n/\delta)\log n)$ bits of precision.
Problem. Is there a randomized floating-point algorithm, with universal constants and a universal exponent $c$, such that for every $A \in \mathbb{C}^{n \times n}$ with $\|A\|_2 \le 1$ and every $0 < \delta < 1/2$ it uses at most $O(n^3 \log^c(n/\delta))$ arithmetic operations and $O(\log(n/\delta))$ mantissa bits and, with probability at least $0.99$, returns an upper triangular $T$ and a matrix $Q$ with $$\|A - QTQ^*\|_2 \le \delta, \qquad \|Q^*Q - I\|_2 \le \delta,$$ without any assumption on the separation of the eigenvalues of $A$ or on its diagonalizability?
Source: Amsel et al. (2026), Problem 3.3 (scribes Bürgisser, Pearce and Schneider), for backward-error diagonalization or Schur form. In this form, for the Schur form with ‖A‖₂ ≤ 1, 0 < δ < 1/2, success probability 0.99 and both residuals bounded by δ, OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- SP
- Keywords
- floating-point arithmetic, OpenProblemsInNLA, randomized algorithms, Schur decompositions
- Literature checked
- Oct. 8, 2026 by clemens-admin
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},
}
@article{banks2023,
author = {Banks, Jess and Garza-Vargas, Jorge and Kulkarni, Archit and Srivastava, Nikhil},
title = {Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time},
journal = {Found. Comput. Math.},
volume = {23},
number = {6},
year = {2023},
pages = {1959--2047},
doi = {10.1007/s10208-022-09577-5},
eprint = {1912.08805},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ie08,
author = {Townsend, Alex},
title = {{IE-08}: A cubic-time Schur algorithm using logarithmic precision},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/eigenvalues-and-inverse-problems/IE-08/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
The paper proves that there are universal constants $C, c > 0$ and a randomized floating-point algorithm which, given $A \in \mathbb{C}^{n \times n}$ with $\|A\|_2 \le 1$ and $0 < \delta < 1/2$, uses at most $Cn^3\log^c(n/\delta)$ arithmetic operations and $C\log(n/\delta)$ mantissa bits and, with probability at least $0.99$, returns an exactly upper triangular $T$ and a $Q$ with …
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-00219, "A cubic-time Schur algorithm using logarithmic precision", clopen.solutions.