Krylov.jl

A Julia Basket of Hand-Picked Krylov Methods
Popularity
115 Stars
Updated Last
5 Months Ago
Started In
March 2015

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

DOI

Documentation Linux/macOS/Windows/FreeBSD Coverage
CI Build Status codecov.io

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 sytems 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

sould 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 sytems are less common but also occur.

  1. Adjoint systems

Ax = b   and   Aᵀy = c

where A can have any shape.

  1. Saddle-point or symmetric quasi-definite (SQD) systems

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

where A can have any shape.

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

How to Cite

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