Documentation
¶
Overview ¶
Package iter provides Krylov-subspace solvers for sparse linear systems (CG, GMRES(m), BiCGSTAB, MINRES, LSQR) and preconditioners (Jacobi, SSOR, IC(0), ILU(0), ILUT). The solvers follow scipy.sparse.linalg: the same stopping rule ||b - A x|| <= max(rtol*||b||, atol), the same default maxiter, the same info codes, so results are directly comparable.
The algorithms are the textbook ones (Hestenes-Stiefel 1952; Saad-Schultz 1986; van der Vorst 1992; Paige-Saunders 1975 and 1982; Meijerink-van der Vorst 1977; Saad 1994). The stopping logic and the GMRES inner-tolerance control mirror SciPy's BSD-3-Clause implementation, which is credited here.
Index ¶
Constants ¶
const ( Converged = 0 BreakdownRho = -10 // BiCGSTAB: (r̃, r) vanished BreakdownOmega = -11 // BiCGSTAB: omega or (r̃, v) vanished )
Info codes of Result.Info (SciPy convention: 0 success, > 0 the iteration limit was reached, < 0 breakdown).
Variables ¶
var ErrBreakdown = errors.New("iter: factorisation breakdown")
ErrBreakdown reports a zero or non-positive pivot while factorising.
var ErrShape = errors.New("iter: incompatible shapes")
ErrShape reports an operator that is not square or a vector of the wrong size.
Functions ¶
func TrueResidual ¶
TrueResidual returns ||b - A x|| / ||b|| (the quantity to verify, not the recurrence residual); it is ||b - A x|| when b is zero.
Types ¶
type IC0 ¶
type IC0 struct {
// contains filtered or unexported fields
}
IC0 is the incomplete Cholesky factorisation with zero fill, M = L Lᵀ, L having the sparsity of the lower triangle of A (Meijerink and van der Vorst 1977).
func NewIC0 ¶
NewIC0 factorises the lower triangle of a symmetric positive definite matrix; a non-positive pivot returns ErrBreakdown.
type ILU ¶
type ILU struct {
// contains filtered or unexported fields
}
ILU is an incomplete LU factorisation A ≈ L U, L unit lower triangular (strict part stored), U upper triangular with the diagonal stored first in each row. It is produced by NewILU0 and NewILUT.
func NewILUT ¶
NewILUT computes the dual-threshold incomplete LU of Saad (1994): entries smaller than droptol times the 2-norm of their row of A are dropped, and at most lfil entries are kept in each row of L and in each row of U (the diagonal is always kept). lfil <= 0 means no cap.
type Jacobi ¶
type Jacobi struct {
// contains filtered or unexported fields
}
Jacobi is the diagonal preconditioner M = diag(A).
type LSMROptions ¶
type LSMROptions struct {
Damp float64
ATol float64 // 0 means 1e-6; negative means 0
BTol float64 // 0 means 1e-6; negative means 0
ConLim float64 // 0 means 1e8; negative disables the test
MaxIter int // 0 means min(m, n)
X0 []float64
}
LSMROptions configures LSMR; the zero value is SciPy's default call (atol = btol = 1e-6, conlim = 1e8, maxiter = min(m, n)).
type LSMRResult ¶
type LSMRResult struct {
X []float64
Istop int
Itn int
NormR float64 // ||b - A x||
NormAR float64 // ||Aᵀ(b - A x)||
NormA float64
CondA float64
NormX float64
}
LSMRResult mirrors the tuple returned by scipy.sparse.linalg.lsmr.
func LSMR ¶
func LSMR(a sparse.TransposeOperator, b []float64, o *LSMROptions) (LSMRResult, error)
LSMR solves min ||b - A x|| (Fong and Saunders 2011, doi:10.1137/10079687X) by Golub-Kahan bidiagonalisation, minimising ||Aᵀ r|| at each step, with the stopping rules of scipy.sparse.linalg.lsmr.
type LSQROptions ¶
type LSQROptions struct {
Damp float64 // solves min ||b-Ax||² + damp²||x||²
ATol float64 // 0 means 1e-6; negative means 0
BTol float64 // 0 means 1e-6; negative means 0
ConLim float64 // 0 means 1e8; negative disables the test
IterLim int // 0 means 2n
X0 []float64
// CalcVar requests the diagonal estimate of (AᵀA + damp²I)⁻¹.
CalcVar bool
}
LSQROptions configures LSQR; the zero value is SciPy's default call (atol = btol = 1e-6, conlim = 1e8, iter_lim = 2n).
type LSQRResult ¶
type LSQRResult struct {
X []float64
Istop int // 0..7 as documented by SciPy
Itn int
R1Norm float64 // ||b - A x||
R2Norm float64 // sqrt(||b - A x||² + damp²||x||²)
ANorm float64
ACond float64
ARNorm float64
XNorm float64
Var []float64
}
LSQRResult mirrors the tuple returned by scipy.sparse.linalg.lsqr.
func LSQR ¶
func LSQR(a sparse.TransposeOperator, b []float64, o *LSQROptions) (LSQRResult, error)
LSQR solves the least-squares problem min ||b - A x|| (Paige and Saunders 1982) for a rectangular operator that can apply Aᵀ, following scipy.sparse.linalg.lsqr.
type Operator ¶
type Operator = sparse.LinearOperator
Operator is the matrix-free input of the solvers.
type Options ¶
type Options struct {
// RTol is the relative tolerance; 0 means the SciPy default 1e-5 and a
// negative value means exactly 0 (use ATol alone).
RTol float64
// ATol is the absolute tolerance (default 0).
ATol float64
// MaxIter bounds the iterations: 0 means 10n (5n for MINRES). For GMRES
// it bounds restart cycles.
MaxIter int
// X0 is the initial guess (default zero). It is not modified.
X0 []float64
// M is the preconditioner (default none). For CG and MINRES it must be
// symmetric positive definite. GMRES preconditions on the left.
M Preconditioner
// Callback, if set, is called after each iteration with the current
// iterate (after each restart cycle for GMRES). x must not be retained.
Callback func(x []float64)
// Restart is the GMRES restart length m (default 20).
Restart int
// Shift solves (A - Shift*I) x = b in MINRES.
Shift float64
}
Options configures CG, GMRES, BiCGSTAB and MINRES. The zero value is SciPy's default call.
type Preconditioner ¶
type Preconditioner interface {
Solve(dst, r []float64)
}
Preconditioner applies an approximate inverse: Solve stores M⁻¹ r in dst. dst and r never alias.
type Result ¶
type Result struct {
X []float64
Info int // see the info constants; > 0 is the iteration limit
Iterations int // iterations performed (GMRES: inner iterations)
}
Result is the outcome of a solve.
func GMRES ¶
GMRES solves A x = b with restarted GMRES(m), left-preconditioned, using modified Gram-Schmidt and Givens rotations, with the inner-iteration tolerance control of scipy.sparse.linalg.gmres (gh-8400): the inner loop stops on the preconditioned residual and the outer loop checks the true residual.
func MINRES ¶
MINRES solves A x = b for symmetric, possibly indefinite A (Paige and Saunders 1975), with the stopping tests of scipy.sparse.linalg.minres: relative residual ||r||/(||A|| ||x||) against RTol (default 1e-5), and the least-squares test. Info is 0 on success and the iteration limit when it was reached; o.MaxIter defaults to 5n. The preconditioner must be symmetric positive definite.
type SSOR ¶
type SSOR struct {
// contains filtered or unexported fields
}
SSOR is the symmetric successive over-relaxation preconditioner M = 1/(ω(2-ω)) (D+ωL) D⁻¹ (D+ωU), for the splitting A = L + D + U.
Source Files