## CG

`Krylov.cg`

— Function```
(x, stats) = cg(A, b::AbstractVector{FC};
M=I, ldiv::Bool=false, radius::T=zero(T),
linesearch::Bool=false, atol::T=√eps(T),
rtol::T=√eps(T), itmax::Int=0,
timemax::Float64=Inf, verbose::Int=0, history::Bool=false,
callback=solver->false, iostream::IO=kstdout)
```

`T`

is an `AbstractFloat`

such as `Float32`

, `Float64`

or `BigFloat`

. `FC`

is `T`

or `Complex{T}`

.

`(x, stats) = cg(A, b, x0::AbstractVector; kwargs...)`

CG can be warm-started from an initial guess `x0`

where `kwargs`

are the same keyword arguments as above.

The conjugate gradient method to solve the Hermitian linear system Ax = b of size n.

The method does *not* abort if A is not definite. M also indicates the weighted norm in which residuals are measured.

**Input arguments**

`A`

: a linear operator that models a Hermitian positive definite matrix of dimension n;`b`

: a vector of length n.

**Optional argument**

`x0`

: a vector of length n that represents an initial guess of the solution x.

**Keyword arguments**

`M`

: linear operator that models a Hermitian positive-definite matrix of size`n`

used for centered preconditioning;`ldiv`

: define whether the preconditioner uses`ldiv!`

or`mul!`

;`radius`

: add the trust-region constraint ‖x‖ ≤`radius`

if`radius > 0`

. Useful to compute a step in a trust-region method for optimization;`linesearch`

: if`true`

, indicate that the solution is to be used in an inexact Newton method with linesearch. If negative curvature is detected at iteration k > 0, the solution of iteration k-1 is returned. If negative curvature is detected at iteration 0, the right-hand side is returned (i.e., the negative gradient);`atol`

: absolute stopping tolerance based on the residual norm;`rtol`

: relative stopping tolerance based on the residual norm;`itmax`

: the maximum number of iterations. If`itmax=0`

, the default number of iterations is set to`2n`

;`timemax`

: the time limit in seconds;`verbose`

: additional details can be displayed if verbose mode is enabled (verbose > 0). Information will be displayed every`verbose`

iterations;`history`

: collect additional statistics on the run such as residual norms, or Aᴴ-residual norms;`callback`

: function or functor called as`callback(solver)`

that returns`true`

if the Krylov method should terminate, and`false`

otherwise;`iostream`

: stream to which output is logged.

**Output arguments**

`x`

: a dense vector of length n;`stats`

: statistics collected on the run in a`SimpleStats`

structure.

**Reference**

- M. R. Hestenes and E. Stiefel,
*Methods of conjugate gradients for solving linear systems*, Journal of Research of the National Bureau of Standards, 49(6), pp. 409–436, 1952.

`Krylov.cg!`

— Function```
solver = cg!(solver::CgSolver, A, b; kwargs...)
solver = cg!(solver::CgSolver, A, b, x0; kwargs...)
```

where `kwargs`

are keyword arguments of `cg`

.

See `CgSolver`

for more details about the `solver`

.

## CR

`Krylov.cr`

— Function```
(x, stats) = cr(A, b::AbstractVector{FC};
M=I, ldiv::Bool=false, radius::T=zero(T),
linesearch::Bool=false, γ::T=√eps(T),
atol::T=√eps(T), rtol::T=√eps(T), itmax::Int=0,
timemax::Float64=Inf, verbose::Int=0, history::Bool=false,
callback=solver->false, iostream::IO=kstdout)
```

`T`

is an `AbstractFloat`

such as `Float32`

, `Float64`

or `BigFloat`

. `FC`

is `T`

or `Complex{T}`

.

`(x, stats) = cr(A, b, x0::AbstractVector; kwargs...)`

CR can be warm-started from an initial guess `x0`

where `kwargs`

are the same keyword arguments as above.

A truncated version of Stiefel’s Conjugate Residual method to solve the Hermitian linear system Ax = b of size n or the least-squares problem min ‖b - Ax‖ if A is singular. The matrix A must be Hermitian semi-definite. M also indicates the weighted norm in which residuals are measured.

**Input arguments**

`A`

: a linear operator that models a Hermitian positive definite matrix of dimension n;`b`

: a vector of length n.

**Optional argument**

`x0`

: a vector of length n that represents an initial guess of the solution x.

**Keyword arguments**

`M`

: linear operator that models a Hermitian positive-definite matrix of size`n`

used for centered preconditioning;`ldiv`

: define whether the preconditioner uses`ldiv!`

or`mul!`

;`radius`

: add the trust-region constraint ‖x‖ ≤`radius`

if`radius > 0`

. Useful to compute a step in a trust-region method for optimization;`linesearch`

: if`true`

, indicate that the solution is to be used in an inexact Newton method with linesearch. If negative curvature is detected at iteration k > 0, the solution of iteration k-1 is returned. If negative curvature is detected at iteration 0, the right-hand side is returned (i.e., the negative gradient);`γ`

: tolerance to determine that the curvature of the quadratic model is nonpositive;`atol`

: absolute stopping tolerance based on the residual norm;`rtol`

: relative stopping tolerance based on the residual norm;`itmax`

: the maximum number of iterations. If`itmax=0`

, the default number of iterations is set to`2n`

;`timemax`

: the time limit in seconds;`verbose`

: additional details can be displayed if verbose mode is enabled (verbose > 0). Information will be displayed every`verbose`

iterations;`history`

: collect additional statistics on the run such as residual norms, or Aᴴ-residual norms;`callback`

: function or functor called as`callback(solver)`

that returns`true`

if the Krylov method should terminate, and`false`

otherwise;`iostream`

: stream to which output is logged.

**Output arguments**

`x`

: a dense vector of length n;`stats`

: statistics collected on the run in a`SimpleStats`

structure.

**References**

- M. R. Hestenes and E. Stiefel,
*Methods of conjugate gradients for solving linear systems*, Journal of Research of the National Bureau of Standards, 49(6), pp. 409–436, 1952. - E. Stiefel,
*Relaxationsmethoden bester Strategie zur Losung linearer Gleichungssysteme*, Commentarii Mathematici Helvetici, 29(1), pp. 157–179, 1955. - D. G. Luenberger,
*The conjugate residual method for constrained minimization problems*, SIAM Journal on Numerical Analysis, 7(3), pp. 390–398, 1970. - M-A. Dahito and D. Orban,
*The Conjugate Residual Method in Linesearch and Trust-Region Methods*, SIAM Journal on Optimization, 29(3), pp. 1988–2025, 2019.

`Krylov.cr!`

— Function```
solver = cr!(solver::CrSolver, A, b; kwargs...)
solver = cr!(solver::CrSolver, A, b, x0; kwargs...)
```

where `kwargs`

are keyword arguments of `cr`

.

See `CrSolver`

for more details about the `solver`

.

## CAR

`Krylov.car`

— Function```
(x, stats) = car(A, b::AbstractVector{FC};
M=I, ldiv::Bool=false,
atol::T=√eps(T), rtol::T=√eps(T),
itmax::Int=0, timemax::Float64=Inf,
verbose::Int=0, history::Bool=false,
callback=solver->false, iostream::IO=kstdout)
```

`T`

is an `AbstractFloat`

such as `Float32`

, `Float64`

or `BigFloat`

. `FC`

is `T`

or `Complex{T}`

.

`(x, stats) = car(A, b, x0::AbstractVector; kwargs...)`

CAR can be warm-started from an initial guess `x0`

where `kwargs`

are the same keyword arguments as above.

CAR solves the Hermitian and positive definite linear system Ax = b of size n. CAR minimizes ‖Arₖ‖₂ when M = Iₙ and ‖AMrₖ‖*M otherwise. The estimates computed every iteration are ‖Mrₖ‖₂ and ‖AMrₖ‖*M.

**Input arguments**

`A`

: a linear operator that models a Hermitian positive definite matrix of dimension n;`b`

: a vector of length n.

**Optional argument**

`x0`

: a vector of length n that represents an initial guess of the solution x.

**Keyword arguments**

`M`

: linear operator that models a Hermitian positive-definite matrix of size`n`

used for centered preconditioning;`ldiv`

: define whether the preconditioner uses`ldiv!`

or`mul!`

;`atol`

: absolute stopping tolerance based on the residual norm;`rtol`

: relative stopping tolerance based on the residual norm;`itmax`

: the maximum number of iterations. If`itmax=0`

, the default number of iterations is set to`2n`

;`timemax`

: the time limit in seconds;`verbose`

: additional details can be displayed if verbose mode is enabled (verbose > 0). Information will be displayed every`verbose`

iterations;`history`

: collect additional statistics on the run such as residual norms, or Aᴴ-residual norms;`callback`

: function or functor called as`callback(solver)`

that returns`true`

if the Krylov method should terminate, and`false`

otherwise;`iostream`

: stream to which output is logged.

**Output arguments**

`x`

: a dense vector of length n;`stats`

: statistics collected on the run in a`SimpleStats`

structure.

**Reference**

- A. Montoison, D. Orban and M. A. Saunders,
*MinAres: An Iterative Solver for Symmetric Linear Systems*, Cahier du GERAD G-2023-40, GERAD, Montréal, 2023.

`Krylov.car!`

— Function```
solver = car!(solver::CarSolver, A, b; kwargs...)
solver = car!(solver::CarSolver, A, b, x0; kwargs...)
```

where `kwargs`

are keyword arguments of `car`

.

See `CarSolver`

for more details about the `solver`

.

## CG-LANCZOS

`Krylov.cg_lanczos`

— Function```
(x, stats) = cg_lanczos(A, b::AbstractVector{FC};
M=I, ldiv::Bool=false,
check_curvature::Bool=false, atol::T=√eps(T),
rtol::T=√eps(T), itmax::Int=0,
timemax::Float64=Inf, verbose::Int=0, history::Bool=false,
callback=solver->false, iostream::IO=kstdout)
```

`T`

is an `AbstractFloat`

such as `Float32`

, `Float64`

or `BigFloat`

. `FC`

is `T`

or `Complex{T}`

.

`(x, stats) = cg_lanczos(A, b, x0::AbstractVector; kwargs...)`

CG-LANCZOS can be warm-started from an initial guess `x0`

where `kwargs`

are the same keyword arguments as above.

The Lanczos version of the conjugate gradient method to solve the Hermitian linear system Ax = b of size n.

The method does *not* abort if A is not definite.

**Input arguments**

`A`

: a linear operator that models a Hermitian matrix of dimension n;`b`

: a vector of length n.

**Optional argument**

`x0`

: a vector of length n that represents an initial guess of the solution x.

**Keyword arguments**

`M`

: linear operator that models a Hermitian positive-definite matrix of size`n`

used for centered preconditioning;`ldiv`

: define whether the preconditioner uses`ldiv!`

or`mul!`

;`check_curvature`

: if`true`

, check that the curvature of the quadratic along the search direction is positive, and abort if not, unless`linesearch`

is also`true`

;`atol`

: absolute stopping tolerance based on the residual norm;`rtol`

: relative stopping tolerance based on the residual norm;`itmax`

: the maximum number of iterations. If`itmax=0`

, the default number of iterations is set to`2n`

;`timemax`

: the time limit in seconds;`verbose`

: additional details can be displayed if verbose mode is enabled (verbose > 0). Information will be displayed every`verbose`

iterations;`history`

: collect additional statistics on the run such as residual norms, or Aᴴ-residual norms;`callback`

: function or functor called as`callback(solver)`

that returns`true`

if the Krylov method should terminate, and`false`

otherwise;`iostream`

: stream to which output is logged.

**Output arguments**

`x`

: a dense vector of length n;`stats`

: statistics collected on the run in a`LanczosStats`

structure.

**References**

- A. Frommer and P. Maass,
*Fast CG-Based Methods for Tikhonov-Phillips Regularization*, SIAM Journal on Scientific Computing, 20(5), pp. 1831–1850, 1999. - C. C. Paige and M. A. Saunders,
*Solution of Sparse Indefinite Systems of Linear Equations*, SIAM Journal on Numerical Analysis, 12(4), pp. 617–629, 1975.

`Krylov.cg_lanczos!`

— Function```
solver = cg_lanczos!(solver::CgLanczosSolver, A, b; kwargs...)
solver = cg_lanczos!(solver::CgLanczosSolver, A, b, x0; kwargs...)
```

where `kwargs`

are keyword arguments of `cg_lanczos`

.

See `CgLanczosSolver`

for more details about the `solver`

.

## CG-LANCZOS-SHIFT

`Krylov.cg_lanczos_shift`

— Function```
(x, stats) = cg_lanczos_shift(A, b::AbstractVector{FC}, shifts::AbstractVector{T};
M=I, ldiv::Bool=false,
check_curvature::Bool=false, atol::T=√eps(T),
rtol::T=√eps(T), itmax::Int=0,
timemax::Float64=Inf, verbose::Int=0, history::Bool=false,
callback=solver->false, iostream::IO=kstdout)
```

`T`

is an `AbstractFloat`

such as `Float32`

, `Float64`

or `BigFloat`

. `FC`

is `T`

or `Complex{T}`

.

The Lanczos version of the conjugate gradient method to solve a family of shifted systems

`(A + αI) x = b (α = α₁, ..., αₚ)`

of size n. The method does *not* abort if A + αI is not definite.

**Input arguments**

`A`

: a linear operator that models a Hermitian matrix of dimension n;`b`

: a vector of length n;`shifts`

: a vector of length p.

**Keyword arguments**

`M`

: linear operator that models a Hermitian positive-definite matrix of size`n`

used for centered preconditioning;`ldiv`

: define whether the preconditioner uses`ldiv!`

or`mul!`

;`check_curvature`

: if`true`

, check that the curvature of the quadratic along the search direction is positive, and abort if not, unless`linesearch`

is also`true`

;`atol`

: absolute stopping tolerance based on the residual norm;`rtol`

: relative stopping tolerance based on the residual norm;`itmax`

: the maximum number of iterations. If`itmax=0`

, the default number of iterations is set to`2n`

;`timemax`

: the time limit in seconds;`verbose`

: additional details can be displayed if verbose mode is enabled (verbose > 0). Information will be displayed every`verbose`

iterations;`history`

: collect additional statistics on the run such as residual norms, or Aᴴ-residual norms;`callback`

: function or functor called as`callback(solver)`

that returns`true`

if the Krylov method should terminate, and`false`

otherwise;`iostream`

: stream to which output is logged.

**Output arguments**

`x`

: a vector of p dense vectors, each one of length n;`stats`

: statistics collected on the run in a`LanczosShiftStats`

structure.

**References**

- A. Frommer and P. Maass,
*Fast CG-Based Methods for Tikhonov-Phillips Regularization*, SIAM Journal on Scientific Computing, 20(5), pp. 1831–1850, 1999. - C. C. Paige and M. A. Saunders,
*Solution of Sparse Indefinite Systems of Linear Equations*, SIAM Journal on Numerical Analysis, 12(4), pp. 617–629, 1975.

`Krylov.cg_lanczos_shift!`

— Function`solver = cg_lanczos!(solver::CgLanczosShiftSolver, A, b, shifts; kwargs...)`

where `kwargs`

are keyword arguments of `cg_lanczos_shift`

.

See `CgLanczosShiftSolver`

for more details about the `solver`

.