Krylov.jl: A Julia basket of hand-picked Krylov methods

Documentation	CI	Coverage	DOI	Downloads

If you use Krylov.jl in your work, please cite it using the metadata given in CITATION.cff.

@article{montoison-orban-2023,
  author  = {Montoison, Alexis and Orban, Dominique},
  title   = {{Krylov.jl: A Julia basket of hand-picked Krylov methods}},
  journal = {Journal of Open Source Software},
  volume  = {8},
  number  = {89},
  pages   = {5187},
  year    = {2023},
  doi     = {10.21105/joss.05187}
}

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

minimize ‖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 systems 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

minimize ‖x‖   subject to   x ∈ argmin ‖b - Ax‖.

3. Linear least-norm problems

minimize ‖x‖   subject to   Ax = b

should 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 systems are less common but also occur.

4. Adjoint systems

Ax = b   and   Aᴴy = c

where A can have any shape.

5. Saddle-point and Hermitian quasi-definite systems

[M     A]  [x] = [b]
[Aᴴ   -N]  [y]    [c]

where A can have any shape.

6. Generalized saddle-point and non-Hermitian partitioned systems

[M   A]  [x] = [b]
[B   N]  [y]    [c]

where A can have any shape and B has the shape of Aᴴ. A, B, b and c must be all nonzero.

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.

All solvers in Krylov.jl have in-place version, are compatible with GPU and work in any floating-point data type.

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

julia> ]
pkg> add Krylov
pkg> test Krylov

If you think you found a bug, feel free to open an issue. Focused suggestions and requests can also be opened as issues. Before opening a pull request, start an issue or a discussion on the topic, please.

If you want to ask a question not suited for a bug report, feel free to start a discussion here. This forum is for general discussion about this repository and the JuliaSmoothOptimizers organization, so questions about any of our packages are welcome.