1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – vibe Dec 4 '19 at 22:54
  • 1
    $\begingroup$ Given the "eigenvalues" tag, the OP is probably referring to the (Francis) QR iteration for diagonalization, not the Householder QR factorization. $\endgroup$ – rchilton1980 Dec 5 '19 at 14:50
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer! I am just doubting that because I could only find references that introduce the Implicit shift QR algorithm for real matrices. $\endgroup$ – danft Dec 6 '19 at 0:49
  • $\begingroup$ I found this article by Watkins that seems to develop the algorithm for the complex case as well. $\endgroup$ – danft Dec 12 '19 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.