Skip to main content

Module perm

Module perm 

Source
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 index i that comes k-th in the new order (the k-th pivot of an elimination, the k-th column of A Q);
  • inv[i] = k — the new position of the old index i.

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)).

Structs§

Pattern
The structure of a compressed sparse column matrix without its values (invariant (P2)): what the orderings of Chapter 5.10 consume.
Perm
A permutation of 0..n with its inverse (invariant (P1), the contract’s (S3)).