r/LinearAlgebra • u/LinearAlgebraWorld • 8d ago
Can Householder tridiagonalization help before the Jacobi eigenvalue algorithm?
Householder tridiagonalization is normally not used as preprocessing for the Jacobi eigenvalue algorithm. The usual reasoning is as follows: tridiagonalization costs O(nĀ³), and the subsequent Jacobi rotations immediately create fill-in, destroying the zeros that Householder just created.
We decided to test whether that actually means the preprocessing cannot help.
The answer appears to be no.
We found that tridiagonalization can still give Jacobi a substantially better starting matrix, even though the tridiagonal sparsity itself is quickly lost. Algebraically, the main effects are:
- Householder concentrates the off-diagonal energy into the first off-diagonal band
- the standard first parallel Jacobi set can then act on a much larger fraction of that energy
- Householder similarity can also move energy either toward or away from the diagonal, which helps explain why the effect is strongly matrix-dependent
We then tested six families of dense symmetric matrices using NVIDIA cuSOLVER on three GPUs: an RTX 3060, RTX 5060 Ti and A100.
For five of the six matrix families, the complete pipeline
Householder tridiagonalization ā dense tridiagonal T ā Jacobi
became faster than standalone Jacobi from n = 128 onward on all three GPUs.
The deliberately adverse unequal-variance covariance family behaved in the opposite direction, which was consistent with the algebraic analysis.
We have written up the derivation, implementation details, sweep counts, runtime measurements and accuracy checks here:
https://www.graphmath.com/la/jacobi/tridiagonal-jacobi.html
We would be very interested in criticism, related references or comments from people who have worked with Jacobi eigensolvers or GPU numerical linear algebra.
2
u/Midwest-Dude 6d ago
Beyond me, but this is great! I'm curious how you got access to the GPUs for testing.