Popularity
265 Stars
Updated Last
11 Months Ago
Started In
March 2015

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

Documentation Linux/macOS/Windows/FreeBSD Coverage DOI Downloads
docs-stable docs-dev build-gh build-cirrus codecov doi downloads

How to Cite

If you use Krylov.jl in your work, please cite using the format given in CITATION.bib.

Content

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.
  1. 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‖.

  1. 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.

  1. Adjoint systems

Ax = b   and   Aᴴy = c

where A can have any shape.

  1. Saddle-point and Hermitian quasi-definite systems

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

where A can have any shape.

  1. 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.

Features

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

How to Install

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

julia> ]
pkg> add Krylov
pkg> test Krylov

Bug reports and discussions

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.