June 1, 2023

# What is Krylov subspace? Krylov subspace is a powerful mathematical tool that has applications in a wide range of fields, including computational mathematics, engineering, and physics. Understanding Krylov subspace can help you understand and solve problems ranging from linear systems of equations to optimization problems. In this article, we will explore Krylov subspace in detail, including its definition, mathematical foundations, key properties, and applications.

## Understanding Krylov Subspace

### Definition and Basics

Krylov subspace is a subspace of a given vector space that is generated by multiplying a given vector by the matrix of a linear transformation and its successive powers. This means that the Krylov subspace of a matrix A and a vector b is a linear space spanned by the vectors:

1. b
2. Ab
3. A2b
4. A3b
5. ...
6. Am-1b

where m is the dimension of the vector space. Krylov subspace can be used as a basis for solving different problems, including linear systems of equations, eigenvalue problems, and optimization problems.

### Mathematical Foundations

The mathematical foundations of Krylov subspace are based on linear algebra and matrix theory. Given a square matrix A and a vector b, which represents the initial guess of a solution, we can apply the power iteration method to generate a sequence of Krylov subspaces.

The power iteration method involves multiplying the vector by the matrix, normalizing it, and repeating the process until convergence. The result of this process is a sequence of vectors that span the Krylov subspace. This subspace can be used as a starting point for solving different problems.

### Key Properties

One of the key properties of Krylov subspace is its computational efficiency, especially for large-scale problems. The method requires only matrix-vector products, which can be computed efficiently using parallel computing techniques. Additionally, Krylov subspace methods typically converge quickly, making them suitable for iterative methods.

Another important property of Krylov subspace is that the sequence of vectors generated by the power iteration method is orthogonalized relative to the given matrix. This orthogonality is exploited in many Krylov subspace methods, such as the conjugate gradient method.

## Applications of Krylov Subspace

Krylov subspace is a powerful tool that finds applications in various scientific and engineering fields. It is a mathematical concept that involves constructing a subspace of a given vector space by taking linear combinations of powers of a given matrix and a given vector. This technique has proved to be useful in solving a range of problems, including linear systems of equations, eigenvalue problems, model reduction, and optimization problems.

### Linear Systems of Equations

Linear systems of equations arise in many scientific and engineering applications, such as image processing, signal processing, and computational fluid dynamics. Krylov subspace methods can be used to solve large-scale linear systems of equations efficiently and accurately. One of the most popular Krylov subspace methods for solving linear systems of equations is the conjugate gradient method. This method is based on the idea of minimizing the residual error in the Krylov subspace. It is an iterative method that converges quickly and is suitable for solving large and sparse linear systems of equations.

### Eigenvalue Problems

Eigenvalue problems arise in many scientific and engineering applications, including quantum mechanics and structural analysis. Krylov subspace methods can be used to compute the eigenvectors and eigenvalues of a matrix efficiently and accurately. One of the most popular Krylov subspace methods for solving eigenvalue problems is the Lanczos algorithm. This algorithm is based on the idea of constructing an orthogonal basis for the Krylov subspace and computing the eigenvalues of a small tridiagonal matrix. The Lanczos algorithm is suitable for solving large and sparse eigenvalue problems.

### Model Reduction

Model reduction is an important problem in numerical simulation and control. It involves constructing a low-dimensional approximation of a high-dimensional system that captures its essential behavior. Krylov subspace methods can be used to construct the low-dimensional approximation by projecting the original system onto a Krylov subspace with a small dimension. One of the most popular Krylov subspace methods for model reduction is the Arnoldi method. This method is based on the idea of constructing an orthogonal basis for the Krylov subspace and computing the dominant eigenvalues and eigenvectors of a small upper Hessenberg matrix. The Arnoldi method is suitable for reducing the order of large and sparse linear systems and dynamical systems.

### Optimization Problems

Optimization problems arise in many scientific and engineering applications, including machine learning and data analysis. Krylov subspace methods can be used to solve large-scale optimization problems efficiently and accurately. One of the most popular Krylov subspace methods for optimization problems is the generalized minimal residual method (GMRES). This method is based on the idea of minimizing the residual error in the Krylov subspace. It is an iterative method that converges quickly and is suitable for solving large and sparse optimization problems.

## Krylov Subspace Methods

Krylov subspace methods are a class of iterative methods that can be used to solve large-scale linear systems of equations and eigenvalue problems. These methods are based on the idea of constructing a subspace of the vector space that is spanned by the powers of a given matrix. The Krylov subspace is defined as:

Km(A, b) = span{b, Ab, A2b, ..., Am-1b}

where A is a given matrix, b is a given vector, and m is the dimension of the Krylov subspace. The Krylov subspace methods aim to find a solution to the linear system of equations or eigenvalue problem by minimizing the residual error in the Krylov subspace.

The conjugate gradient method is a well-known Krylov subspace method for solving large-scale linear systems of equations. The method is based on the idea of minimizing the residual error in the Krylov subspace. The conjugate gradient method is particularly useful for solving symmetric and positive definite linear systems of equations.

The method uses orthogonalization and conjugation to generate a sequence of orthogonal vectors that span the Krylov subspace. The conjugate gradient method is known for its rapid convergence properties, making it a popular choice for iterative methods.

The conjugate gradient method can be used to solve a wide range of problems, including partial differential equations, optimization problems, and image processing problems.

### Generalized Minimal Residual Method (GMRES)

The generalized minimal residual method (GMRES) is a Krylov subspace method that can be used to solve linear systems of equations and optimization problems. The method works by minimizing the residual error in the Krylov subspace, and it is particularly useful for solving non-symmetric and ill-conditioned systems of equations.

GMRES uses Gram-Schmidt orthogonalization to generate a sequence of orthogonal vectors that span the Krylov subspace. It also uses Arnoldi's method to generate a Hessenberg matrix that can be used to compute the solution of the linear system of equations or optimization problem.

The GMRES method is known for its flexibility and robustness, making it a popular choice for a wide range of problems in scientific computing, such as fluid dynamics, electromagnetics, and structural mechanics.

### Bi-Conjugate Gradient Stabilized Method (BiCGSTAB)

The bi-conjugate gradient stabilized method (BiCGSTAB) is a Krylov subspace method that can be used to solve non-symmetric linear systems of equations. The method works by minimizing the residual error in a Krylov subspace that is obtained by applying two different matrices to the initial guess.

BiCGSTAB uses a combination of orthogonalization, conjugation, and stabilization to generate a sequence of vectors that span the Krylov subspace. It is known for its robustness and stability, making it a popular choice for iterative methods.

The BiCGSTAB method can be used to solve a wide range of problems in scientific computing, such as fluid dynamics, electromagnetics, and structural mechanics.

### Lanczos Algorithm

The Lanczos algorithm is a Krylov subspace method that can be used to compute the eigenvalues and eigenvectors of a large sparse matrix. The method works by constructing an orthogonal basis for the Krylov subspace using a recursive process that involves projecting the matrix onto the Krylov subspace.

The Lanczos algorithm is particularly useful for computing the eigenvalues and eigenvectors of a sparse matrix, as it exploits the sparsity of the matrix to reduce the computational cost. It is known for its reliability and stability, making it a popular choice for eigenvalue problems.

The Lanczos algorithm has many applications in scientific computing, such as quantum mechanics, signal processing, and finance.

## Advantages and Limitations of Krylov Subspace Methods

### Convergence Rates

Krylov subspace methods are a popular choice for iterative methods due to their rapid convergence rates, especially for large-scale problems. Compared to direct methods, such as Gaussian elimination, Krylov subspace methods typically converge more quickly. This makes them a popular choice for solving problems in a variety of fields, including physics, engineering, and computer science.

One reason for the rapid convergence rates of Krylov subspace methods is that they only require matrix-vector products, which can be computed efficiently. This allows for faster calculations and improved performance.

### Preconditioning Techniques

Another advantage of Krylov subspace methods is their flexibility in using different preconditioning techniques to accelerate convergence. Preconditioning techniques involve modifying the original matrix to improve its condition number and reduce the computational cost.

Preconditioning techniques can be used to improve the convergence rates of Krylov subspace methods for different problems, including linear systems of equations and eigenvalue problems. Some common preconditioning techniques include incomplete Cholesky factorization, incomplete LU factorization, and algebraic multigrid methods.

### Memory Requirements

One limitation of Krylov subspace methods is their memory requirements, especially for large-scale problems. Krylov subspace methods require storing the matrix-vector products, which can be computationally expensive and memory-intensive.

To address this limitation, Krylov subspace methods can be parallelized using distributed computing techniques or low-rank approximations. These techniques can reduce the memory requirements of Krylov subspace methods and improve their performance on large-scale problems.

### Parallelization and Scalability

Krylov subspace methods can be parallelized using distributed computing techniques to improve their scalability and performance on large-scale problems. Parallelization techniques involve dividing the problem into smaller subproblems that can be solved in parallel.

Parallelization techniques can improve the scalability and performance of Krylov subspace methods for different problems, including linear systems of equations and eigenvalue problems. Some common parallelization techniques include domain decomposition, multigrid methods, and parallel preconditioning.

Overall, Krylov subspace methods have many advantages, including rapid convergence rates, flexibility in using preconditioning techniques, and the ability to be parallelized for improved scalability and performance. However, they also have limitations, such as high memory requirements for large-scale problems. Researchers continue to explore new techniques and algorithms to improve the efficiency and performance of Krylov subspace methods for a variety of applications.

## Conclusion

Krylov subspace is a powerful mathematical tool that has applications in a wide range of fields, including computational mathematics, engineering, and physics. Understanding Krylov subspace can help you understand and solve problems ranging from linear systems of equations to optimization problems.

In this article, we explored Krylov subspace in detail, including its definition, mathematical foundations, key properties, applications, and methods. We also discussed the advantages and limitations of Krylov subspace methods, including their convergence rates, preconditioning techniques, memory requirements, parallelization, and scalability.