# Streaming Right Multiplication over Grammar-Compressed Matrices: A Memory-Bounded GPU Engine for Genotype and Graph Data

DevFeed: [Streaming Right Multiplication over Grammar-Compressed Matrices: A Memory-Bounded GPU Engine for Genotype and Graph Data](<https://devfeed.tech/articles/streaming-right-multiplication-over-grammar-compressed-matrices-a-memory-bounded-gpu-engine-for-genotype-and-graph-data-113764.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2607.24971>)

Author: Francesco Tosoni, Gabriele Mencagli

Published: 2026-11-03T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Distributed Computing](<https://devfeed.tech/sources/arxiv-distributed-computing.md>)

Topics: [RAPIDS](<https://devfeed.tech/topics/rapids.md>), [Streaming](<https://devfeed.tech/topics/streaming.md>), [Graphs](<https://devfeed.tech/topics/graphs.md>)

Tags: [cs-dc](<https://devfeed.tech/tags/cs-dc.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-ms](<https://devfeed.tech/tags/cs-ms.md>), [cs-pf](<https://devfeed.tech/tags/cs-pf.md>), [engine](<https://devfeed.tech/tags/engine.md>), [gpu](<https://devfeed.tech/tags/gpu.md>), [grammar](<https://devfeed.tech/tags/grammar.md>), [graph](<https://devfeed.tech/tags/graph.md>), [matrices](<https://devfeed.tech/tags/matrices.md>), [memory](<https://devfeed.tech/tags/memory.md>), [streaming](<https://devfeed.tech/tags/streaming.md>)

## AI overview

The GPU engine computes right products over grammar-compressed matrices with a bottom-up gather sweep. Pass-through completion layers the SLP DAG, allowing each level to read from one buffer and write to another; memory use is bounded by two alternating buffers rather than the whole grammar. For genotype polygenic scores, the CUDA implementation uses 3.5-8x less device memory than materialized cuSPARSE CSR, runs single-vector products within a small factor of cuSPARSE, and uses less GPU energy. The same associative, commutative combine framework supports other commutative-monoid computations; its reachability sweep is also demonstrated on a billion-edge Software Heritage graph. Structural metrics are architecture-independent, while timing and energy results come from a single GPU board.

## Source excerpt

arXiv:2607.24971v2 Announce Type: replace-cross Abstract: Grammar-compressed matrices store a matrix's non-zero structure as a RePair straight-line program (SLP), supporting matrix-vector products in time and space proportional to the compressed size. We target the regime where this is decisive on a GPU: when the uncompressed matrix exceeds device memory, so footprint (not floating-point throughput) is the binding constraint. Our SLP is a directed acyclic graph (DAG) of out-degree 2, and the right product $y=Mx$ is a single bottom-up sweep (leaves to roots): a conflict-free gather. We make the grammar properly layered (every nonterminal child one level below its parent) via pass-through completion, which inserts identity nodes to carry values upward until consumed. This yields a streaming evaluation in which each level reads only the level below and writes the next, so the live set fits in two alternating read-only/write-only buffers instead of scaling with the whole grammar. On genotype matrices, where a polygenic score is exactly the right product $y=G\beta$, a CUDA implementation shows a clear space advantage: a device footprint 3.5 to 8 times smaller than a materialized cuSPARSE CSR baseline, single-vector times within a small factor of cuSPARSE, and consistently lower GPU energy. Because the sweep needs only an associative and commutative combine, the same engine evaluates any homomorphism into a commutative monoid over the grammar by swapping a small leaf/combine/emit policy; the same reachability sweep scales to a billion-edge Software Heritage graph (261 TB dense, 21 times smaller serialized than cuSPARSE's CSR). We frame this as an algorithm-engineering case study: structural metrics (depth, live-set width, completion cost) are measured, architecture-independent grammar properties, whereas time and energy are profiled on a single board.