Skip to main content

Subsection 10.4.4 Optimizing the tridiagonal QR algorithm

As the Givens' rotations are applied to the tridiagonal matrix, they are also applied to a matrix in which eigenvectors are accumulated. While one Implicit Francis Step requires \(O( n ) \) computation, this accumulation of the eigenvectors requires \(O( n^2 ) \) computation with \(O( n^2 ) \) data per step. We have learned before that this inherently means the cost of accessing data dominates on current architectures.

In a recent paper, we showed how accumulating the Givens' rotations for several Francis Steps allows one to attain performance similar to that attained by a matrix-matrix multiplication:

  • [28] Field G. Van Zee, Robert A. van de Geijn, Gregorio Quintana-Ortí, Restructuring the Tridiagonal and Bidiagonal QR Algorithms for Performance, ACM Transactions on Mathematical Software (TOMS), Vol. 40, No. 3, 2014.

For computing all eigenvalues and eigenvectors of a dense Hermitian matrix, this approach is competitive with the Method of Relatively Robust Representations, discussed in (((Unresolved xref, reference ""; check spelling or use "provisional" attribute))) .