In this thesis we study the computational problem of approximately diagonalizing an arbitrary complex, n⨉n matrix A in floating point arithmetic — that is, finding V invertible and D diagonal with ||A - VDV⁻¹|| ≤ δ||A|| for some desired accuracy δ>0. Our major contributions are the following.
(i) We prove that a randomized variant of the Spectral Bisection algorithm can approximately diagonalize any n⨉n matrix using O(Tₘₘ(n) log(n/δ) log n) arithmetic operations, on a floating point machine with O(log⁴(n/δ) log n) bits of precision, with probability 1 - O(1/n) — where Tₘₘ(n) is the arithmetic cost of numerically stable n⨉n matrix multiplication.
(ii) We prove that for every k = 2,4,8,... and B ≥ 1 there is a shifting strategy for the Shifted QR algorithm, S(k,B), which converges rapidly in exact arithmetic on every Hessenberg matrix H₀ with eigenvector condition number less than B (e.g. of the form H₀ = VDV⁻¹ with D diagonal and ||V||||V⁻¹||≤B). The resulting algorithm gives a sequence H₀,H₁,H₂,... of Hesssenberg matrices unitarily similar to H₀, and rapid convergence means: each iteration costs O(n² k log k + B^(16k⁻¹ log k)) arithmetic operations, and for any ω>0, it takes O(log(1/ω)) iterations to drive the smallest subdiagonal entry below ω||H₀||.
(iii) We prove that the shifting strategy S(k,B) can be implemented in floating point as a randomized algorithm, using O(k log(nB||H₀||/ωgap(H₀))) bits of precision (where gap(H) is the minimum eigenvalue gap, or the smallest distance between two eigenvalues of H), and succeeding with probability 1 - O(1/n). For any n⨉n matrix A, this can be used to give a randomized algorithm for computing the matrix D in the notion of approximate diagonalization above (e.g., the approximate eigenvalues a matrix δ||A||-close to A), using O(n³ log²(n/δ) poly(log(log(n/δ)))) arithmetic operations, on a floating point machine with O(log²(n/δ) log(log(n/δ))) bits of precision, again succeeding with probability 1-O(1/n).
A crucial step along the way is a new result in random matrix theory: for any complex n⨉n matrix A and δ > 0, if G is an n⨉n matrix with independent, standard complex Gaussian entries, then with probability at least 1 - O(1/n), A + δG has eigenvector condition number at most n²/δ and minimum eigenvalue gap at least δ/n². We show similar results for random real perturbations of real matrices as well.
