betaFeedback

WorksComputer Science

Dual-Number Associative Arrays for One-Pass Provenance and Sensitivity

Abstract

Associative arrays and GraphBLAS express sparse computations as matrix operations over a chosen semiring, but the result normally contains only the ordinary value. We define a dual-number extension Dk(S)=S⋉SkD_k(S)=S\ltimes S^k that carries this value together with kk independent auxiliary channels in the same computation. We prove that the construction is a split square-zero extension of any commutative semiring. Over min-plus, the auxiliary value is the weight of the shortest walk constrained to use the corresponding edge, excluding the weight of that edge. This gives an exact shortest-path membership test for that edge, although ties return the union of the edges on all optimal paths. We implement the min-plus construction using sparse python-graphblas operations, with a fixpoint test that checks the value and auxiliary components together. We validate the implementation across 18,692 checks, including 2,825 tied target pairs. On random graphs with 100,000 vertices and 32 seed edges, the dual method is 3.39×3.39\times faster than the sequential algorithm but 1.50×1.50\times slower than a min-plus-specific batched method. This difference is largely explained by the dual method requiring 1.55×1.55\times as many sweeps. Thus, the main contribution is a general algebraic approach with competitive sparse performance, rather than information that specialized min-plus algorithms cannot already compute.

Paper details

vlnc:W_jt5b2xdp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…