Skip to main content

Module symbolic

Module symbolic 

Source
Expand description

§Chapter 5.12 — The reusable pivot sequence: SymbolicLu

New with task L1.3 (PLAN.md trilha L; the contract’s SymbolicLu, LuFactor::refactorize_same_pattern and the pre-order PreOrder).

§Purpose

Algorithm L (Chapter 5.3) spends most of its time deciding: loading the doubly linked row and column files, keeping the count lists, and searching for Markowitz pivots. When the same pattern comes back with new values — the same basis after a change of scaling or of bounds, a node of branch and bound that restarts from its parent’s basis, a sequence of systems with one structure — the decisions of the last factorization are still good ones, and only the arithmetic has to be redone. SymbolicLu keeps those decisions: the pivot sequence (p_s, q_s), s = 0, …, m − 1. crate::LuFactor::refactorize_same_pattern replays it by a left-looking elimination (Algorithm R) that computes one column of L and U at a time with a sparse triangular solve, the scheme of Gilbert & Peierls (1988) with the pivot rows given instead of searched for.

This is weaker than the symbolic object of UMFPACK, which also fixes the patterns of L and U (a threshold-pivoting Markowitz LU chooses its pivots by value, so its analysis is not separable; the contract, Divergences): the patterns are recomputed — cheaply, by the reach of each column — and every pivot is tested again. A pivot refused by the test, or a sequence of another order, sends the call back to Algorithm L, so the result is always a valid factorization (or the diagnosis of a singular basis).

The optional COLAMD pre-order of the bump (crate::Lu::set_pre_order, step L5′ of Chapter 5.3) is the other half of the contract’s symbolic phase: it fixes the column order of the first factorization from the pattern alone, and the sequence it produces is the one Algorithm R reuses.

§Notation

B is m × m with columns given by a ColumnSource; the sequence is p_s = pivot_rows[s], q_s = pivot_cols[s]; its first σ steps (singletons) were singleton pivots of the triangular phase (L3–L4), forced by the structure. At step s the rows p_0, …, p_{s−1} are pivoted, the others active. L_t is the L column of step t (multipliers l_it for active rows i at step t), indexed by its pivot row; the graph G_L has an edge p_t → i for every l_it.

§Algorithm R (Refactorization with a given pivot sequence)

R1. [Applicable?] If there is no sequence, or its order is not m, fall back to Algorithm L. Validate the source (invariant (B1)). R2. [Scatter.] For s = 0, 1, …, m − 1: let q = q_s, p = p_s; scatter column q of B into the dense row-indexed work vector x and its rows into the pattern X. R3. [Reach.] Find the set of rows reachable from X in G_L by depth- first search; it joins X. The pivoted rows with an L column, in reverse postorder of the search, are a topological order of the reach (Gilbert & Peierls 1988). R4. [Solve.] In that order, for each pivoted row r with x_r ≠ 0: x_i ← x_i − l_ir x_r for every l_ir of L_r. Now x_r (pivoted r) is the entry u_{r q} of U, and x_i (active i) is the entry s_iq of the Schur complement that Algorithm L would have seen when pivoting column q. R5. [Test.] Let γ = max_{i active} |x_i|. If |x_p| ≤ τ_abs, or s ≥ σ and |x_p| < u_R γ (by default u_R = u, Markowitz’s threshold of Chapter 5.3; the singleton steps keep the rule of L3–L4: forced pivots, no relative test), fall back to Algorithm L. R6. [Record.] u_pq ← x_p; for each pivoted r ∈ X with |x_r| > ε_drop record u_rq = x_r; for each active i ≠ p with |x_i| > ε_drop record l_is = x_i / x_p (the L column of step s, pivot row p). Clear x on X; row p is pivoted. R7. [Finish.] Step L7 of Chapter 5.3 on the result (the statistics of the singleton and Markowitz pivots are those of the sequence).

§Invariants

(R1) R4 computes the Schur complement column of step s exactly as Algorithm L would (in a different order of the same operations), so with the same sequence L U = P B Q holds to rounding and (F1)–(F3) of Chapter 5.3 hold (checked by check_invariants after step L7 in debug builds and against the dense product in the tests). (R2) With the default u_R = u, the threshold test of R5 is the one Algorithm L applies to its bump pivots, so a sequence is replayed only when it would have been acceptable to Algorithm L for these values. crate::Lu::set_refactor_pivot_tol may lower u_R (never u, which Algorithm L keeps).

§The replay threshold (task L1.5b)

A Markowitz search accepts the sparsest pivot that passes u, so many recorded pivots sit just above it: in L1.3, 30 of 109 bases (93 Netlib optimal bases and 16 unsymmetric Harwell–Boeing matrices), with every value perturbed by an independent ±1 %, fell back on the first replay. Measured in L1.5b on the same 109, first replay of B₂ with the sequence of B₁:

u_Rfallbacksreplays with a residual > 10× the fresh one
u = 10⁻² (default)300
5·10⁻³190
10⁻³90
10⁻⁴22 (orsirr_1 ×43, degen3 ×290)

(residual ‖B x − b‖_∞ / (‖B‖_∞‖x‖_∞ + ‖b‖_∞) for b = B·1). The default stays u, which keeps (R2); u_R = u/10 is the measured compromise for a caller that replays sequences over drifting values (the simplex method does not replay yet: integration pending, D-0091 (a)). (R3) A SymbolicLu is recorded after every successful factorization (Algorithm L or R) and dropped after a failed one; its two arrays are permutations of 0..m (debug_assert in the tests).

§Complexity

R2–R6 cost O(nnz(B) + flops) — the flops of the elimination itself, with no count lists, no search and no linked files. Step L7 is shared.

§References

Gilbert & Peierls, “Sparse partial pivoting in time proportional to arithmetic operations”, SIAM J. Sci. Stat. Comput. 9(5), 1988; Davis & Palamadai Natarajan, “Algorithm 907: KLU”, ACM TOMS 37(3), 2010 (refactorization with the previous pivots); Davis, “Algorithm 832: UMFPACK V4.3”, ACM TOMS 30(2), 2004 (symbolic and numeric phases); Suhl & Suhl (1990); the contract of the crate (SymbolicLu, Divergences).

Structs§

SymbolicLu
The reusable part of a factorization: its pivot sequence (Chapter 5.12), consumed by crate::LuFactor::refactorize_same_pattern.