Band Lanczos

mutable struct BandLanczosFactorization{T, S<:Number, SR<:Real} <: KrylovFactorization{T, S}

Band Lanczos factorization of a real symmetric or complex hermitian linear map A, storing a partial factorization of the form

A * V = V * H + R * B'

where V is an orthonormal basis of the Krylov subspace, H is a block tridiagonal Rayleigh quotient matrix, R is the residual block, and B = [0; I] contains an identity matrix in the last kᵣ rows.

Compared to KrylovKit.BlockLanczosFactorization, which requires ModifiedGramSchmidt and always keeps the full basis, this factorization is compatible with both single-pass ModifiedGramSchmidt and ModifiedGramSchmidt2, and can drop old basis vectors to save memory (controlled by the iterator, not the factorization itself).

Fields

• k::Int: current dimension of the Krylov subspace (number of basis vectors).
• V::OrthonormalBasis{T}: orthonormal basis of the Krylov subspace.
• H::Matrix{S}: block tridiagonal Rayleigh quotient matrix, preallocated to maxdim × maxdim.
• R::Block{T}: residual block; only the first kᵣ vectors are valid.
• kᵣ::Int: number of vectors in the current residual block.
• normᵣ::SR: Frobenius norm of the residual block.

Interface

• length(fact) → fact.k
• basis(fact) → fact.V (requires keepvecs=true)
• rayleighquotient(fact) → fact.H[1:k, 1:k]
• residual(fact) → fact.R[1:kᵣ]
• normres(fact) → fact.normᵣ
• rayleighextension(fact) → [0; I] matrix of size (k, kᵣ)

See also: BandLanczosIterator, expand!, initialize.

struct BandLanczosIterator{F, T, S<:Real, SR<:Real, OR<:Orthogonalizer, OO<:Orthogonalizer} <: KrylovIterator{F, T}

Iterator that produces a progressively expanding BandLanczosFactorization of a real symmetric or complex hermitian linear map f with a starting block x₀.

Compared to KrylovKit.BlockLanczosIterator, which only supports ModifiedGramSchmidt and always keeps the full Krylov basis, this iterator:

• Supports both single-pass ModifiedGramSchmidt and ModifiedGramSchmidt2 for both the QR step and the reorthogonalization step, independently selectable.
• Supports optional basis truncation via keepvecs to save memory.
• Separates the Lanczos convergence tolerance (tol) from the QR rank-determination tolerance (tolᵣ), allowing fine-grained control over numerical behavior.

Fields

• operator::F: the linear map (function or matrix).
• x₀::Block{T}: initial block of vectors.
• maxdim::Int: maximum dimension of the Krylov subspace.
• tol::S: Lanczos convergence tolerance — iteration stops when normres < tol.
• tolᵣ::SR: QR rank-determination tolerance — a vector with norm < tolᵣ is considered numerically zero in block_qr!.
• keepvecs::Bool: whether to retain all basis vectors (if false, old vectors are dropped each iteration to save memory).
• orthᵣ::OR: Orthogonalizer used in block_qr! for rank determination of initial and residual blocks.
• orthₒ::OO: Orthogonalizer used in block_reorthogonalize! for reorthogonalization against the full Krylov basis during the Lanczos recurrence.

See also: BandLanczosFactorization, initialize, expand!.

band_lanczosrecurrence(operator, V::OrthonormalBasis, B::AbstractMatrix, orth::Orthogonalizer) -> (AX, M)

Perform one step of the band Lanczos recurrence.

Given the current orthonormal basis V, the QR factor B (of size bs × bsₚ), and an Orthogonalizer orth:

1. Apply the operator to the newest block X = V[end-bs+1:end].
2. Compute the Rayleigh quotient M = X' * A * X.
3. Subtract projections onto the current block X (via M) and the previous block Xₚ (via B) to form the next residual.
4. Reorthogonalize against the full Krylov basis via block_reorthogonalize! using orth.

Returns the new residual block AX and the Rayleigh quotient block M.

block_qr!(block::Block, tol::Real, orth::Orthogonalizer) -> (R, good_idx)

QR factorization of a block of vectors using the specified orthogonalizer.

• orth = ModifiedGramSchmidt(): single-pass Modified Gram-Schmidt (delegates to KrylovKit's standard block_qr!).
• orth = ModifiedGramSchmidt2(): Modified Gram-Schmidt with one reorthogonalization pass. Each vector is orthogonalized against all previous vectors twice, which significantly improves numerical orthogonality.

Returns the upper-triangular factor R (size r × n where r is the numerical rank) and a vector good_idx of indices of the linearly independent columns. Vectors whose norm after orthogonalization falls below tol are set to zero and excluded from good_idx.

block_reorthogonalize!(R::Block{T}, V::OrthonormalBasis{T}, orth::Orthogonalizer) where {T}

Reorthogonalize the vectors in R against the orthonormal basis V using the specified orthogonalizer.

For each vector R[i], projects out its components along every direction in V: R[i] = R[i] - Σⱼ ⟨R[i], V[j]⟩ V[j].

• orth = ModifiedGramSchmidt(): single-pass MGS (delegates to KrylovKit's standard block_reorthogonalize!).
• orth = ModifiedGramSchmidt2(): two-pass MGS, providing better orthogonality.

It is assumed that V is already orthonormal.

expand!(iter::BandLanczosIterator, state::BandLanczosFactorization) -> BandLanczosFactorization

Expand the band Lanczos factorization by one block step.

1. QR-decompose the residual block via block_qr!(R, iter.tolᵣ, iter.orthᵣ). If the residual is exhausted (bsₙ == 0), return the state unchanged.
2. Append the QR-orthonormalized residual to the basis.
3. Fill the off-diagonal blocks of H with the QR factor B.
4. Compute the next residual via band_lanczosrecurrence using iter.orthₒ.
5. Update the diagonal block of H with the Rayleigh quotient of the new basis vectors.
6. Update normᵣ and kᵣ.

initialize(iter::BandLanczosIterator) -> BandLanczosFactorization

Initialize the band Lanczos factorization from the starting block iter.x₀.

Performs a QR decomposition of the initial block via block_qr! (usingiter.tolᵣ and iter.orthᵣ), applies the operator to the orthonormalized block, computes the first block of the Rayleigh quotient, and constructs the initial residual.