# Available algorithms

## Orthogonalization algorithms

`KrylovKit.Orthogonalizer`

— Type`abstract type Orthogonalizer`

Supertype of a hierarchy for representing different orthogonalization strategies or algorithms.

See also: `ClassicalGramSchmidt`

, `ModifiedGramSchmidt`

, `ClassicalGramSchmidt2`

, `ModifiedGramSchmidt2`

, `ClassicalGramSchmidtIR`

, `ModifiedGramSchmidtIR`

.

`KrylovKit.ClassicalGramSchmidt`

— Type`ClassicalGramSchmidt()`

Represents the classical Gram Schmidt algorithm for orthogonalizing different vectors, typically not an optimal choice.

`KrylovKit.ModifiedGramSchmidt`

— Type`ModifiedGramSchmidt()`

Represents the modified Gram Schmidt algorithm for orthogonalizing different vectors, typically a reasonable choice for linear systems but not for eigenvalue solvers with a large Krylov dimension.

`KrylovKit.ClassicalGramSchmidt2`

— Type`ClassicalGramSchmidt2()`

Represents the classical Gram Schmidt algorithm with a second reorthogonalization step always taking place.

`KrylovKit.ModifiedGramSchmidt2`

— Type`ModifiedGramSchmidt2()`

Represents the modified Gram Schmidt algorithm with a second reorthogonalization step always taking place.

`KrylovKit.ClassicalGramSchmidtIR`

— Type`ClassicalGramSchmidtIR(η::Real = 1/sqrt(2))`

Represents the classical Gram Schmidt algorithm with iterative (i.e. zero or more) reorthogonalization until the norm of the vector after an orthogonalization step has not decreased by a factor smaller than `η`

with respect to the norm before the step. The default value corresponds to the Daniel-Gragg-Kaufman-Stewart condition.

`KrylovKit.ModifiedGramSchmidtIR`

— Type`ModifiedGramSchmidtIR(η::Real = 1/sqrt(2))`

Represents the modified Gram Schmidt algorithm with iterative (i.e. zero or more) reorthogonalization until the norm of the vector after an orthogonalization step has not decreased by a factor smaller than `η`

with respect to the norm before the step. The default value corresponds to the Daniel-Gragg-Kaufman-Stewart condition.

## General Krylov algorithms

`KrylovKit.Lanczos`

— Type```
Lanczos(; krylovdim = KrylovDefaults.krylovdim, maxiter = KrylovDefaults.maxiter,
tol = KrylovDefaults.tol, orth = KrylovDefaults.orth, eager = false, verbosity = 0)
```

Represents the Lanczos algorithm for building the Krylov subspace; assumes the linear operator is real symmetric or complex Hermitian. Can be used in `eigsolve`

and `exponentiate`

. The corresponding algorithms will build a Krylov subspace of size at most `krylovdim`

, which will be repeated at most `maxiter`

times and will stop when the norm of the residual of the Lanczos factorization is smaller than `tol`

. The orthogonalizer `orth`

will be used to orthogonalize the different Krylov vectors. Eager mode, as selected by `eager = true`

, means that the algorithm that uses this Lanczos process (e.g. `eigsolve`

) can try to finish its computation before the total Krylov subspace of dimension `krylovdim`

is constructed. Default verbosity level `verbosity`

is zero, meaning that no output will be printed.

Use `Arnoldi`

for non-symmetric or non-Hermitian linear operators.

See also: `factorize`

, `eigsolve`

, `exponentiate`

, `Arnoldi`

, `Orthogonalizer`

`KrylovKit.Arnoldi`

— Type```
Arnoldi(; krylovdim = KrylovDefaults.krylovdim, maxiter = KrylovDefaults.maxiter,
tol = KrylovDefaults.tol, orth = KrylovDefaults.orth, verbosity = 0)
```

Represents the Arnoldi algorithm for building the Krylov subspace for a general matrix or linear operator. Can be used in `eigsolve`

and `exponentiate`

. The corresponding algorithms will build a Krylov subspace of size at most `krylovdim`

, which will be repeated at most `maxiter`

times and will stop when the norm of the residual of the Arnoldi factorization is smaller than `tol`

. The orthogonalizer `orth`

will be used to orthogonalize the different Krylov vectors. Eager mode, as selected by `eager = true`

, means that the algorithm that uses this Arnoldi process (e.g. `eigsolve`

) can try to finish its computation before the total Krylov subspace of dimension `krylovdim`

is constructed. Default verbosity level `verbosity`

is zero, meaning that no output will be printed.

Use `Lanczos`

for real symmetric or complex Hermitian linear operators.

See also: `eigsolve`

, `exponentiate`

, `Lanczos`

, `Orthogonalizer`

## Specific algorithms for linear systems

`KrylovKit.CG`

— Type`CG(; maxiter = KrylovDefaults.maxiter, tol = KrylovDefaults.tol)`

Construct an instance of the conjugate gradient algorithm with specified parameters, which can be passed to `linsolve`

in order to iteratively solve a linear system with a positive definite (and thus symmetric or hermitian) coefficient matrix or operator. The `CG`

method will search for the optimal `x`

in a Krylov subspace of maximal size `maxiter`

, or stop when `norm(A*x - b) < tol`

. Default verbosity level `verbosity`

is zero, meaning that no output will be printed.

`KrylovKit.MINRES`

— Type```
MINRES(; maxiter = KrylovDefaults.maxiter, tol = KrylovDefaults.tol)
!!! warning "Not implemented yet"
Construct an instance of the conjugate gradient algorithm with specified parameters,
which can be passed to `linsolve` in order to iteratively solve a linear system with a
real symmetric or complex hermitian coefficient matrix or operator. The `MINRES` method
will search for the optimal `x` in a Krylov subspace of maximal size `maxiter`, or stop
when `norm(A*x - b) < tol`. In building the Krylov subspace, `MINRES` will use the
orthogonalizer `orth`. Default verbosity level `verbosity` is zero, meaning that no
output will be printed.
```

`KrylovKit.GMRES`

— Type```
GMRES(; krylovdim = KrylovDefaults.krylovdim, maxiter = KrylovDefaults.maxiter,
tol = KrylovDefaults.tol, orth::Orthogonalizer = KrylovDefaults.orth)
```

Construct an instance of the GMRES algorithm with specified parameters, which can be passed to `linsolve`

in order to iteratively solve a linear system. The `GMRES`

method will search for the optimal `x`

in a Krylov subspace of maximal size `krylovdim`

, and repeat this process for at most `maxiter`

times, or stop when `norm(A*x - b) < tol`

. In building the Krylov subspace, `GMRES`

will use the orthogonalizer `orth`

. Default verbosity level `verbosity`

is zero, meaning that no output will be printed.

Note that in the traditional nomenclature of `GMRES`

, the parameter `krylovdim`

is referred to as the restart parameter, and `maxiter`

is the number of outer iterations, i.e. restart cycles. The total iteration count, i.e. the number of expansion steps, is roughly `krylovdim`

times the number of iterations.

`KrylovKit.BiCG`

— Type```
BiCG(; maxiter = KrylovDefaults.maxiter, tol = KrylovDefaults.tol)
!!! warning "Not implemented yet"
Construct an instance of the Biconjugate gradient algorithm with specified parameters,
which can be passed to `linsolve` in order to iteratively solve a linear system general
linear map, of which the adjoint can also be applied. The `BiCG` method will search for
the optimal `x` in a Krylov subspace of maximal size `maxiter`, or stop when `norm(A*x -
b) < tol`. Default verbosity level `verbosity` is zero, meaning that no output will be
printed.
```

`KrylovKit.BiCGStab`

— Type```
BiCGStab(; maxiter = KrylovDefaults.maxiter, tol = KrylovDefaults.tol)
!!! warning "Not implemented yet"
Construct an instance of the Biconjugate gradient algorithm with specified parameters,
which can be passed to `linsolve` in order to iteratively solve a linear system general
linear map. The `BiCGStab` method will search for the optimal `x` in a Krylov subspace
of maximal size `maxiter`, or stop when `norm(A*x - b) < tol`. Default verbosity level
`verbosity` is zero, meaning that no output will be printed.
```

## Specific algorithms for generalized eigenvalue problems

`KrylovKit.GolubYe`

— Type```
GolubYe(; krylovdim = KrylovDefaults.krylovdim, maxiter = KrylovDefaults.maxiter,
tol = KrylovDefaults.tol, orth = KrylovDefaults.orth, verbosity = 0)
```

Represents the Golub-Ye algorithm for solving hermitian (symmetric) generalized eigenvalue problems `A x = λ B x`

with positive definite `B`

, without the need for inverting `B`

. Builds a Krylov subspace of size `krylovdim`

starting from an estimate `x`

by acting with `(A - ρ(x) B)`

, where `ρ(x) = dot(x, A*x)/dot(x, B*x)`

, and employing the Lanczos algorithm. This process is repeated at most `maxiter`

times. In every iteration `k>1`

, the subspace will also be expanded to size `krylovdim+1`

by adding $x_k - x_{k-1}$, which is known as the LOPCG correction and was suggested by Money and Ye. With `krylovdim = 2`

, this algorithm becomes equivalent to `LOPCG`

.

## Specific algorithms for singular value problems

`KrylovKit.GKL`

— Type```
GKL(; krylovdim = KrylovDefaults.krylovdim, maxiter = KrylovDefaults.maxiter,
tol = KrylovDefaults.tol, orth = KrylovDefaults.orth, verbosity = 0)
```

Represents the Golub-Kahan-Lanczos bidiagonalization algorithm for sequentially building a Krylov-like factorization of a general matrix or linear operator with a bidiagonal reduced matrix. Can be used in `svdsolve`

. The corresponding algorithm builds a Krylov subspace of size at most `krylovdim`

, which will be repeated at most `maxiter`

times and will stop when the norm of the residual of the Arnoldi factorization is smaller than `tol`

. The orthogonalizer `orth`

will be used to orthogonalize the different Krylov vectors. Default verbosity level `verbosity`

is zero, meaning that no output will be printed.

See also: `svdsolve`

, `Orthogonalizer`

## Default values

`KrylovKit.KrylovDefaults`

— Module```
module KrylovDefaults
const orth = KrylovKit.ModifiedGramSchmidtIR()
const krylovdim = 30
const maxiter = 100
const tol = 1e-12
end
```

A module listing the default values for the typical parameters in Krylov based algorithms:

`orth = ModifiedGramSchmidtIR()`

: the orthogonalization routine used to orthogonalize the Krylov basis in the`Lanczos`

or`Arnoldi`

iteration`krylovdim = 30`

: the maximal dimension of the Krylov subspace that will be constructed`maxiter = 100`

: the maximal number of outer iterations, i.e. the maximum number of times the Krylov subspace may be rebuilt`tol = 1e-12`

: the tolerance to which the problem must be solved, based on a suitable error measure, e.g. the norm of some residual.

The default value of `tol`

is a `Float64`

value, if you solve problems in `Float32`

or `ComplexF32`

arithmetic, you should always specify a new `tol`

as the default value will not be attainable.