Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
I am trying to find out if the known QR algorithm to find the eigenvalues of a real matrix, which can be found in the book Fundamentals of Matrix Computations, can also be used for complex matrices and still runs in $O(n^3)$?
Also, if yes, does anyone know any reference for it?
If you're lucky enough to have a complex-hermitian $\mathbf A$, the eigendecomposition of $\mathbf A$ can be computed using basically the same algorithmic machinery as the real-symmetric case: an initial/frontend pass to reduce to tridiagonal form $\mathbf T$ via Householder reflections, followed by shifted-QR iterations on $\mathbf T$. Notably, a complex-hermitian $\mathbf A$ can be orthogonally reduced to a real-symmetric tridiagonal $\mathbf T$! This enables extensive reuse of the innermost shifted-QR routines.
Unfortunately, the situation is less rosy for real-nonsymmetric $\mathbf A$ or complex-nonhermitian $\mathbf A$. In fact, you might not even want the eigendecomposition here, but rather the Schur decomposition. It too displays the eigenvalues but can be more stable/accurate because it uses only orthogonal transformations. And the Schur vectors are often just as useful as the eigenvectors depending upon the application.
In the real-nonsymmetric case, the best you can do with the Householder frontend is a reduction to Hessenberg form, then you perform shifted QR iterations on that. The shifting strategy is messy. In the symmetric case a rank-2 shift is robust because the eigenvalues can only be pure-real or conjugate-pairs .. but this doesn't hold in the nonsymmetric case. You have to use higher-rank shifts ("multishifted QR"). Fortunately these algorithmic difficulties do not jeopardize the overall complexity, it's still $\mathcal O(n^3)$
I think the complex-nonhermitian case is worse still, as I don't believe the Householder frontend can reduce a general complex matrix to real-Hessenberg form using unitary transformations (though I admit I am not certain of this). I would expect the inner shifted QR iteration to be very messy (mainly due to complexity of shifting strategy - for this kind of input the eigenvalues could be anywhere). I believe this is still $\mathcal O(n^3)$ too.
A good entry point for eigendecomposition of general complex $\mathbf A$ would be LAPACK's ZGEEV routine - just be aware it's a pretty deep hole.
