Direct Methods

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

where , where is a modestly growing polynomial function of .

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.