lanczos.cpp File Reference

Lanczos algorithm with full reorthogonalisation. More...

#include "linalg/eigen/lanczos.hpp"
#include "linalg/eigen/jacobi_eig.hpp"
#include <cmath>
#include <stdexcept>
#include <algorithm>

Go to the source code of this file.

Namespaces
namespace	num

Functions
LanczosResult	num::lanczos (MatVecFn matvec, idx n, idx k, real tol=1e-10, idx max_steps=0, Backend backend=Backend::seq)
	Lanczos eigensolver for large sparse symmetric matrices.

Detailed Description

Lanczos algorithm with full reorthogonalisation.

The k-step Lanczos recurrence:

beta_0 = 0, v_0 = 0 v_1 = random unit vector for j = 1..k: w = A*vⱼ alphaⱼ = vⱼᵀ*w w = w - alphaⱼ*vⱼ - betaⱼ₋_1*vⱼ₋_1 [reorthogonalise w against all previous v_1..vⱼ] betaⱼ = ||w|| vⱼ₊_1 = w / betaⱼ

This builds the symmetric tridiagonal T_k = Vₖᵀ A Vₖ with diagonal alpha and off-diagonal beta. The Ritz values are the eigenvalues of T_k and the Ritz vectors are Vₖ * (eigenvectors of T_k).

T_k is diagonalised with eig_sym (Jacobi), which is O(k^3) – cheap for k << n.

Definition in file lanczos.cpp.