Krylov.jl documentation

This package provides implementations of certain of the most useful Krylov method for a variety of problems:

1 - Square or rectangular full-rank systems

\[ Ax = b\]

should be solved when b lies in the range space of A. This situation occurs when

A is square and nonsingular,
A is tall and has full column rank and b lies in the range of A.

2 - Linear least-squares problems

\[ \min \|b - Ax\|\]

should be solved when b is not in the range of A (inconsistent systems), regardless of the shape and rank of A. This situation mainly occurs when

A is square and singular,
A is tall and thin.

Underdetermined sytems are less common but also occur.

If there are infinitely many such x (because A is column rank-deficient), one with minimum norm is identified

\[ \min \|x\| \quad \text{subject to} \quad x \in \argmin \|b - Ax\|.\]

3 - Linear least-norm problems

\[ \min \|x\| \quad \text{subject to} \quad Ax = b\]

sould be solved when A is column rank-deficient but b is in the range of A (consistent systems), regardless of the shape of A. This situation mainly occurs when

A is square and singular,
A is short and wide.

Overdetermined sytems are less common but also occur.

4 - Adjoint systems

\[ Ax = b \quad \text{and} \quad A^T y = c\]

where A can have any shape.

5 - Saddle-point or symmetric quasi-definite (SQD) systems

\[ \begin{bmatrix} M & \phantom{-}A \\ A^T & -N \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \left(\begin{bmatrix} b \\ 0 \end{bmatrix},\begin{bmatrix} 0 \\ c \end{bmatrix},\begin{bmatrix} b \\ c \end{bmatrix}\right)\]

where A can have any shape.

Krylov solvers are particularly appropriate in situations where such problems must be solved but a factorization is not possible, either because:

A is not available explicitly,
A would be dense or would consume an excessive amount of memory if it were materialized,
factors would consume an excessive amount of memory.

Iterative methods are recommended in either of the following situations:

the problem is sufficiently large that a factorization is not feasible or would be slow,
an effective preconditioner is known in cases where the problem has unfavorable spectral structure,
the operator can be represented efficiently as a sparse matrix,
the operator is fast, i.e., can be applied with better complexity than if it were materialized as a matrix. Certain fast operators would materialize as dense matrices.

How to Install

Krylov can be installed and tested through the Julia package manager:

julia> ]
pkg> add Krylov
pkg> test Krylov