← 研踪 PaperTrailarXiv:2611.09589 · v1
Dual-Number Associative Arrays for One-Pass Provenance and Sensitivity
首次提交 2026-11-06 23:22
版本更新 2026-11-06 23:22
雷达观测 2026-11-09 13:22
摘要
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 $D_k(S)=S\ltimes S^k$ that carries this value together with $k$ 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 \texttt{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\times$ faster than the sequential algorithm but $1.50\times$ slower than a min-plus-specific batched method. This difference is largely explained by the dual method requiring $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.
作者备注：5 pages, 1 figure
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-06 23:22 · 最新观测版本
Dual-Number Associative Arrays for One-Pass Provenance and Sensitivity
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 $D_k(S)=S\ltimes S^k$ that carries this value together with $k$ 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 \texttt{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\times$ faster than the sequential algorithm but $1.50\times$ slower than a min-plus-specific batched method. This difference is largely explained by the dual method requiring $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.
查看此版本解读 →查看此版本原文 ↗