Krylov Subspace

• categories: Linear algebra, Definition

Definition

The Krylov subspace is a sequence of subspaces generated by repeatedly applying a matrix to a vector. Given a matrix $A\in {\mathbb{R}}^{n\times n}$ (or ${\mathbb{C}}^{n\times n}$) and an initial vector $\mathbf{b}\in {\mathbb{R}}^n$, the Krylov subspace of dimension $k$ is defined as:

$${\mathcal{K}}_k(A,\mathbf{b})=\text{span}\{\mathbf{b},A\mathbf{b},A^2\mathbf{b},\dots ,A^{k-1}\mathbf{b}\}.$$

Key Points

1. Dimensionality:
   The dimension of ${\mathcal{K}}_k(A,\mathbf{b})$ is at most $k$, but it may be smaller if the vectors $\{\mathbf{b},A\mathbf{b},\dots ,A^{k-1}\mathbf{b}\}$ are linearly dependent.

2. Purpose:
   Krylov subspaces are used to approximate solutions to large-scale Linear Systems, eigenvalue problems, and other matrix computations without directly working with the full matrix.

3. Orthogonal Basis:
   Algorithms like Arnoldi iteration and Lanczos process construct orthonormal bases for ${\mathcal{K}}_k(A,\mathbf{b})$ to facilitate numerical computations.

---

Applications

1. Solving Linear Systems:
   Iterative methods such as GMRES and CG (for symmetric positive definite matrices) operate within the Krylov subspace to approximate the solution of $A\mathbf{x}=\mathbf{b}$.

2. Eigenvalue Problems:
   Krylov subspace methods, such as Arnoldi iteration and Lanczos algorithm, are used to find a few dominant Eigenvalues and eigenvectors of $A$.

3. Model Order Reduction:
   Krylov subspaces are used to approximate dynamical systems in control theory.

---

Example

Matrix:

Let $A=\left[\begin{array}{cc}4& 1\\ 1& 3\end{array}\right]$ and $\mathbf{b}=\left[\begin{array}{c}1\\ 0\end{array}\right]$.

Krylov Subspaces:

• ${\mathcal{K}}_1(A,\mathbf{b})=\text{span}\{\mathbf{b}\}=\text{span}\{\left[\begin{array}{c}1\\ 0\end{array}\right]\}$.
• ${\mathcal{K}}_2(A,\mathbf{b})=\text{span}\{\mathbf{b},A\mathbf{b}\}$: $$A\mathbf{b}=\left[\begin{array}{cc}4& 1\\ 1& 3\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{c}4\\ 1\end{array}\right].$$ Thus: $${\mathcal{K}}_2(A,\mathbf{b})=\text{span}\{\left[\begin{array}{c}1\\ 0\end{array}\right],\left[\begin{array}{c}4\\ 1\end{array}\right]\}.$$

By normalizing and orthogonalizing these vectors (e.g., using Arnoldi iteration), we can form an orthonormal basis for ${\mathcal{K}}_2(A,\mathbf{b})$.

---

Key Algorithms

1. Arnoldi iteration:
   Generates an orthonormal basis for ${\mathcal{K}}_k(A,\mathbf{b})$ and produces an upper Hessenberg Matrix representation of $A$.

2. Lanczos Algorithm:
   A specialized version of Arnoldi for symmetric matrices, producing a tridiagonal matrix representation.

---

Visualization

If $\mathbf{b}$ is a vector in ${\mathbb{R}}^n$, the Krylov subspace ${\mathcal{K}}_k(A,\mathbf{b})$ can be thought of as the space spanned by applying $A$ repeatedly to $\mathbf{b}$ and observing how the vector evolves within ${\mathbb{R}}^n$. This sequence encapsulates the dominant behavior of $A$ with respect to $\mathbf{b}$.