5. The optional hooks: emergent pairs

HasRowFiltration has optional methods (hooks) with correct but generic defaults. Overriding them tells the reduction things about your matrix that it would otherwise work out the slow way. volume_lazy.rs starts from the filtration order on cells, and the two questions apparent pairs ask:

/// The filtration order on cells: by value, then number.
fn key(volume: &Volume, cell: u64) -> (NotNan<f32>, u64) {
    (NotNan::new(volume.value(cell)).unwrap(), cell)
}

/// The oldest coface of a cell (the first column in its row of the boundary), and its youngest face (its pivot).
fn oldest_coface(volume: &Volume, cell: u64) -> Option<u64> {
    volume.cofaces(cell).min_by_key(|&c| key(volume, c))
}

fn youngest_face(volume: &Volume, cell: u64) -> Option<u64> {
    volume.faces(cell).max_by_key(|&f| key(volume, f))
}

and overrides three hooks on the coboundary:

impl HasRowFiltration for Coboundary<'_> {
    type FiltrationT = NotNan<f32>;

    fn filtration_value(&self, row: Cell) -> NotNan<f32> {
        NotNan::new(self.0.value(row.0)).unwrap()
    }

    // Step 5, emergent pairs: cohomology's pivot of a column is its *smallest* coface. No coface comes before the cell
    // itself, and cofaces are enumerated in increasing order of their numbers, so the first coface with the cell's own
    // value is the smallest: stop there. Most columns need nothing else, so this usually looks at one or two cofaces.
    fn column_min(&self, col: Cell) -> Option<ColumnEntry<NotNan<f32>, Cell, Z2>> {
        let own = self.filtration_value(col);
        let mut best: Option<ColumnEntry<NotNan<f32>, Cell, Z2>> = None;
        for coface in self.0.cofaces(col.0) {
            let entry: ColumnEntry<_, _, _> = (Z2::one(), Cell(coface), self.filtration_value(Cell(coface))).into();
            if entry.filtration_value == own {
                return Some(entry);
            }
            if best.as_ref().is_none_or(|b| entry < *b) {
                best = Some(entry);
            }
        }
        best
    }

    // Step 5, apparent pairs without the transpose: the columns with an entry in row `r` of the coboundary are the
    // faces of `r`, so the first and last are its oldest and youngest faces
    fn first_column_in_row(&self, row: Cell) -> Option<Cell> {
        self.0.faces(row.0).min_by_key(|&f| key(self.0, f)).map(Cell)
    }

    fn last_column_in_row(&self, row: Cell) -> Option<Cell> {
        youngest_face(self.0, row.0).map(Cell)
    }
}

• column_min: emergent pairs. Cohomology reduces the reversed coboundary, whose pivot is a column’s smallest coface. In a lower-star filtration no coface can come before the cell itself, and our cofaces come in increasing order of their numbers, so the first coface with the cell’s own value is the smallest, and the search stops there. Most columns need nothing but their pivot (nobody else owns it), so most columns are finished after looking at one or two cofaces. Ripser does the same for Vietoris–Rips; Bauer calls these emergent pairs.
• first_column_in_row / last_column_in_row: apparent pairs without the transpose. The columns with an entry in row \(r\) of the coboundary are exactly the faces of \(r\), so the first is its oldest face. No transpose, and no adding up of coefficients.
• column_pivot isn’t overridden: homology would use it, cohomology doesn’t.

Every hook must be right. A pivot that isn’t the true smallest entry, or a “first column” that isn’t, gives a wrong barcode silently. The example checks its barcode against the other methods; the property tests show how to test hooks against their defaults on random inputs.

    // Step 5: the hooks find pivots (emergent pairs) and apparent pairs without building columns or the transpose.
    // Columns are cheap to compute, so recompute them rather than caching, and keep the working column as a heap
    let algorithm = Clearing::new().with_columns(HeapColumns).cache_columns(false);
    reset_peak_memory();
    let full = timed("build every cell up to dimension 2", || full_basis(&volume, 2));
    let delta_full = Coboundary(&volume).with_basis(full);
    let hooks = timed("cohomology, clearing, hooks", || {
        barcode::cohomology(&delta_full, Algorithm::Clearing(algorithm.clone()))
    });

On their own the hooks don’t buy much here: on the 40³ volume this runs in 167 ms, about the same as plain clearing in step 3. With at most six cofaces per column, stopping the search early saves little. (For Vietoris–Rips, where a simplex can have thousands of cofacets, emergent pairs are what make cohomology fast.) What the hooks do buy is cheap, exact apparent pairs, which the next step builds on.

Heap columns, uncached, as in phlite_rips: our columns are short and cheap to recompute, so there is nothing to gain from sorting or keeping them (see choosing a representation).