Unit10.4.5The Method of Multiple Relatively Robust Representations (MRRR)

The Method of Multiple Relative Robust Representations (MRRR) computes the eigenvalues and eigenvectors of a $m \times m$ tridiagonal matrix in $O( m^2 )$ time. It can be argued that this is within a constant factor of the lower bound for computing these eigenvectors since the eigenvectors constitute $O( m^2 )$ data that must be written upon the completion of the computation.

When computing the eigenvalues and eigenvectors of a dense Hermitian matrix, MRRR can replace the implicitly shifted QR algorithm for finding the eigenvalues and eigenvectors of the tridiagonal matrix. The overall steps then become

• Reduce matrix $A$ to tridiagonal form:

\begin{equation*} A \rightarrow Q_A T Q_A^H \end{equation*}

where $T$ is a tridiagonal real valued matrix. The matrix $Q_A$ is not explicitly formed but instead the Householder vectors that were computed as part of the reduction to tridiagonal form are stored.

• Compute the eigenvalues and eigenvectors of the tridiagonal matrix $T \text{:}$

\begin{equation*} T \rightarrow Q_T D Q_T^T. \end{equation*}
• "Back transform" the eigenvectors by forming $Q_A Q_T$ (applying the Householder transformations that define $Q_A$ to $Q_T$).

The details of that method go beyond the scope of this note. We refer the interested reader to

• [12] Inderjit S. Dhillon and Beresford N. Parlett, Multiple Representations to Compute Orthogonal Eigenvectors of Symmetric Tridiagonal Matrices, Lin. Alg. Appl., Vol. 387, 2004.

• [3] Paolo Bientinesi, Inderjit S. Dhillon, Robert A. van de Geijn, A Parallel Eigensolver for Dense Symmetric Matrices Based on Multiple Relatively Robust Representations, SIAM Journal on Scientific Computing, 2005

Remark10.4.5.1.

An important feature of MRRR is that it can be used to find a subset of eigenvectors. This is in contrast to the QR algorithm, which computes all eigenvectors.