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=KrylovDefaults.verbosity[])

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. The default verbosity level verbosity amounts to printing warnings upon lack of convergence.

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,
        eager=false,
        verbosity=KrylovDefaults.verbosity[])

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. The default verbosity level verbosity amounts to printing warnings upon lack of convergence.

Use Lanczos for real symmetric or complex Hermitian linear operators.

See also: eigsolve, exponentiate, Lanczos, Orthogonalizer

CG(; maxiter=KrylovDefaults.maxiter[], tol=KrylovDefaults.tol[], verbosity=KrylovDefaults.verbosity[])

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. The default verbosity level verbosity amounts to printing warnings upon lack of convergence.

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

MINRES(; maxiter=KrylovDefaults.maxiter[], tol=KrylovDefaults.tol[], verbosity=KrylovDefaults.verbosity[])

!!! 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`. The default verbosity level `verbosity` amounts to printing
warnings upon lack of convergence.

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

GMRES(; krylovdim=KrylovDefaults.krylovdim[],
        maxiter=KrylovDefaults.maxiter[],
        tol=KrylovDefaults.tol[], 
        orth::Orthogonalizer=KrylovDefaults.orth,
        verbosity=KrylovDefaults.verbosity[])

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. The default verbosity level verbosity amounts to printing warnings upon lack of convergence.

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, LSMR, MINRES

BiCG(; maxiter=KrylovDefaults.maxiter[], tol=KrylovDefaults.tol[], verbosity=KrylovDefaults.verbosity[])

!!! 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`. The default verbosity level `verbosity` amounts to printing warnings upon
lack of convergence.

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

BiCGStab(; maxiter=KrylovDefaults.maxiter[], tol=KrylovDefaults.tol[], verbosity=KrylovDefaults.verbosity[])

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`. The default verbosity level 
`verbosity` amounts to printing warnings upon lack of convergence.

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

LSMR(; krylovdim=1,
        maxiter=KrylovDefaults.maxiter[],
        tol=KrylovDefaults.tol[], 
        orth::Orthogonalizer=ModifiedGramSchmidt(),
        verbosity=KrylovDefaults.verbosity[])

Represents the LSMR algorithm, which minimizes $\|Ax - b\|^2 + \|λx\|^2$ in the Euclidean norm. If multiple solutions exists the minimum norm solution is returned. The method is based on the Golub-Kahan bidiagonalization process. It is algebraically equivalent to applying MINRES to the normal equations $(A^*A + λ^2I)x = A^*b$, but has better numerical properties, especially if $A$ is ill-conditioned.

The LSMR method will search for the optimal $x$ in a Krylov subspace of maximal size maxiter, or stop when $norm(A'*(A*x - b) + λ^2 * x) < tol$. The parameter krylovdim does in this case not indicate that a subspace of that size will be built, but represents the number of most recent vectors that will be kept to which the next vector will be reorthogonalized. The default verbosity level verbosity amounts to printing warnings upon lack of convergence.

See also: lssolve

GolubYe(; krylovdim=KrylovDefaults.krylovdim[],
        maxiter=KrylovDefaults.maxiter[],
        tol=KrylovDefaults.tol[],
        orth=KrylovDefaults.orth,
        eager=false,
        verbosity=KrylovDefaults.verbosity[])

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,
    eager=false,
    verbosity=KrylovDefaults.verbosity[])

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. The default verbosity level verbosity amounts to printing warnings upon lack of convergence.

See also: svdsolve, Orthogonalizer

module KrylovDefaults
    const orth = KrylovKit.ModifiedGramSchmidtIR()
    const krylovdim = Ref(30)
    const maxiter = Ref(100)
    const tol = Ref(1e-12)
    const verbosity = Ref(KrylovKit.WARN_LEVEL)
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.