Advanced Linear Algebra: Foundations to Frontiers

Subsection 10.4.5 The 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