Skip to main content

Module faer_ldl

Module faer_ldl 

Source
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 intranodal LBLᵀ with Bunch–Kaufman pivots (unregularized augmented systems), with faer’s simplicial/supernodal selection, ordered by our ordering through KktSolver::analyze. Regularization policy and refinement are the trait’s (Chapter 5.14).
FaerNumeric
The numeric factor of FaerLdl (opaque; invariant (F1)).
FaerSymbolic
The symbolic phase of FaerLdl (opaque): the analyzed lower pattern, the ordering and faer’s symbolic factor.