Skip to main content
eScholarship
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Electronic Theses and Dissertations bannerUC Berkeley

Random Matrices and Provable Algorithms for Approximate Diagonalization

Abstract

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.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View