Householder Tridiagonalization as Preprocessing for the Jacobi Eigenvalue Algorithm

Householder tridiagonalization is normally not used as preprocessing for the Jacobi eigenvalue algorithm because it costs O(n³) and subsequent Jacobi rotations gradually destroy the tridiagonal zeros. We show that this does not determine whether preprocessing is beneficial. Algebraically, Householder tridiagonalization concentrates all off-diagonal energy into the first off-diagonal band while also redistributing energy between the diagonal and off-diagonal parts of the matrix. This leads to favorable and unfavorable regimes related to diagonal spread. Experiments with NVIDIA cuSOLVER on six families of dense symmetric matrices show that Householder preprocessing reduced Jacobi sweep counts in five commonly encountered families and, for matrices larger than 32×32, reduced total runtime even after including the cost of tridiagonalization. Across these five families and matrix sizes from 64×64 to 1024×1024, the reduction in total runtime ranged from 1.2% to 49.0%. An unequal-variance covariance family provides the contrasting case that is less common in practice, since variables on very different scales are often standardized before analysis. In this case, preprocessing moves substantial energy off the diagonal and increases Jacobi work. The results suggest diagonal spread as an inexpensive indicator of when Householder preprocessing may be unfavorable.