Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time
Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time
We exhibit a randomized algorithm which given a square matrix A ∈ \mathbbC <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n×n</sup> with ||A|| ≤ 1 and , computes with high probability an invertible V and diagonal D such that ||A-VDV <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> || ≤ δ in O(TMM(n)log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> (n/δ)) arithmetic operations on …