Expand description
§Chapter 5.9 — Permutations and sparsity patterns
New with task L1.3 (PLAN.md trilha L).
§Purpose
A fill-reducing ordering (Chapter 5.10) looks only at where the
nonzeros of a matrix are, never at their values, and answers with a
permutation. This chapter fixes both objects: Pattern, the
structure of a compressed matrix without its values, and Perm, a
permutation stored together with its inverse. It also measures what an
ordering is for — the number of nonzeros of the Cholesky factor of the
permuted pattern (Algorithm E) — which is the yardstick of every test
and of the acceptance tables of the orderings.
§Notation
A Pattern S with n_rows = m and n = n_cols columns stores, as
a CscMatrix does, the row indices of column j in
row_idx[col_ptr[j]..col_ptr[j + 1]]. A Perm π of 0..n is the
pair of arrays
fwd[k] = i— the old indexithat comesk-th in the new order (thek-th pivot of an elimination, thek-th column ofA Q);inv[i] = k— the new position of the old indexi.
As matrices: P with (P x)_k = x_{fwd[k]}, so P A Pᵀ has entry
(k, l) = a_{fwd[k], fwd[l]}.
For a square pattern S let G(S) be the undirected graph on 0..n
with an edge {i, j} (i ≠ j) whenever s_ij or s_ji is stored: the
graph of S + Sᵀ without its diagonal. L is the Cholesky factor of a
symmetric positive definite matrix with the pattern of P (S + Sᵀ) Pᵀ
(and a full diagonal), nnz(L) its number of entries including the
diagonal — the fill of the ordering in the tables (no numerical
cancellation is assumed: the structural count).
§Algorithm S (Symmetrization S + Sᵀ)
S1. Compute Sᵀ by Algorithm T of Chapter 5.8 (indices only).
S2. For each column j, merge the sorted lists of column j of S and
of Sᵀ, keeping each index once. The result has sorted columns.
§Algorithm E (Elimination tree and Cholesky counts, by row subtrees)
Given the symmetric graph G and the permutation π; let C = P G Pᵀ.
Row k of L is the set of l ≤ k reached from the entries c_kl,
l < k, by walking up the elimination tree of the leading k × k
block (the row subtree, Liu 1986).
E1. Set parent[k] ← ∅, mark[k] ← ∅ for all k, count ← n (the
diagonal).
E2. For k = 0, 1, …, n − 1: set mark[k] ← k; for every neighbour i
of fwd[k] with l = inv[i] < k, walk x ← l, parent[x], … while
mark[x] ≠ k: set mark[x] ← k, count ← count + 1 (the entry
l_kx), and if parent[x] = ∅ set parent[x] ← k and stop.
E3. Return count.
The walk of E2 from l stops at the first node already in row k’s
subtree, so every node of the row subtree is visited once: the cost is
O(nnz(L) + nnz(S)), no log and no sort. Setting parent the first
time a root is reached is Liu’s elimination-tree algorithm without path
compression.
§Algorithm P (Postorder of the elimination tree, heaviest child last)
New with task L1.5b. Given G and π, a permutation π′ with the
same filled graph whose subtrees are contiguous and whose heaviest
child comes right before its parent.
P1. Run Algorithm E, keeping parent[k] and the column counts c_k
(entries of column k of L, diagonal included).
P2. Order the children of every node by increasing (c, k): the child
with the largest column count — the largest front — last.
P3. Visit the roots in increasing order, each subtree depth first with
the children in the order of P2, and number every node after its
children: post[t] is the t-th node. Return fwd′[t] = fwd[post[t]].
Every topological order of the elimination tree — a postorder in
particular — eliminates with the same filled graph (Liu 1990, §3), so
nnz(L) does not change; the postorder makes each subtree a run of
consecutive columns, so every chain of only children (a fundamental
supernode) is contiguous; and placing the heaviest child last puts the
largest front next to its parent. That matters to a supernodal
backend: faer 0.24 (read, not copied) merges a child supernode into its
parent in its relaxed amalgamation only when the child immediately
precedes the parent, and SuiteSparse’s AMD postorders its assembly tree
with the largest front last for the same reason. With the children in
index order instead, faer stored 2.78 M entries of L for the
augmented system of maros-r7 (the same 1.21 M structural ones) and
factorized 11× slower (task L1.5b, D4). Cost O(nnz(L) + n log n).
§Algorithm G (The pattern of SᵀS)
For COLAMD (Chapter 5.10) the relevant symmetric graph is that of SᵀS,
whose Cholesky factor bounds the U of an LU with partial pivoting and
is the R of a QR factorization (George & Ng 1987). Column j of SᵀS
is the union, over the rows i of column j of S, of the columns of
row i (rows read from Sᵀ): mark-and-collect, then sort each column.
Cost O(Σ_i r_i²) with r_i the row counts — which is why COLAMD itself
never forms it.
§Invariants
(P1) (= the contract’s (S3)) A Perm of length n has fwd and inv
of length n, entries < n, and inv[fwd[k]] = k for every k
(so both are bijections). Perm::check_invariants checks it and
every constructor asserts it in debug builds.
(P2) A Pattern satisfies (C1), (C2) and (C4) of Chapter 5.8 (there
are no values, so (C3) is void): pointers non-decreasing from 0 to
nnz, row indices strictly increasing inside a column and smaller
than n_rows. Checked by Pattern::check_invariants.
(P3) The outputs of Algorithms S and G are symmetric patterns that
satisfy (P2).
(P4) Algorithm P returns a permutation with the nnz(L) of its input
(checked in the tests against Algorithm E), in which every node
comes after all of its elimination-tree descendants.
§References
Liu, “A compact row storage scheme for Cholesky factors using
elimination trees”, ACM TOMS 12(2), 1986, and “The role of elimination
trees in sparse factorization”, SIAM J. Matrix Anal. Appl. 11(1), 1990;
George & Ng, “Symbolic factorization for sparse Gaussian elimination
with partial pivoting”, SIAM J. Sci. Stat. Comput. 8(6), 1987; Davis,
Direct Methods for Sparse Linear Systems (2006), §4.1 and §4.4 (read,
not copied); the contract of the crate (Pattern, Perm, (S3)).