Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time

Jess Banks, Jorge Garza-Vargas, Archit Kulkarni +1

We exhibit a randomized algorithm which given a matrix $A\in {\mathbb{C}}^{n\times n}$ with $\Vert A\Vert \le 1$ and $\delta >0$, computes with high probability an invertible $V$ and diagonal $D$…