Case study 03

Traceable Sparse Algebra

Sparse algebra that carries value, lineage, and sensitivity.

A dual-number-style semiring extension for associative-array algebra that tracks value, provenance, and first-order sensitivity together.

Evidence at a glance

Representation
One sparse computation carries value, provenance, and first-order sensitivity.
Research state
IEEE URTC write-up in preparation.
Caveat
Bookkeeping illustration, not a live GraphBLAS kernel.

Carry value, sensitivity, and lineage together.

The research extends associative-array algebra with a dual-number-style semiring, keeping first-order sensitivity and provenance attached to a sparse computation.

Representation

A primal value travels with an epsilon coefficient and a record of the sparse path that contributed it. The three records remain associated through the illustrated multiply and reduce stages.

Research boundary

This route explains bookkeeping for the MIT SSRC work. It is not a live GraphBLAS kernel, and the IEEE URTC write-up is still in preparation.

Trace one seed

Select a diagonal epsilon seed. The matrix, propagation stages, and result expose the corresponding value, derivative, and provenance record.

0a0bc0
  1. 01A₁₁
  2. 02multiply
  3. 03reduce
  • ValueThe primal scalar that survives the sparse product.
  • SensitivityThe ε coefficient: first-order response of that seed.
  • ProvenanceWhich matrix path wrote the number, still labeled illustration.

Illustration of the bookkeeping, not a live GraphBLAS kernel. Choose an ε seed on the diagonal.