Available algorithms

abstract type Orthogonalizer

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

See also: ClassicalGramSchmidt, ModifiedGramSchmidt, ClassicalGramSchmidt2, ModifiedGramSchmidt2, ClassicalGramSchmidtIR, ModifiedGramSchmidtIR.

ClassicalGramSchmidt()

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

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.

ClassicalGramSchmidt2()

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

ModifiedGramSchmidt2()

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

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.

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.

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

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

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.

See also: linsolve, MINRES, GMRES, BiCG, BiCGStab

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.

See also: linsolve, CG, GMRES, BiCG, BiCGStab

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.

See also: linsolve, BiCG, BiCGStab, CG, MINRES

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.

See also: linsolve, GMRES, CG, BiCGStab, MINRES

BiCGStab(; maxiter = KrylovDefaults.maxiter, tol = KrylovDefaults.tol)

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.

See also: linsolve, GMRES, CG, BiCG, MINRES

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.

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

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.