A cubic-time Schur algorithm with logarithmic mantissa precision

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 $\|A - QTQ^*\|_2 \le \delta$ and
$\|Q^*Q - I\|_2 \le \delta$, with no separation, simplicity or
diagonalizability assumption on $A$. The algorithm perturbs $A$ by a finitely
sampled complex Gaussian matrix, using the regularization theorem of Banks,
Garza-Vargas, Kulkarni and Srivastava, and splits the spectrum recursively
along one random dyadic grid, computing spectral projectors by Newton's sign
iteration and their ranges by Gaussian sampling and Householder QR. A contour
estimate bounds the remaining compositions of the sign iteration uniformly, so
rounding errors accumulate additively.