# Reference for QR algorithm for complex matrix

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?

• I'm not familiar with the book you mention, but if you're talking about householder qr, the answer is yes. See the lapack routine ZGEQR2, netlib.org/lapack/explore-3.1.1-html/zgeqr2.f.html#ZGEQR2.1
– vibe
Dec 4 '19 at 22:54
• Given the "eigenvalues" tag, the OP is probably referring to the (Francis) QR iteration for diagonalization, not the Householder QR factorization. Dec 5 '19 at 14:50

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.