Skip to main content

Unit 10.4.3 Casting the reduction to tridiagonal form in terms of matrix-matrix multiplication

For many algorithms, we have discussed blocked versions that cast more computation in terms of matrix-matrix multiplication, thus achieving portable high performance (when linked to a high-performance implementation of matrix-matrix multiplication). The inconvenient truth is that reduction to tridiagonal form can only be partially cast in terms of matrix-matrix multiplication. This is a severe hindrance to high performance for that first step towards computing all eigenvalues and eigenvector of a Hermitian matrix. Worse, a considerable fraction of the total cost of the computation is in that first step.

For a detailed discussion on the blocked algorithm for reduction to tridiagonal form, we recommend

  • [45] Field G. Van Zee, Robert A. van de Geijn, Gregorio Quintana-Ortí, G. Joseph Elizondo, Families of Algorithms for Reducing a Matrix to Condensed Form, ACM Transactions on Mathematical Software (TOMS) , Vol. 39, No. 1, 2012.

Tridiagonal form is one case of what is more generally referred to as "condensed form."