## 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

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

•  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.