STRIKE: Stateful Traversal for Restart-Based Intersection Kernels for Embedded Sparse Matrix Multiplication

Sparse matrix multiplication (SpGEMM) constitutes a fundamental operation with applications spanning graph neural networks, iterative solvers, and large-scale analytics. State-of-theart algorithms achieve optimal O(|Rowi| + |Colj|) complexity through merge-based intersection, yet systematically discard intermediate state by resetting data structures before each column computation. STRIKE (Stateful Traversal for Restart-based Intersection Kernels) maintains persistent pointer state across consecutive operations, reducing asymptotic cost from O(k(ρA + ρB)) to O(kρA + ρ unique B) for k consecutive columns, where ρ unique B denotes distinct indices encountered. The mechanism functions independently of matrix properties-neither requiring nor assuming correlation-though performance amplifies when structural regularity (quantified via Jaccard similarity β) is present. Integration with Roaring Bitmaps yields combined 4-5× speedups over naive merge across the entire regularity spectrum (β ∈ [0, 0.99]), with restart contributing 1.0-1.7× (varying with ρ unique B , empirically predicted by β) and bitmaps providing 2.5-3× through SIMD acceleration. Experimental validation establishes clear viability thresholds: substantial speedups for n ≥ 1024, nnz ≥ 10 5 ; slowdowns (0.6-0.8×) only for very small problems where preprocessing dominates. Parallel efficiency reaches 37% (embedded workstations) and 55% (servers) at 8 threads. Raspberry Pi 4 deployment achieves 3.3× speedup and 4.4× energy efficiency for edge analytics. This work establishes statefulness as an underexplored design axis for sparse computation, particularly relevant for embedded platforms where moderate memory overhead (2-4×) and algorithmic efficiency directly impact deployment viability.