Expand description
§Chapter 5.15 — FaerLdl: the v0.1 KKT backend
New with task L1.5 (PLAN.md trilha L; the contract’s §5.7, decision
D10 “hybrid”). Compiled with the faer feature (on by default).
§Purpose
FaerLdl implements KktSolver with the sparse symmetric
factorizations of the faer crate (pure Rust, MIT): LDLᵀ
(simplicial or supernodal, faer’s choice by flops per nnz(L) as in
CHOLMOD, or forced by FaerLdl::supernodal) and the intranodal
Bunch–Kaufman LBLᵀ. What is ours: the fill-reducing ordering (any
Ordering, by default our crate::Amd of Chapter 5.10 — faer’s own AMD
is never called), the regularization policy and the inertia check
(Algorithm K of Chapter 5.14), and the refinement (Algorithm F). The
simplex method never touches this chapter (D10).
§Notation
As in Chapter 5.14: K of order N by its lower triangle, L₀ the
analyzed lower pattern with a full diagonal, π the ordering
(crate::Perm, fwd[k] = the row eliminated k-th), σ_k the pivot
signs, (ρ, δ, τ, β) the regularization.
§Algorithm A (Analyze)
A1. L₀ ← the lower triangle of the pattern plus a full diagonal
(invariant (K1) of Chapter 5.14; KktError::NotSymmetric or
KktError::Structure otherwise).
A2. π ← ordering.order(L₀ + L₀ᵀ, Symmetric).
A2′. π ← the postorder of the elimination tree of π, heaviest
child last (Algorithm P of Chapter 5.9): the same nnz(L), but
subtrees contiguous and the largest front next to its parent —
the one child faer’s relaxed supernodal amalgamation can merge.
Whatever the ordering’s own output convention (the assembly tree of
our crate::Amd, the pivot order of crate::Colamd, a caller’s
permutation), the supernodes faer builds are then as good as the
elimination tree allows (task L1.5b: maros-r7’s augmented system
factorized 11× slower without this step, with the same
nnz(L)).
A3. faer’s symbolic Cholesky of L₀ under the custom permutation π:
elimination tree, column counts, and the simplicial or supernodal
structure of L (threshold from FaerLdl::supernodal).
A4. The pattern of P L₀ Pᵀ in the triangle faer’s numeric phase reads
(upper for the simplicial structure, lower for the supernodal one),
with the position of every entry of L₀ in it: each factorization
then permutes its values by a scatter, and calls faer’s
structure-level numeric phase, which reports how many pivots it
bumped (the top-level one does not; task L1.5b).
§Algorithm N (Numeric factorization)
N1. v ← the values of K on L₀ (steps K1′–K2 of Chapter 5.14),
equilibrated to K̃ = S K S (step K2′), plus the static shifts
(step K2″): v holds K̃_reg.
N2. Choose the kernel:
* LDLᵀ (diagonal Δ, no pivoting) for the normal equations,
for an augmented system that is quasi-definite (ρ, δ > 0), and
whenever dynamic regularization is on (τ = Some): faer’s
left-looking simplicial or supernodal LDLᵀ with the signs σ_k
(permuted by π inside faer), threshold τ and bump β
(step K3). A zero or non-finite pivot without bumping is
KktError::ZeroPivot at the original row fwd[k].
* LBLᵀ (Bunch & Kaufman 1977, 1×1 and 2×2 pivots) for an
augmented system without regularization (ρ = 0 or δ = 0, and
τ = None) when the structure is supernodal: faer’s intranodal
Bunch–Kaufman, whose interchanges stay inside each supernode (the
analyzed structure does not change). With a simplicial structure
faer has no pivoted kernel, and the LDLᵀ path runs instead.
N3. Read the pivots — the diagonal of Δ (first entry of each column
of the simplicial L; diagonal of each supernode’s dense block),
plus the subdiagonal of B for the 2×2 blocks of LBLᵀ — and
count the inertia (step K4). The bumped pivots of step K3: faer’s
count, exact for the simplicial structure; its supernodal kernel
counts only the positive-sign pivots it bumps, so a negative-sign
pivot equal to −β exactly is added — the one count by value left
(it can only overcount, by a pivot that happens to equal −β bit
for bit).
N3′. (S10): if a stored value of the factor (or of the subdiagonal of
B) is not finite, fail with KktError::NotFinite at the
original row fwd[k] of the first such column k.
N4. (S6): fail with KktError::WrongInertia unless the inertia is the
one the form requires.
§Algorithm S (Solve)
x ← S x, faer’s permuted triangular solves x ← Pᵀ L⁻ᵀ Δ⁻¹ L⁻¹ P x
on K̃, then x ← S x (the factor is of K̃ = S K_reg S; and the
intranodal permutation and 2×2 blocks for LBLᵀ), sequentially
(Par::Seq; faer is built without its rayon feature, so results do
not depend on threads). The solve allocates nothing: faer’s stack
memory for it is sized and allocated once, by the factorization, and
kept in the FaerNumeric behind a mutex (a second thread solving
with the same factor at the same moment gets a temporary buffer
instead of waiting) — with KktSolver::solve_refined_with and a
reused crate::RefineWorkspace, a refined solve allocates nothing
either. Measured in L1.5b with a counting allocator on the 186 Netlib
systems of the middle regime: 0 allocations in a second solve and in
a second refined solve with the same workspace (the first solve with a
factor may make one, the lazy initialization of the mutex on macOS).
§Invariants
(F1) The numeric factor shares the symbolic structure it was computed
with (an Arc): a FaerNumeric can be solved with after its
FaerSymbolic is dropped, and never with another one.
(F2) nnz_factor is faer’s stored length of L (diagonal included;
for the supernodal structure, the dense supernodal blocks with
their explicit zeros).
(S6) as in Chapter 5.14, checked in step N4 and asserted in debug
builds.
§What was read
faer 0.24.4, sparse::linalg::cholesky (the public API and its
documentation: factorize_symbolic_cholesky, SymmetricOrdering::Custom,
factorize_numeric_ldlt with LdltRegularization, the intranodal
LBLᵀ, the supernodal storage read by the solves) and
linalg::cholesky::ldlt::factor (the dynamic regularization rule, to
match step K3) — read, not copied; CHOLMOD (Chen, Davis, Hager &
Rajamanickam 2008) for the shape.
§References
See Chapter 5.14; the faer documentation (docs.rs/faer/0.24.4,
sparse::linalg::cholesky); Bunch & Kaufman (1977); Davis, Direct
Methods for Sparse Linear Systems (2006), ch. 4 and 9.
Structs§
- FaerLdl
- The v0.1 backend (D10, hybrid): faer’s sparse
LDLᵀ(normal equations, quasi-definite augmented systems) or intranodalLBLᵀwith Bunch–Kaufman pivots (unregularized augmented systems), with faer’s simplicial/supernodal selection, ordered by our ordering throughKktSolver::analyze. Regularization policy and refinement are the trait’s (Chapter 5.14). - Faer
Numeric - The numeric factor of
FaerLdl(opaque; invariant (F1)). - Faer
Symbolic - The symbolic phase of
FaerLdl(opaque): the analyzed lower pattern, the ordering and faer’s symbolic factor.