The primary direct method
used in practice to solve the
NHEP (7.1) (and (7.2)) is
the QR algorithm. It first
computes the Schur canonical form (or simply called Schur decomposition)
of a non-Hermitian matrix
:
The QR algorithm is originated from the simple QR iteration:
Let,
For![]()
QR-factorize![]()
Compute![]()
Under certain conditions, converges to Schur
form
. However, the convergence of the QR iteration is extremely
slow for practical usage. To make QR iteration a fast, effective
method for computing Schur decomposition, a number of crucial
improvements have been developed, including Hessenberg reduction,
implicitly shifting, deflation, and matrix balancing.
We refer the interested reader to
[198,114] and references therein for the details
of the related theory and implementations.
The QR algorithm costs floating point operations and
memory for a general
matrix. A crude estimate for the costs
for a real
matrix is
floating point operations if both
and
are computed.
If only eigenvalues are desired, then about
floating point operations are necessary.
The QR algorithm is backward stable;
i.e.,
for the computed unitary matrix (within machine precision)
and the computed upper triangular matrix
, we have
The subroutine that implements the QR algorithm is
available in almost every
linear algebra-related software package.
It is used as the eig command in
MATLAB.In LAPACK [12],
the following driver routines are available for performing
a variant of tasks for computing Schur decompositions, eigenvalues,
eigenvectors, and estimates for the accuracy of computed results:
xGEES | compute Schur decomposition with eigenvalue ordering, |
xGEESX | xGEES plus condition estimates, |
xGEEV | eigenvalues and eigenvectors, |
xGEEVX | xGEEVX plus condition estimates, |
In ScaLAPACK [52], computational routines are provided for solving the parallel Hessenberg reduction and the parallel QR iteration with implicit shifting. They are PxGEHRD and PxLAHQR, respectively.