1
$\begingroup$

It is possible to find many references describing the QR Algorithm with more or less refinements to approximate the eigenvalues of a square matrix $A\in\mathbb{R}^{n\times n}$.

I implemented a version which can be summarized by these two usual steps:

  • Step 1. Transformation of $A$ into its upper Hessenberg form $H$ using orthogonal similarity transforms. It takes $\mathcal{O}(n^3)$ operations using Householder reflection matrices.
  • Step 2. Application of several QR iterations to $H$ until some convergence criteria is met. Since $H$ is upper Hessenberg, each iteration takes $\mathcal{O}(n^2)$ operations (in the general case).

For a general square matrix $A\in\mathbb{R}^{n\times n}$, this algorithm converges to the real Schur decomposition of $A$. By carefully accumulating all the orthogonal transformation matrices of Step 1 and Step 2 into an orthogonal matrix $Q$, it means that we obtain $A= QUQ^T$ (where U is an upper triangular matrix called the Schur form of A).

In the case $A$ is symmetric (which is the most discussed case in many references), $U$ is diagonal and $Q$ are the eigenvectors of $A$ since we have the eigendecomposition of $A$.

My questions concerns the unsymmetric case: how can we compute the eigenvectors of $A$?

I suppose that it is not possible to do it with the $Q$ and $U$ matrices from the Schur decomposition, right? I found some references saying that, given the eigenvalues, we could use Inverse iterations to find the eigenvectors. But then it is very costly since applying Inverse iteration for one eigenvalue cost $\mathcal{O}(n^3)$ operations. How is this done in efficient implementations?

Thank you!

$\endgroup$
1
  • $\begingroup$ In LAPACK, this is step is done by the xTGEVC routines, see the docs. The essence is that using the Schur decomposition the problem is reduced to inverting a (singular) triangular system for each eigenvalue, which can be done with $O(n^2)$ operations. $\endgroup$
    – James
    Apr 24, 2022 at 19:53

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.