Lanczos tridiagonalization algorithm in Julia?

Do you have a dense or sparse matrix? How big?

If you have a huge sparse matrix (or some other huge matrix represented implicitly somehow), then it doesn’t make sense to compute the whole unitary matrix V, because this is a dense matrix that you wouldn’t be able to store, not to mention the cost is \Theta(n^3) in the matrix size n. Krylov iterative methods like Lanczos are designed in practice to compute only a part of the tridiagonalization, typically to span only a small number of extremal eigenvalues.

If you have a dense/moderate-size Hermitian matrix, on the other hand, and you want the unitary reduction to real-symmetric tridiagonal form, then what you want is called the “Hessenberg factorization” and there are better algorithms than Lanczos, typically using Householder reflectors. In Julia, you can call hessenberg(Hermitian(A)) in the LinearAlgebra standard library, which uses the underlying LAPACK routines for this factorization.

(What is your application, by the way?)

4 Likes