Documentation
¶
Overview ¶
Package ldl is a sparse LDLᵀ factorisation of quasi-definite (more generally, strongly factorisable) symmetric matrices, the factorisation OSQP uses for its KKT systems.
The algorithms and the three-phase interface (elimination tree and column counts, numeric factorisation, solve) are a port of QDLDL v0.1.9, https://github.com/osqp/qdldl, Copyright 2018 Paul Goulart, Bartolomeo Stellato, Goran Banjac and the OSQP developers, licensed under the Apache License 2.0 (see NOTICE in the repository root). Only QDLDL was consulted; Davis's LDL (LGPL) was not.
A matrix K is quasi-definite when K = [[A, Bᵀ], [B, −C]] with A and C positive definite: every symmetric permutation of K then has an LDLᵀ factorisation with a diagonal D (positive and negative entries, no pivoting) so the ordering can be chosen for sparsity alone. The factorisation fails, with an error, on an exact zero pivot (or a NaN or infinite one); it does not pivot.
The matrix is given as its upper triangle (diagonal included) in CSC form, as OSQP stores it. The symbolic phase (Analyze) depends on the pattern only; the numeric phase (Factor.Refactor) can be redone with new values on the same pattern, without allocating, which is what an ADMM loop that changes ρ needs.
sym, err := ldl.Analyze(kkt) // pattern only f := sym.NewFactor() err = f.Refactor(kkt) // numeric; again after changing values err = f.Solve(x) // x ← K⁻¹ x, in place
Permuted wraps the same phases around a fill-reducing permutation such as order.AMD.
Index ¶
- Variables
- type Factor
- func (f *Factor) D() []float64
- func (f *Factor) DSolve(x []float64) error
- func (f *Factor) LSolve(x []float64) error
- func (f *Factor) LTSolve(x []float64) error
- func (f *Factor) NNZL() int
- func (f *Factor) NumPositive() int
- func (f *Factor) Refactor(a *sparse.CSC[float64]) error
- func (f *Factor) Solve(x []float64) error
- func (f *Factor) Symbolic() *Symbolic
- type Permuted
- type PivotError
- type Symbolic
Constants ¶
This section is empty.
Variables ¶
var ( // ErrDimension: the matrix is not square, or a vector has the wrong length. ErrDimension = errors.New("ldl: dimension mismatch") // ErrNotUpper: an entry lies below the diagonal. Pass the upper triangle only. ErrNotUpper = errors.New("ldl: entry below the diagonal (the upper triangle is expected)") // ErrEmptyColumn: a column has no stored entry. QDLDL requires at least // one per column; store an explicit zero on the diagonal if needed. ErrEmptyColumn = errors.New("ldl: empty column") // ErrDuplicate: a row index appears twice in a column. ErrDuplicate = errors.New("ldl: duplicate entry") // ErrPattern: the matrix passed to Refactor does not have the sparsity // pattern that was analysed. ErrPattern = errors.New("ldl: sparsity pattern differs from the analysed one") // ErrPermutation: the permutation is not a permutation of 0..n-1. ErrPermutation = errors.New("ldl: invalid permutation") // ErrOverflow: a size does not fit the index types (or would not fit // in memory on this platform). ErrOverflow = errors.New("ldl: size overflow") // ErrZeroPivot: a pivot of D is exactly zero; K is not quasi-definite. ErrZeroPivot = errors.New("ldl: zero pivot") // ErrNonFinite: a pivot of D is NaN or infinite. ErrNonFinite = errors.New("ldl: non-finite pivot") // ErrNotFactored: Solve was called before a successful Refactor. ErrNotFactored = errors.New("ldl: not factored") )
Errors returned by the package, matched with errors.Is.
Functions ¶
This section is empty.
Types ¶
type Factor ¶
type Factor struct {
// contains filtered or unexported fields
}
Factor holds L, D and the workspace of the numeric phase for a Symbolic. A Factor is not safe for concurrent use; Solve calls on a factored Factor are read-only and may run concurrently.
func (*Factor) D ¶
D returns the diagonal of D. It is valid after a successful Refactor, and overwritten by the next one. The slice must not be modified.
func (*Factor) NumPositive ¶
NumPositive returns the number of positive entries of D (the positive inertia). For a KKT matrix [[P+σI, Aᵀ], [A, −diag(1/ρ)]] it is n when the matrix is quasi-definite; fewer means P is not positive semidefinite.
func (*Factor) Refactor ¶
Refactor runs the numeric phase (QDLDL_factor) with the values of a, which must have the analysed pattern (checked in O(nnz)). It does not allocate. On a zero or non-finite pivot it returns a *PivotError and the Factor is not usable until a later Refactor succeeds.
type Permuted ¶
type Permuted struct {
// contains filtered or unexported fields
}
Permuted factors P K Pᵀ for a fill-reducing permutation, where K is given by its upper triangle. The permutation follows the package order: p[k] is the original index placed at position k, as returned by order.AMD, so that (P K Pᵀ)[i, j] = K[p[i], p[j]].
The symbolic phase is done once in NewPermuted; Permuted.Refactor takes the original matrix with new values (same pattern) and refactors without allocating; Permuted.Solve permutes, solves and permutes back.
A Permuted owns all the memory of the symbolic phase, so Permuted.Reset can redo it for another matrix and permutation (say, the next problem of a sequence) without allocating once the storage is large enough.
func NewPermuted ¶
NewPermuted validates a (upper triangle, CSC) and perm, builds the upper triangle of P K Pᵀ and runs the symbolic phase on it. Call Refactor before Solve.
func (*Permuted) NumPositive ¶
NumPositive returns the number of positive entries of D (see Factor).
func (*Permuted) Refactor ¶
Refactor refreshes the permuted values from a (the original matrix, same pattern as at NewPermuted) and runs the numeric phase.
func (*Permuted) Reset ¶ added in v0.3.0
Reset is NewPermuted on p itself: it validates a and perm and redoes the symbolic phase, reusing the storage of the previous one where it is large enough, so that a sequence of problems of similar size allocates nothing after the first. The Symbolic and Factor values obtained from p before the call are overwritten and must not be used afterwards. On an error p is unusable until a later Reset succeeds. Call Refactor before Solve.
type PivotError ¶
PivotError reports the column whose pivot made the factorisation fail. It unwraps to ErrZeroPivot or ErrNonFinite.
func (*PivotError) Error ¶
func (e *PivotError) Error() string
func (*PivotError) Unwrap ¶
func (e *PivotError) Unwrap() error
type Symbolic ¶
type Symbolic struct {
// contains filtered or unexported fields
}
Symbolic is the result of the symbolic phase: the elimination tree and the structure of L. It depends on the sparsity pattern of the matrix only and is immutable, so it can back several Factors.
func Analyze ¶
Analyze runs the symbolic phase on the upper triangle a of a symmetric matrix: it validates the structure, computes the elimination tree and the column counts of L (QDLDL_etree). Only O(n + nnz(a)) memory is allocated; L itself is allocated by Symbolic.NewFactor, so a caller can refuse a factor that is too large by looking at NNZL first.
func (*Symbolic) ColCounts ¶
ColCounts returns the number of entries below the diagonal in each column of L. The slice must not be modified.
func (*Symbolic) NNZL ¶
NNZL returns the number of stored (strictly lower) entries of L, the unit diagonal excluded.
Source Files