Pith. sign in

REVIEW 3 major objections 4 minor 49 references

The paper argues that a GPU-specialized entropy coder (dtANS), applied to delta-encoded CSR sparse matrices, can decode on the fly during SpMVM so efficiently that the compressed matrix's smaller size translates directly into speed, with up

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 19:31 UTC pith:GYEEEPXK

load-bearing objection A credible first application of entropy decoding to GPU SpMVM, but the missing encoder artifact keeps the headline numbers unverifiable. the 3 major comments →

arxiv 2603.01915 v2 pith:GYEEEPXK submitted 2026-03-02 cs.PF

Fast Entropy Decoding for Sparse MVM on GPUs

Emil Sch\"atzle , Tommaso Pegolotti , Markus P\"uschel This is my paper
classification cs.PF
keywords sparse matrix-vector multiplicationentropy codingasymmetric numeral systemsdtANSGPU kernelsCSR formatdelta encodingmemory-bound computing
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tries to establish that lossless entropy coding, usually considered too slow for high-performance on-the-fly use, can be adapted to GPUs and applied to sparse matrices to make both their storage and their matrix-vector products smaller and faster. The vehicle is dtANS, a GPU-tuned variant of asymmetric numeral systems, layered on delta-encoded CSR to form a compressed format called CSR-dtANS. For matrices with at least 2^15 nonzeros and at least 10 nonzeros per row on average, almost all tested matrices fit in fewer bytes than the smallest of CSR, COO, and SELL, up to 11.77x fewer, and most matrices with at least 2^25 nonzeros multiply faster, up to 3.48x. If correct, this gives a lossless way to speed up a memory-bound primitive by shrinking the data it must read, with the decoding cost largely hidden behind memory traffic.

Core claim

The paper's central claim is that lossless entropy coding can be made fast enough to run inside a memory-bound GPU kernel, turning compressed size directly into runtime. The authors introduce dtANS, a GPU-specialized variant of table-based asymmetric numeral systems that decodes several symbols at once by breaking the serial state chain, stores the compressed output as warp-interleaved 32-bit words for coalesced reads, and caps symbol multiplicity so most word loads are unconditional. Applying dtANS to delta-encoded CSR gives CSR-dtANS, which on a large public collection of sparse matrices compresses nearly all matrices with at least 2^15 nonzeros and at least 10 nonzeros per row below the s

What carries the argument

dtANS (decoupled tANS), a GPU adaptation of asymmetric numeral systems, the integer-based entropy coder that approaches arithmetic-coding compression with Huffman-like decoding speed. Where standard tANS decodes one symbol through a serial state update, dtANS decodes l=8 symbols per step from o=3 32-bit words, creating instruction-level parallelism, and interleaves the 32 threads' private streams into one word stream so global reads coalesce. A new parameter M caps each symbol's multiplicity in the probability table; with M=256 the decoder needs only f=2 conditional loads per segment, and the remaining o-f loads are unconditional, which keeps threads synchronized. Delta-encoding column indic

Load-bearing premise

The load-bearing premise is that a warp of 32 threads decoding 32 rows consumes the interleaved compressed stream at a roughly synchronized pace, so per-row overhead amortizes and conditional loads stay within their bound; the paper itself notes this fails for matrices with highly irregular numbers of nonzeros per row.

What would settle it

Benchmark CSR-dtANS against the fastest standard format on large matrices (>=2^25 nonzeros, >=10 per row on average) with deliberately skewed row lengths, such as half the nonzeros packed into 1% of rows; if warm-cache runtime does not beat the baseline for most of these, the synchronized-warp premise fails. Alternatively, use memory hardware counters to check whether runtime speedup tracks the reduction in bytes moved, which would show whether decoding is truly hidden.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Matrices with at least 2^15 nonzeros and at least 10 nonzeros per row on average can be stored losslessly with up to 11.77x less memory than the smallest standard format, and a few matrices too large for GPU memory in standard formats fit when compressed.
  • For matrices with at least 2^25 nonzeros, the majority see SpMVM speedups, with a best measured 3.48x; cold-cache runs raise the fraction further.
  • Speedup tracks compression but stays below the compression ratio, indicating that decoding adds some cost yet is fast enough to preserve most of the memory-traffic benefit.
  • Warm-cache speedups mean the scheme helps iterative solvers that reuse the same matrix, not only one-shot cold-cache workloads.
  • dtANS is not tied to CSR: the authors state it can be applied to other sparse formats and other memory-bound GPU data streams.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If decoding truly hides behind memory traffic, the advantage should grow as memory bandwidth lags compute, making entropy-coded formats a natural fit for memory-wall hardware trends and for other bandwidth-bound kernels such as sparse-dense matrix multiplication or embedding lookups.
  • The paper's own split between matrices that compress but do not speed up suggests a cheap runtime heuristic based on total nonzeros and row-length regularity could decide when to use CSR-dtANS versus a standard format; the paper reports the data to calibrate such a rule but does not build it.
  • A direct next step the conclusion hints at is assigning several rows per thread, which would amortize the fixed per-row overhead for short rows and directly attack the irregular-row-length failure mode.
  • Combining dtANS with block or sliced formats could capture both entropy savings and structural padding savings, an avenue the paper does not explore.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes dtANS, a GPU-oriented variant of tANS entropy coding, and applies it to Compressed Sparse Row (CSR) matrices to obtain a compressible format called CSR-dtANS. The matrix indices are delta-encoded, then deltas and values are entropy-coded and interleaved at warp level; the SpMVM kernel decodes the compressed stream on the fly while multiplying by the dense vector. The main empirical claims, evaluated on the SuiteSparse collection against cuSPARSE CSR/COO/SELL and against AlphaSparse, are (i) for matrices with at least 2^15 nonzeros and at least 10 nonzeros per row on average, the representation is smaller than the smallest cuSPARSE format in almost all cases, up to 11.77x; and (ii) for matrices with at least 2^25 nonzeros, CSR-dtANS achieves a SpMVM speedup for the majority of cases, up to 3.48x. The decoder is given as Algorithm 3, with design parameters satisfying the algebraic equalities K^l = W^o and M^l = W^f.

Significance. If the results hold, the paper makes a genuinely useful contribution: it shows that entropy-coded sparse matrices can be decoded on the fly on GPUs fast enough to beat optimized cuSPARSE kernels for large matrices in both warm- and cold-cache settings. The corpus study is broad (8975 SuiteSparse matrices), the baseline is strong, and the decoder specification is sufficiently precise for the reader to check the central design equalities: K^l = 4096^8 = 2^96 = W^o = (2^32)^3, and M^l = 256^8 = 2^64 = W^f = (2^32)^2. The limitations for small matrices and irregular row lengths are explicitly disclosed. However, the paper’s headline is empirical, and the encoder that produced the measured compression ratios is only sketched and not shipped; without a full encoder description or an artifact, the central numbers cannot be reproduced or independently checked.

major comments (3)
  1. [§IV.E and Abstract] The central quantitative claims (Section V.A, Fig. 6, Table I: “up to 11.77 times”) are measurements of an encoder that is not described. Section IV.E states only: “We only discuss encoding with dtANS on a high level due to lack of space” and gives two high-level passes (base pass, digit pass). The Abstract and Section IV.E promise an open-source library, but no repository URL, commit hash, or artifact appears anywhere in the manuscript. The compression ratio depends on several unstated implementation choices: how P' is chosen to minimize cross entropy under the M=256 constraint, how the escape threshold is set, how tables are packed, and how the backward digit pass exactly inverts Algorithm 3. These choices determine the measured ratios, so the headline claim is not independently checkable. The authors must either provide the actual code/artifact or a complete, precise encoder specifica
  2. [§IV.E, §IV.F] No correctness proof is given that the encoder’s digit pass is the exact inverse of Algorithm 3. The statement that loops and checks “have to be reversed exactly” is an implementation directive, not an argument. In particular, the handling of rows whose length is not divisible by 4, the tail treatment, and the escape path (Section IV.F) are described narratively; a subtle mismatch there would silently corrupt the decoded values and make the reported lossless compression and speedups invalid. A theorem or rigorous invariant showing decode(encode(u)) = u for all supported inputs, including padded rows and escaped symbols, is needed for the central “lossless” claim.
  3. [§V.B, Tables II–III] The speedup claim is heavily regime-dependent: Table II shows that for matrices between 2^20 and 2^25 nonzeros, only 10–16% of cases (64-bit, warm) achieve a speedup, and the warm-cache 32-bit numbers for annzpr ≤ 10 are near 1%. The paper does acknowledge the row-irregularity limitation in Section V.B, but the abstract’s phrasing “we achieve an SpMVM speedup for the majority of matrices with at least 2^25 nonzero entries” should state that this is for the largest matrices and depends on cache state and precision. This is more a framing issue than an error, but it affects how a reader interprets the headline.
minor comments (4)
  1. [§IV.D, Algorithm 3] Typographical/heading issues: “Decodingu” should be “Decoding”; Algorithm 3’s loop bound n/l − 1 implies n divisible by l, but Section IV.F allows padding; the pseudocode should use ceil(n/l) or explicitly mention padding before the loop.
  2. [§V.C] The sentence “the success numbers are uniformly increased compared to Table III” should refer to Table II; Table III is the cold-cache table being discussed.
  3. [§V.D, Fig. 9] The AlphaSparse comparison is preselected: Section V.D says the 265-matrix family was chosen as those for which CSR-dtANS improved by at least 10% over cuSPARSE in an early experiment, and speedups are reported on only 28 of 229 matrices. This is disclosed, but the abstract’s claim “we can improve over the AI-based multi-format AlphaSparse” should be qualified as an existence result on a favorable subset, not a general improvement.
  4. [§IV.E] The paper repeatedly promises code (“we provide our code as an open source C++/CUDA header library”, Abstract and Section IV.E) but supplies no link or artifact. Even for a paper whose focus is algorithmic, an available artifact is essential given that the encoder is otherwise unspecified.

Circularity Check

0 steps flagged

No circularity found: all quantitative claims are direct measurements against external baselines; dtANS parameter choices are fixed by algebraic equalities, not fitted to outcomes.

full rationale

The derivation chain is not circular. The central claims—compression ratios, SpMVM speedups, and the comparison against AlphaSparse—are direct measurements of the proposed format on the SuiteSparse collection against external baselines (cuSPARSE CSR/COO/SELL and AlphaSparse), not quantities derived from the paper's own definitions or fitted parameters. The dtANS design parameters are chosen to satisfy the stated algebraic equalities K^l >= W^o (K=2^12, W=2^32, o=3, l=8) and M^l <= W^f (M=2^8, f=2), which are construction constraints, not parameters fit to make benchmarks pass. Delta-encoding's entropy benefit is supported by simulations over standard random graph models with external citations; there are no self-citations. Flagged but not circular: Section IV.E omits the encoder implementation ('We only discuss encoding with dtANS on a high level due to lack of space...') and no repository URL is provided, which is a reproducibility and evidence gap rather than a re-import of the claimed conclusion. Likewise, the AlphaSparse comparison in Section V.D is restricted to a favorable subset ('This family was selected as those matrices for which CSR-dtANS improved in size and runtime by at least 10% over the best cuSPARSE format in an early experiment'), which is an acknowledged selection-bias caveat rather than a circular reduction. No step exhibits Eq. X = Eq. Y by construction or a fitted parameter renamed as a prediction.

Axiom & Free-Parameter Ledger

4 free parameters · 6 axioms · 0 invented entities

The central claims rest on (i) the memory-bound premise, (ii) a correctness black-box for ANS/tANS from the cited literature, (iii) an asserted transfer of delta-encoding benefits from random graph models to the whole SuiteSparse corpus, and (iv) hand-chosen implementation parameters (K, M, l, o, f, segment size) that satisfy algebraic equalities rather than being fitted to benchmark outcomes. No numerical constant is fitted to make the results pass; the success thresholds (2^15 nonzeros, 10/row, 2^25 nonzeros) are disclosed reporting filters, and the escape/table-construction policy ("approximate the exact distributions such that the expected total size is minimized", Section IV.F) is an under-specified algorithm whose quality directly drives the compression ratios.

free parameters (4)
  • K (coding table slots) = 4096
    Table size chosen as a power of two that "fit[s] in shared memory" and is "large enough for many symbols" (Section IV.D). Hand-picked design parameter; affects cross-entropy granularity and table memory (48-64 KB).
  • M (max per-symbol multiplicity) = 256
    Chosen so returned digits are at most 8 bits for "a convenient size for efficient computation" (Section IV.D). Trades achievable cross-entropy against number of unconditional loads.
  • Segment geometry (l, o, f) = l=8, o=3, f=2
    Chosen so K^l = W^o (2^96 = 2^96) and M^l = W^f (2^64 = 2^64) hold exactly for 32-bit words (Section IV.D). These equalities, not benchmark outcomes, determine the values.
  • Segment size in nonzeros = 4 nonzeros = 8 symbols
    Sets instruction-level parallelism of the decoder; tail handling designed around it (Section IV.B).
axioms (6)
  • standard math Shannon cross-entropy lower bound governs achievable compressed size (Eq. 1-2).
    Section III.B invokes Shannon's source coding theorem [22] to state that expected bits/symbol are bounded below by entropy H and approached by cross-entropy H'.
  • standard math ANS/tANS as described in [16] is a correct lossless codec.
    Sections III.D-E adopt Duda's construction (Algorithms 1-2) as a correctness black-box, then modify it into dtANS.
  • domain assumption SpMVM is inherently memory-bound, so reducing bytes moved translates into runtime gains.
    Section I: "SpMVM is inherently memory-bound, and thus the key to performance is efficient representation... reducing the amount of data movement overall." This premise justifies why decode cost can be traded for memory traffic.
  • domain assumption Delta-encoding of sorted column indices reduces entropy on real sparse matrices.
    Section IV.A supports this with three random graph models (Fig. 4, median of 3 runs); the transfer to the SuiteSparse corpus is assumed, not separately measured.
  • domain assumption One global symbol table per matrix adequately approximates the distribution of every row.
    Section IV.C: "the coding table... is obtained as in tANS by approximating the symbol distribution of the entire matrix". Heterogeneous matrices would pay higher cross-entropy.
  • domain assumption Best-of-(CSR, COO, SELL) from cuSPARSE is an adequate state-of-the-art comparator.
    Section V compares only 3 of the 7 cuSPARSE formats; Kokkos Kernels is excluded on the grounds that cuSPARSE's fastest format wins for >=2^20 nonzeros. The other 4 cuSPARSE formats (BSR, ELL, HYB, etc.) are not benchmarked.

pith-pipeline@v1.3.0-alltime-deepseek · 5098 in / 5714 out tokens · 211364 ms · 2026-08-02T19:31:11.624344+00:00 · methodology

0 comments
read the original abstract

We present a novel, practical approach to speed up sparse matrix-vector multiplication (SpMVM) on GPUs. The novel key idea is to apply lossless entropy coding to further compress the sparse matrix when stored in one of the commonly supported formats. Our method is based on dtANS, our new lossless compression method that improves the entropy coding technique of asymmetric numeral systems (ANS) specifically for fast parallel GPU decoding when used in tandem with SpMVM. We apply dtANS on the widely used CSR format and present extensive benchmarks on the SuiteSparse collection of matrices against the state-of-the-art cuSPARSE library. On matrices with at least 2^(15) entries and at least 10 entries per row on average, our compression reduces the matrix size over the smallest cuSPARSE format (CSR, COO and SELL) in almost all cases and up to 11.77 times. Further, we achieve an SpMVM speedup for the majority of matrices with at least 2^(25) nonzero entries. The best speedup is 3.48x. We also show that we can improve over the AI-based multi-format AlphaSparse in an experiment that is limited due to its extreme computation overhead. We provide our code as an open source C++/CUDA header library, which includes both compression and multiplication kernels.

Figures

Figures reproduced from arXiv: 2603.01915 by Emil Sch\"atzle, Markus P\"uschel, Tommaso Pegolotti.

Figure 1
Figure 1. Figure 1: Encoding into CSR-dtANS (left) and SpMVM on CSR [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Example for the CSR format with 6 nonzeros [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Example of entropy encoding with tANS steps are shown in [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Entropy reduction via delta-encoding for three random [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Mapping of data to threads and dtANS representation [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Matrix compression achieved with CSR-dtANS for [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Comparison of matrix size and SpMVM runtime [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Comparison of matrix size and SpMVM runtime [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Comparison of CSR and CSR-dtANS SpMVM runtime [PITH_FULL_IMAGE:figures/full_fig_p012_9.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

49 extracted references · 5 canonical work pages

  1. [1]

    A Tech- nique for Accelerating the Convergence of Restarted GMRES,

    A. H. Baker, E. R. Jessup, and T. Manteuffel, “A Tech- nique for Accelerating the Convergence of Restarted GMRES,” en,SIAM Journal on Matrix Analysis and Applications, vol. 26, no. 4, pp. 962–984, Jan. 2005,ISSN: 0895-4798, 1095-7162.DOI: 10 . 1137 / S0895479803422014 Accessed: Oct. 7, 2025. [Online]. Available: http : / / epubs . siam . org / doi / 10 . ...

    2005

  2. [2]

    The Block Lanczos Method for Computing Eigenvalues,

    G. Golub and R. Underwood, “The Block Lanczos Method for Computing Eigenvalues,” en, inMathemat- ical Software, Elsevier, 1977, pp. 361–377,ISBN: 978- 0-12-587260-7.DOI: 10 . 1016 / B978 - 0 - 12 - 587260 - 7 . 50018 - 2 Accessed: Oct. 7, 2025. [Online]. Avail- able: https : / / linkinghub . elsevier . com / retrieve / pii / B9780125872607500182

    1977

  3. [3]

    A Shifted Block Lanczos Algorithm for Solving Sparse Symmetric Generalized Eigenproblems,

    R. G. Grimes, J. G. Lewis, and H. D. Simon, “A Shifted Block Lanczos Algorithm for Solving Sparse Symmetric Generalized Eigenproblems,”SIAM J. Ma- trix Anal. Appl., vol. 15, no. 1, pp. 228–272, Jan. 1994, ISSN: 0895-4798.DOI: 10.1137/S0895479888151111 Accessed: Oct. 7, 2025. [Online]. Available: https://doi. org/10.1137/S0895479888151111

    work page doi:10.1137/s0895479888151111 1994

  4. [4]

    Sparsegpt: Massive lan- guage models can be accurately pruned in one-shot,

    E. Frantar and D. Alistarh, “Sparsegpt: Massive lan- guage models can be accurately pruned in one-shot,” inProceedings of the 40th International Conference on Machine Learning, ser. ICML’23, Honolulu, Hawaii, USA: JMLR.org, 2023

    2023

  5. [5]

    Dettmers, R

    T. Dettmers, R. Svirschevski, V . Egiazarian, D. Kuznedelev, E. Frantar, S. Ashkboos, A. Borzunov, T. Hoefler, and D. Alistarh,Spqr: A sparse-quantized representation for near-lossless llm weight compression,

  6. [6]

    R. I. for Advanced Computer Science (U.S.), Y . Saad, U. of Illinois at Urbana-Champaign. Center for Super- computing Research, and Development,SPARSKIT: a Basic Tool Kit for Sparse Matrix Computations(CSRD rpt). University of Illinois at Urbana-Champaign. Cen- ter for Supercomputing Research and Development [CSRD], 1990. [Online]. Available: https : / / ...

    1990

  7. [7]

    Performance optimizations and bounds for sparse matrix-vector multiply,

    R. Vuduc, J. Demmel, K. Yelick, S. Kamil, R. Nishtala, and B. Lee, “Performance optimizations and bounds for sparse matrix-vector multiply,” inSC ’02: Proceedings of the 2002 ACM/IEEE Conference on Supercomputing, 2002

    2002

  8. [8]

    Pattern-based sparse matrix representation for memory-efficient smvm kernels,

    M. Belgin, G. Back, and C. J. Ribbens, “Pattern-based sparse matrix representation for memory-efficient smvm kernels,” ser. ICS ’09, 2009

    2009

  9. [9]

    Accelerating sparse matrix computations via data compression,

    J. Willcock and A. Lumsdaine, “Accelerating sparse matrix computations via data compression,” inPro- ceedings of the 20th Annual International Conference on Supercomputing, ser. ICS ’06, Cairns, Queensland, Australia: Association for Computing Machinery, 2006, pp. 307–316,ISBN: 1595932828.DOI: 10 . 1145 / 1183401.1183444 [Online]. Available: https://doi.o...

    arXiv 2006

  10. [10]

    Exploiting compression opportunities to improve spmxv perfor- mance on shared memory systems,

    K. Kourtis, G. Goumas, and N. Koziris, “Exploiting compression opportunities to improve spmxv perfor- mance on shared memory systems,”ACM Trans. Archit. Code Optim., vol. 7, no. 3, Dec. 2011,ISSN: 1544-3566. DOI: 10 . 1145 / 1880037 . 1880041 [Online]. Available: https://doi.org/10.1145/1880037.1880041

    arXiv 2011

  11. [11]

    Ai and memory wall,

    A. Gholami, Z. Yao, S. Kim, C. Hooper, M. W. Ma- honey, and K. Keutzer, “Ai and memory wall,”IEEE Micro, vol. 44, no. 3, pp. 33–39, May 2024.DOI: 10. 1109 / MM . 2024 . 3373763 [Online]. Available: https : //doi.org/10.1109/MM.2024.3373763 [12]cuSPARSE cuda sparse matrix library, https : / / docs . nvidia.com/cuda/cusparse/, Accessed: 2025-10-06

    arXiv 2024

  12. [13]

    Alphasparse: Generating high performance spmv codes directly from sparse matrices,

    Z. Du, J. Li, Y . Wang, X. Li, G. Tan, and N. Sun, “Alphasparse: Generating high performance spmv codes directly from sparse matrices,” inProceedings of the In- ternational Conference on High Performance Comput- ing, Networking, Storage and Analysis, ser. SC ’22, Dal- las, Texas: IEEE Press, 2022,ISBN: 9784665454445

    2022

  13. [14]

    Frantar, S

    E. Frantar, S. Ashkboos, T. Hoefler, and D. Alistarh, Gptq: Accurate post-training quantization for genera- tive pre-trained transformers, 2023

    2023

  14. [15]

    J. Lin, J. Tang, H. Tang, S. Yang, W.-M. Chen, W.-C. Wang, G. Xiao, X. Dang, C. Gan, and S. Han,Awq: Activation-aware weight quantization for llm compres- sion and acceleration, 2024

    2024

  15. [16]

    Asymmetric numeral systems as close to capacity low state entropy coders,

    J. Duda, “Asymmetric numeral systems as close to capacity low state entropy coders,”CoRR, vol. abs/1311.2540, 2013. arXiv: 1311.2540. [Online]. Available: http://arxiv.org/abs/1311.2540

    Pith/arXiv arXiv 2013

  16. [17]

    The university of florida sparse matrix collection,

    T. A. Davis and Y . Hu, “The university of florida sparse matrix collection,”ACM Trans. Math. Softw., vol. 38, no. 1, Dec. 2011,ISSN: 0098-3500.DOI: 10 . 1145 / 2049662.2049663 [Online]. Available: https://doi.org/ 10.1145/2049662.2049663

    arXiv 2011

  17. [18]

    Chapter 14 - sparse matrix computation,

    W.-m. W. Hwu, D. B. Kirk, and I. El Hajj, “Chapter 14 - sparse matrix computation,” inProgramming Massively Parallel Processors (F ourth Edition), W.-m. W. Hwu, D. B. Kirk, and I. El Hajj, Eds., Fourth Edition, Morgan Kaufmann, 2023, pp. 311–329,ISBN: 978-0-323-91231- 0.DOI: https://doi.org/10.1016/B978-0-323-91231-0. 00010-0 [Online]. Available: https://...

    work page doi:10.1016/b978-0-323-91231-0 2023

  18. [19]

    Sparsity: Opti- mization framework for sparse matrix kernels,

    E.-J. Im, K. Yelick, and R. Vuduc, “Sparsity: Opti- mization framework for sparse matrix kernels,”Int. J. High Perform. Comput. Appl., vol. 18, no. 1, pp. 135– 158, Feb. 2004,ISSN: 1094-3420.DOI: 10 . 1177 / 1094342004041296 [Online]. Available: https://doi.org/ 10.1177/1094342004041296

    doi:10.1177/1094342004041296 2004

  19. [20]

    Au- tomatically tuning sparse matrix-vector multiplication for gpu architectures,

    A. Monakov, A. Lokhmotov, and A. Avetisyan, “Au- tomatically tuning sparse matrix-vector multiplication for gpu architectures,” inHigh Performance Embedded Architectures and Compilers, Y . N. Patt, P. Foglia, E. Duesterwald, P. Faraboschi, and X. Martorell, Eds., Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 111–125,ISBN: 978-3-642-11515-8

    2010

  20. [21]

    Entropy coding tech- niques,

    W. A. Pearlman and A. Said, “Entropy coding tech- niques,” inDigital Signal Compression: Principles and Practice. Cambridge University Press, 2011, pp. 41–76

    2011

  21. [22]

    A mathematical theory of communica- tion,

    C. E. Shannon, “A mathematical theory of communica- tion,”The Bell System Technical Journal, vol. 27, no. 3, pp. 379–423, 1948.DOI: 10.1002/j.1538- 7305.1948. tb01338.x

    arXiv 1948

  22. [23]

    Generalized kraft inequality and arith- metic coding,

    J. J. Rissanen, “Generalized kraft inequality and arith- metic coding,”IBM Journal of Research and Develop- ment, vol. 20, no. 3, pp. 198–203, 1976.DOI: 10.1147/ rd.203.0198

    1976

  23. [24]

    A Method for the Construction of Minimum-Redundancy Codes,

    D. A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes,”Proceedings of the IRE, vol. 40, no. 9, pp. 1098–1101, Sep. 1952,ISSN: 2162- 6634.DOI: 10.1109/JRPROC.1952.273898 Accessed: Oct. 7, 2025. [Online]. Available: https : / / ieeexplore . ieee.org/document/4051119

    arXiv 1952

  24. [25]

    On random graphs i,

    P. Erd ¨os and A. R ´enyi, “On random graphs i,”Publica- tiones Mathematicae Debrecen, vol. 6, p. 290, 1959

    1959

  25. [26]

    Collective dynamics of ‘small-world’ networks,

    D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,”Nature, vol. 393, no. 6684, pp. 440–442, Jun. 1998,ISSN: 1476-4687.DOI: 10 . 1038 / 30918 [Online]. Available: https : / / doi . org / 10 . 1038/30918

    1998

  26. [27]

    Emergence of scaling in random networks,

    A.-L. Barab ´asi and R. Albert, “Emergence of scaling in random networks,”Science, vol. 286, no. 5439, pp. 509– 512, 1999.DOI: 10.1126/science.286.5439.509 eprint: https://www.science.org/doi/pdf/10.1126/science.286. 5439.509. [Online]. Available: https://www.science.org/ doi/abs/10.1126/science.286.5439.509

    doi:10.1126/science.286.5439.509 1999

  27. [28]

    Rajamanickam, S

    S. Rajamanickam, S. Acer, L. Berger-Vergiat, V . Dang, N. Ellingwood, E. Harvey, B. Kelley, C. R. Trott, J. Wilke, and I. Yamazaki,Kokkos kernels: Performance portable sparse/dense linear algebra and graph kernels,

  28. [29]

    High-precision floating-point arithmetic in scientific computation,

    D. Bailey, “High-precision floating-point arithmetic in scientific computation,”Computing in Science & Engi- neering, vol. 7, no. 3, pp. 54–61, 2005.DOI: 10.1109/ MCSE.2005.52

    2005

  29. [30]

    VNEC: A Vectorized Non-Empty Column Format for SpMV on CPUs,

    L. Wang, H. Jia, L. Xu, C. Wei, K. Li, X. Jiang, and Y . Zhang, “VNEC: A Vectorized Non-Empty Column Format for SpMV on CPUs,” in2024 IEEE Interna- tional Parallel and Distributed Processing Symposium (IPDPS), ISSN: 1530-2075, May 2024, pp. 14–25.DOI: 10.1109/IPDPS57955.2024.00011 Accessed: Oct. 7,

    arXiv 2075

  30. [31]

    Vec- torizing Sparse Matrix Computations with Partially- Strided Codelets,

    K. Cheshmi, Z. Cetinic, and M. M. Dehnavi, “Vec- torizing Sparse Matrix Computations with Partially- Strided Codelets,” inSC22: International Conference for High Performance Computing, Networking, Storage and Analysis, ISSN: 2167-4337, Nov. 2022, pp. 1–15. DOI: 10.1109/SC41404.2022.00037 Accessed: Oct. 7,

    Pith/arXiv arXiv 2022

  31. [32]

    Div: An index & value compression method for spmv on large matrices,

    D. Galanopoulos, P. Mpakos, P. Anastasiadis, N. Koziris, and G. Goumas, “Div: An index & value compression method for spmv on large matrices,” ser. ICS ’25, Association for Computing Machinery, 2025, pp. 705–717,ISBN: 9798400715372.DOI: 10 . 1145/3721145.3725767 [Online]. Available: https://doi. org/10.1145/3721145.3725767

    arXiv 2025

  32. [33]

    Unified compilation for lossless compression and sparse com- puting,

    D. Donenfeld, S. Chou, and S. Amarasinghe, “Unified compilation for lossless compression and sparse com- puting,” in2022 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), 2022, pp. 205–216.DOI: 10.1109/CGO53902.2022.9741282

    arXiv 2022

  33. [34]

    Available: https://ieeexplore.ieee.org/ document/10046127/

    [Online]. Available: https://ieeexplore.ieee.org/ document/10046127/

    arXiv

  34. [35]

    Improving the performance of the sparse matrix vector product with gpus,

    F. V ´azquez, G. Ortega, J. Fern ´andez, and E. Garz ´on, “Improving the performance of the sparse matrix vector product with gpus,” in2010 10th IEEE International Conference on Computer and Information Technology, 2010.DOI: 10.1109/CIT.2010.208

    work page doi:10.1109/cit.2010.208 2010

  35. [36]

    Fast sparse matrix-vector mul- tiplication on gpus for graph applications,

    A. Ashari, N. Sedaghati, J. Eisenlohr, S. Parthasarath, and P. Sadayappan, “Fast sparse matrix-vector mul- tiplication on gpus for graph applications,” inSC ’14: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2014, pp. 781–792.DOI: 10.1109/SC.2014.69

    doi:10.1109/sc.2014.69 2014

  36. [37]

    Implementing sparse matrix- vector multiplication on throughput-oriented proces- sors,

    N. Bell and M. Garland, “Implementing sparse matrix- vector multiplication on throughput-oriented proces- sors,” inProceedings of the Conference on High Perfor- mance Computing Networking, Storage and Analysis, ser. SC ’09, Portland, Oregon: Association for Com- puting Machinery, 2009,ISBN: 9781605587448.DOI: 10.1145/1654059.1654078 [Online]. Available: h...

    arXiv 2009

  37. [39]

    Implementing a sparse matrix vector product for the sell-c / sell-c-σ formats on nvidia gpus,

    H. Anzt, S. Tomov, and J. J. Dongarra, “Implementing a sparse matrix vector product for the sell-c / sell-c-σ formats on nvidia gpus,” 2014

    2014

  38. [40]

    Efficient sparse matrix- vector multiplication on gpus using the csr storage format,

    J. L. Greathouse and M. Daga, “Efficient sparse matrix- vector multiplication on gpus using the csr storage format,” inSC ’14: Proceedings of the International Conference for High Performance Computing, Network- ing, Storage and Analysis, 2014, pp. 769–780.DOI: 10. 1109/SC.2014.68

    2014

  39. [41]

    Clspmv: A cross-platform opencl spmv framework on gpus,

    B.-Y . Su and K. Keutzer, “Clspmv: A cross-platform opencl spmv framework on gpus,” inProceedings of the 26th ACM International Conference on Supercomput- ing, ser. ICS ’12, San Servolo Island, Venice, Italy: As- sociation for Computing Machinery, 2012, pp. 353–364, ISBN: 9781450313162.DOI: 10.1145/2304576.2304624 [Online]. Available: https://doi.org/10.1...

    arXiv 2012

  40. [42]

    Automatic selection of sparse ma- trix representation on gpus,

    N. Sedaghati, T. Mu, L.-N. Pouchet, S. Parthasarathy, and P. Sadayappan, “Automatic selection of sparse ma- trix representation on gpus,” inProceedings of the 29th ACM on International Conference on Supercomputing, ser. ICS ’15, Newport Beach, California, USA: Asso- ciation for Computing Machinery, 2015, pp. 99–108, ISBN: 9781450335591.DOI: 10.1145/275120...

    arXiv 2015

  41. [43]

    Model-driven autotuning of sparse matrix-vector multiply on gpus,

    J. W. Choi, A. Singh, and R. W. Vuduc, “Model-driven autotuning of sparse matrix-vector multiply on gpus,” inProceedings of the 15th ACM SIGPLAN Sympo- sium on Principles and Practice of Parallel Program- ming, ser. PPoPP ’10, Bangalore, India: Association for Computing Machinery, 2010, pp. 115–126,ISBN: 9781605588773.DOI: 10 . 1145 / 1693453 . 1693471 [O...

    work page doi:10.1145/1693453 2010

  42. [44]

    Tilespmv: A tiled algorithm for sparse matrix- vector multiplication on gpus,

    Y . Niu, Z. Lu, M. Dong, Z. Jin, W. Liu, and G. Tan, “Tilespmv: A tiled algorithm for sparse matrix- vector multiplication on gpus,” in2021 IEEE Interna- tional Parallel and Distributed Processing Symposium (IPDPS), 2021, pp. 68–78.DOI: 10.1109/IPDPS49936. 2021.00016

    arXiv 2021

  43. [45]

    Nm-spmm: Accelerating matrix multiplication using n:m sparsity with gpgpu,

    C. Ma, D. Wu, Z. Deng, J. Chen, X. Huang, J. Meng, W. Zhu, B. Wang, A. C. Zhou, P. Chen, M. Deng, Y . Wei, S. Feng, and Y . Pan, “Nm-spmm: Accelerating matrix multiplication using n:m sparsity with gpgpu,” in2025 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2025, pp. 926–937.DOI: 10.1109/ IPDPS64566.2025.00087

    arXiv 2025

  44. [46]

    Bridging the gap between deep learning and sparse matrix format selection,

    Y . Zhao, J. Li, C. Liao, and X. Shen, “Bridging the gap between deep learning and sparse matrix format selection,”SIGPLAN Not., vol. 53, no. 1, pp. 94–108, Feb. 2018,ISSN: 0362-1340.DOI: 10.1145/3200691. 3178495 [Online]. Available: https://doi.org/10.1145/ 3200691.3178495

    arXiv 2018

  45. [47]

    Dcsr: A memory-efficient sparse matrix representation for parallel neural network inference,

    E. Trommer, B. Waschneck, and A. Kumar, “Dcsr: A memory-efficient sparse matrix representation for parallel neural network inference,” in2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD), Munich, Germany: IEEE Press, 2021, pp. 1– 9.DOI: 10.1109/ICCAD51958.2021.9643506 [Online]. Available: https://doi.org/10.1109/ICCAD51958.2021. 9643506

    arXiv 2021

  46. [49]

    In-memory data compression for sparse matrices,

    O. S. Lawlor, “In-memory data compression for sparse matrices,” inProceedings of the 3rd Work- shop on Irregular Applications: Architectures and Al- gorithms, ser. IA¡sup¿3¡/sup¿ ’13, Denver, Colorado: Association for Computing Machinery, 2013,ISBN: 9781450325035.DOI: 10 . 1145 / 2535753 . 2535758 [Online]. Available: https://doi.org/10.1145/2535753. 2535758

    work page doi:10.1145/2535753 2013

  47. [2021]

    [Online]

    arXiv: 2103.11991[cs.MS]. [Online]. Avail- able: https://arxiv.org/abs/2103.11991

    Pith/arXiv arXiv

  48. [2023]

    [Online]

    arXiv: 2306.03078[cs.CL]. [Online]. Avail- able: https://arxiv.org/abs/2306.03078

    Pith/arXiv arXiv

  49. [2025]

    Available: https://ieeexplore.ieee.org/ document/10579118/

    [Online]. Available: https://ieeexplore.ieee.org/ document/10579118/

    arXiv