Householder Tridiagonalization as Preprocessing for the Jacobi Eigenvalue Algorithm

Abstract

Householder tridiagonalization is not normally used before a Jacobi eigensolver because the reduction costs O(n³), while subsequent Jacobi rotations do not preserve the zeros it creates. We show that this argument does not settle whether preprocessing can nevertheless reduce the total computation. After tridiagonalization, all off-diagonal energy lies in the first off-diagonal band, and the standard first Jacobi set covers approximately half of those positions. Tridiagonalization can also move energy either toward or away from the diagonal. We derive an exact upper bound on the possible unfavorable diagonal-energy loss in terms of the initial diagonal standard deviation, giving an O(n) diagnostic available before preprocessing. We test the approach with NVIDIA cuSOLVER on six families of dense symmetric matrices, for n = 16 through 1024, on three NVIDIA GPUs. For the five ordinary matrix families, the complete eigenvalue-only preprocessing pipeline had lower mean runtime than standalone Jacobi from n = 32 onward on both GeForce processors and from n = 128 on the A100. Averaged across those families, the runtime reduction ranged from 7.5% to 10.0% at n = 128 and from 20.8% to 31.6% at n = 1024. Clustered-spectrum matrices benefited most, with runtime reduction reaching 49%. The unequal variance-covariance stress test remained unfavorable on all three GPUs and had by far the largest initial diagonal spread. A separate eigenvector experiment showed the same family-level separation, while a deterministic substitution of the second Jacobi set produced a modest additional reduction in sweep count.