lanczos.cpp File Reference

Lanczos algorithm with full reorthogonalisation. More...

#include "linalg/eigen/lanczos.hpp"
#include "kernel/subspace.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_j alpha_j = v_j^T * w w = w - alpha_j*v_j - beta_{j-1}*v_{j-1} [reorthogonalise w against all previous v_1..v_j] beta_j = ||w|| v_{j+1} = w / beta_j

This builds the symmetric tridiagonal T_k = V_k^T * A * V_k with diagonal alpha and off-diagonal beta. The Ritz values are the eigenvalues of T_k and the Ritz vectors are V_k * (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.