low_rank_toolbox.krylov.spaces.krylov_space

Standard Krylov subspace construction and operations.

Author: Benjamin Carrel, University of Geneva, 2022-2023

Classes

KrylovSpace(A, X, **extra_args)

Class for (block) Krylov spaces. The definition of a Krylov space of size $m$ is the following: K_m(A,x) = span{x, A x, A^2 x, ..., A^(m-1) x} where $A$ is a sparse matrix, and $x$ is a vector or a matrix.
class low_rank_toolbox.krylov.spaces.krylov_space.KrylovSpace(A, X, **extra_args)[source]

Bases: SpaceStructure

Class for (block) Krylov spaces. The definition of a Krylov space of size $m$ is the following:

K_m(A,x) = span{x, A x, A^2 x, …, A^(m-1) x}

where $A$ is a sparse matrix, and $x$ is a vector or a matrix.

Algorithm Selection: - If A is symmetric (is_symmetric=True): Uses Lanczos algorithm with 3-term recurrence

  • Stores tridiagonal coefficients (alpha, beta) in O(m) space

  • Orthogonalization cost: O(n*r) per iteration

  • If A is non-symmetric (is_symmetric=False): Uses Arnoldi algorithm with full orthogonalization - Stores upper Hessenberg matrix H in O(m²) space - Orthogonalization cost: O(n*m*r) per iteration

Performance: For symmetric problems, Lanczos is faster and uses significantly less memory than Arnoldi.

How to use

  1. Initialize the Krylov space with the matrix $A$ and the vector $x$.

  2. Augment the basis of the Krylov space as needed with the method augment_basis.

  3. The basis is stored in the attribute ‘basis’, or ‘Q’ for short.

A

Matrix of shape (n,n)

Type:

spmatrix

X

Vector of shape (n,1) or (n,r)

Type:

ndarray

m

Size of the Krylov space

Type:

int

is_symmetric

True if A is symmetric (uses Lanczos), False otherwise (uses Arnoldi)

Type:

bool

Q

Matrix of shape (n,m) or (n,m*r) containing the basis of the Krylov space

Type:

ndarray

basis

Pointer to Q

Type:

ndarray

_alpha

Lanczos diagonal coefficients

Type:

ndarray (symmetric only)

_beta

Lanczos off-diagonal coefficients

Type:

ndarray (symmetric only)

H

Upper Hessenberg matrix from Arnoldi

Type:

ndarray (non-symmetric only)

Examples

>>> import numpy as np
>>> from scipy.sparse import csr_matrix
>>> from low_rank_toolbox.krylov import KrylovSpace
>>> # Non-symmetric case (uses Arnoldi)
>>> A = csr_matrix([[1, 2, 0], [0, 3, 1], [1, 0, 2]])
>>> x = np.array([1.0, 0.0, 0.0])
>>> K = KrylovSpace(A, x, is_symmetric=False)
>>> K.augment_basis()  # Add next basis vector
>>> K.Q.shape
(3, 2)
>>> # Symmetric case (uses Lanczos - more efficient)
>>> A_sym = csr_matrix([[4, 1, 0], [1, 3, 1], [0, 1, 2]])
>>> K_sym = KrylovSpace(A_sym, x, is_symmetric=True)
>>> K_sym.augment_basis()
>>> K_sym.Q.shape
(3, 2)
__init__(A, X, **extra_args)[source]

Initialize a Krylov Space where X is a vector or a matrix

Parameters:

  • A (spmatrix) – Sparse matrix of shape (n,n)

  • X (ndarray) – Vector or matrix of shape (n,) or (n,r)

  • extra_args (dict) – Extra arguments

  • arguments (Extra)

  • ---------------

  • is_symmetric (bool) – True if A is symmetric (uses Lanczos), False otherwise (uses Arnoldi). Lanczos is much cheaper for symmetric problems.

  • matvec (callable) – Function for the matrix-vector product

Return type:

None

augment_basis()[source]

Augment the basis of the Krylov space.

Adds the next block of r basis vectors to the Krylov space using: - Lanczos algorithm if A is symmetric - Arnoldi algorithm if A is non-symmetric

The new basis vectors are computed as A * Q[:, (m-1)*r:m*r] and then orthogonalized against the existing basis.

Return type:

None

Notes

If the next basis would exceed the dimension of the matrix, a warning is issued and the method returns without modifying the basis.

property basis

The orthonormal basis of the Krylov space.

Returns:

Matrix of shape (n, m*r) containing the basis vectors.

Return type:

ndarray

property size

The size of the Krylov space.

Returns:

The number of basis vectors (m * r).

Return type:

int

Parameters:

  • A (spmatrix)

  • X (ndarray)