Pith. sign in

REVIEW 4 major objections 6 minor 1 cited by

Improving SpGEMM Performance Through Matrix Reordering and Cluster-wise Computation

T0 review · 4 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Grouping similar rows, found cheaply via one sparse matrix-times-transpose product, and computing cluster-wise speeds up SpGEMM by 1.39x on average with amortizable preprocessing.

desk verdict Practical and reproducible SpGEMM reordering study; the core speedup is real, but the hand-set hyperparameters need a sensitivity check to be fully convincing. read the letter →

arxiv 2507.21253 v1 pith:MFXO2FDY submitted 2025-07-28 cs.DC

Abdullah Al Raqibul Islam , Helen Xu , Dong Dai , Ayd{i}n Buluç This is my paper
classification cs.DC MSC 65F5065Y0568W10
keywords sparsematrixmultiplicationSpGEMMreorderinghierarchicalclusteringCSR_Clusterformatcachelocalityshared-memoryparallelismcluster-wisecomputation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper is trying to establish that SpGEMM, the sparse matrix-matrix multiplication kernel behind many graph and scientific workloads, can be made significantly faster by reordering rows into clusters of similar rows and then computing cluster-by-cluster rather than row-by-row. Its claim is that similar rows can be identified cheaply by one sparse multiplication of the matrix by its own transpose, and that processing the resulting clusters with a new storage format keeps rows of the second input matrix in cache long enough to be reused. The measured result is a 1.39x average speedup, up to 4.68x, on 110 test matrices, with preprocessing costing less than 20x one SpGEMM on about 90% of inputs. The paper also establishes that reordering and clustering are independent optimizations that sometimes compose and sometimes do not.

What carries the argument

Three pieces carry the argument. The first is candidate generation: A is copied with all values set to 1, the product A times A-transpose is computed, and only the top K entries by set-overlap similarity are retained, converting expensive hashing-based row similarity into one SpGEMM. The second is an agglomerative clustering step that greedily unions those candidate pairs under a similarity threshold (jacc_th = 0.3) and a maximum cluster size (max_cluster_th = 8), producing variable-length groups of similar rows. The third is the CSR_Cluster sparse format, which stores each cluster's nonzeros grouped by column with cluster pointer and cluster-size arrays, together with a cluster-wise SpGEMM dataflow that keeps the accessed rows of B resident in cache while all rows of a cluster are processed. The hand-set similarity threshold and cluster-size cap are what convert structural overlap into usable clusters, and the format is what converts clusters into a memory-access pattern.

What would settle it

On the same set of 110 matrices, sweep the similarity threshold between 0.1 and 0.6 and the maximum cluster size between 4 and 32 and measure the geometric-mean speedup and preprocessing fraction. If no setting reproduces the reported 1.39x average with preprocessing under 20x a single SpGEMM, or if replacing the top-K candidates with randomly chosen row pairs yields the same speedups, then similarity-driven clustering is not the cause of the improvement.

Watch

Extended reading notes

Core claim

The central claim, stated as the authors would state it, is that the expensive locality-sensitive hashing used in earlier hierarchical clustering can be replaced by a single sparse multiplication A times A-transpose whose nonzeros count row-pair overlaps, and that these overlaps are enough to form clusters whose joint processing improves reuse of B rows. In this scheme the matrix A's values are reset to 1, the top-K row pairs by a set-overlap similarity are fed to a greedy union step, and the resulting clusters are stored in a CSR_Cluster format that groups nonzeros by column within each cluster. Cluster-wise computation then iterates over clusters of A instead of single rows, so each B row that is pulled into cache serves every row in the cluster simultaneously. The paper reports that this hierarchical clustering speeds up SpGEMM by 1.39x in geometric mean across 110 matrices from a standard sparse-matrix collection, with a best case of 4.68x, and that the same mechanisms transfer to square-times-tall-skinny multiplication where the reordered A is reused across many B matrices.

Load-bearing premise

The method assumes the top-K row pairs found by one sparse A times A-transpose product really identify rows whose joint processing improves cache reuse, and that the fixed similarity threshold of 0.3 and maximum cluster size of 8 work across most matrices; neither assumption is ablated in the paper.

Editorial extensions

If this is right

  • Applications that run many SpGEMMs on the same matrix, such as iterative graph algorithms, can amortize the preprocessing: on about 90% of inputs the clustering cost is repaid within 20 SpGEMM invocations.
  • Graph and hypergraph partitioning reorderings deliver the largest speedups (geomean 1.77x for hypergraph partitioning) but cost far more preprocessing, so hierarchical clustering sits at a different point on the cost-performance curve.
  • Because the clustered format is decoupled from reordering, users can apply a strong reordering first and then cluster; this combination improves performance on roughly 80% of the test matrices in the study.
  • CSR_Cluster frequently stores fewer column indices than plain CSR, so cluster-wise computation can use less memory than the baseline while also running faster; its memory overhead stays below 2x in over 80% of cases.
  • Reordering benefits transfer across different second matrices: the same reordered A speeds up square-times-tall-skinny SpGEMM, indicating the gain comes from row similarity in A rather than from B's shape.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The similarity threshold of 0.3 and cluster-size cap of 8 are not swept in the paper, so a natural extension is to test whether tuning them per matrix family pushes the 70% improvement rate higher or whether the method is insensitive to them.
  • Because the candidate-generation step is itself a SpGEMM on structural data, the same A times A-transpose product could be reused by other kernels that share the same matrix, such as sparse-matrix times dense-matrix or sampling kernels, making the preprocessing cheaper when several kernels run together.
  • The study covers row-wise SpGEMM on multicore CPUs; testing the same cluster-wise dataflow on GPU tiled variants or distributed-memory SpGEMM would show whether the cache-reuse argument survives different memory hierarchies.
  • The measured tradeoff curves could feed a learned per-input selector, which the paper itself flags as future work, choosing among reordering, clustering, and their combination automatically.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 6 minor

Summary. The paper proposes hierarchical clustering for SpGEMM, combining a new row reordering scheme (based on candidate row pairs from SpGEMM(A,A^T)) with a new sparse storage format (CSR_Cluster) and a cluster-wise computation pattern that improves reuse of rows of the second input matrix B. It also decouples reordering from clustering, enabling either optimization to be applied independently. The empirical evaluation covers 110 SuiteSparse matrices, 10 reordering algorithms, and 3 clustering schemes on two workloads: squaring a sparse matrix and multiplying a square sparse matrix by tall-skinny BFS frontier matrices. The central claim is a 1.39x geometric mean speedup for hierarchical clustering over a row-wise SpGEMM baseline, with speedups up to 4.68x, improvements on about 70% of inputs, and preprocessing cost below 20x a single SpGEMM on about 90% of inputs.

Significance. If the empirical claims hold, the paper makes a useful contribution to shared-memory SpGEMM optimization, particularly for workloads where the same matrix A is multiplied many times (e.g., betweenness centrality and Markov clustering). The strengths of the paper are its unusually broad benchmark suite, the decoupling of reordering and clustering into independent optimizations, the public code release, and the explicit analysis of preprocessing amortization and memory overhead. The comparison of 10 reordering algorithms in the SpGEMM context is a worthwhile addition to the literature, which has mostly focused on SpMV. However, the central speedup and overhead claims are conditional on several hand-set parameters and on the authors' own baseline implementation, so the significance is real but not yet fully established.

major comments (4)
  1. [Section 3.2, Section 3.3, Algorithm 3] The method depends on several unablated hand-set parameters: the Jaccard threshold jacc_th=0.3, the maximum cluster size max_cluster_th=8, and the derived candidate count topk = max_cluster_th - 1 used in SpGEMM_TopK. These parameters directly determine which row pairs are considered similar and how large clusters can grow, and therefore directly shape the reported 1.39x geomean speedup and the overhead claim in Section 4.5. The paper provides no parameter sweep, no robustness analysis, and no sensitivity discussion. The authors should at least report performance for a range of jacc_th and max_cluster_th values on a representative subset of matrices, or provide evidence that the results are stable across reasonable parameter choices.
  2. [Section 4.1, Section 4.2] The baseline is the authors' own row-wise SpGEMM implementation using a hash-table accumulator, and no comparison is made against a production or highly optimized SpGEMM library such as Intel MKL, Kokkos, CombBLAS, or the implementation of Nagasaka et al. [40]. Since the paper claims to 'speed up SpGEMM,' the practical significance of the speedup depends on how competitive the baseline is. The authors should validate their row-wise baseline against a state-of-the-art implementation on at least a representative subset of the 110 matrices, or clearly scope the claim as being relative to their own row-wise kernel.
  3. [Section 4.2, Table 2, Figure 8] All performance numbers are reported as the mean of 10 runs, but no variance, confidence intervals, or statistical tests are provided. This is important because the claim that hierarchical clustering 'improves performance on 70% of inputs' is a per-matrix binary outcome, and benchmark noise near the 1.0 speedup threshold could materially change that fraction. The authors should report standard deviations or min/max values, and ideally provide a per-matrix speedup distribution or a statistical comparison between methods.
  4. [Section 3.1, Section 4.5] The CSR_Cluster format introduces placeholder entries when rows in a cluster do not share a column, and Algorithm 1 iterates over these placeholders. Section 4.5 quantifies the memory overhead of this padding, but not its computational cost. The slowdowns observed for some matrices (e.g., Figure 8) may be partly explained by placeholder iteration overhead, and the paper claims cluster-wise computation is beneficial overall without characterizing this cost. The authors should report the fraction of placeholder entries and its correlation with observed speedups or slowdowns.
minor comments (6)
  1. [Abstract] The abstract contains a typo: 'withhierarchical' should be 'with hierarchical'.
  2. [Algorithm 1] The indexing in lines 5-6 is confusing: the variable 'l' appears in 'a_ikl' and 'c_ijl' without being defined in the loop structure, and the update looks like it should be a sparse accumulator update rather than an element-wise indexed assignment. Please clarify the notation.
  3. [Algorithm 2] In line 6, the equality check uses a single equals sign. Since this is pseudocode it is understandable, but using '==' or making the condition explicit would avoid confusion with assignment.
  4. [Table 2] The 'Best Reord.' row appears to be an oracle result (the best reordering per matrix). This should be stated explicitly in the caption or text so that readers do not interpret it as a single algorithm's performance.
  5. [Section 4.5, Figure 10] The sentence 'about 50% of cases requiring at least 20 SpGEMM iterations to amortize the overhead' is ambiguous about the denominator. Please clarify whether 'cases' means all matrices, only matrices where reordering improves performance, or only matrices where reordering is applied.
  6. [Section 4.4, Table 3] The tall-skinny evaluation is limited to 10 hand-picked datasets that were selected based on their A^2 performance. This selection bias should be acknowledged in the main text, and ideally the authors should add a short discussion of how the results might generalize.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: speedup claims are measured against an independent row-wise baseline; the only self-referential element is using SpGEMM(A,A^T) in preprocessing, which is a cost-accounting concern, not a derivation collapse.

full rationale

This is an empirical systems paper rather than a formal derivation. The central claim of 1.39x average speedup for hierarchical cluster-wise SpGEMM is a measured ratio between the proposed CSR_Cluster kernel and a row-wise Gustavson baseline in original matrix order, using an independently published hashtable accumulator [40]. The clustering and reordering algorithms are heuristics with fixed hand-set thresholds (jacc_th=0.3, max_cluster_th=8); no parameter is fitted to the benchmark set, and the reported speedups are not predictions generated from a model that bakes in the answer. The clustering preprocessing does invoke an SpGEMM (A times A^T) to discover similar rows; for the A^2 workload on symmetric matrices this can compute the same product as the target, and that cost is included in the 'low preprocessing cost' figure, but this affects cost accounting rather than making the measured kernel speedup equivalent to the input by construction. Comparisons against HP, GP, RCM, and other reorderers are external benchmarks. No load-bearing self-citation chain or uniqueness theorem is used; prior work [32] is cited for background and is explicitly modified. The unablated thresholds are an external-validity risk, not circularity.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The central claim rests on several hand-set hyperparameters (jacc_th, max_cluster_th, topK, fixed cluster size) and on the representativeness of the dataset and baseline. No invented physical or mathematical entities are introduced; CSR_Cluster is an implemented data structure whose evidence is the paper's benchmarks, so it is not listed as an invented entity.

free parameters (5)
  • jacc_th (Jaccard similarity threshold) = 0.3
    Used in Algorithm 2 and Algorithm 3 to decide cluster boundaries; fixed without sensitivity analysis in Section 3.2.
  • max_cluster_th (maximum cluster size) = 8
    Limits cluster size in variable-length clustering and indirectly sets topK; hand-chosen in Section 3.2.
  • topK (number of candidate row pairs) = 7
    Set to max_cluster_th - 1 in Algorithm 3; controls how many similar pairs from SpGEMM(A, A^T) are retained.
  • fixed-length cluster size = Not reported, varies per matrix
    Section 3.2 says the number of rows per cluster may vary across matrices depending on diagonal-block structure, but the experiments do not state how it was selected.
  • Dataset inclusion thresholds = 8 million to 10 billion nonzeros
    Selection criteria in Section 4.1 constrain the evaluation set; speedups are reported only for this population.
assumptions (4)
  • domain assumption Reset values of A to 1 so SpGEMM(A, A^T) output counts overlapping nonzeros between rows.
    This structural-similarity proxy underpins hierarchical clustering; the paper does not prove it predicts cache reuse better than other similarity measures. Location: Algorithm 3, Section 3.3.
  • ad hoc to paper The top-K candidate pairs and representative-row Jaccard comparisons produce clusters that improve B-row reuse.
    The clustering heuristic is specific to this paper and its parameters; no independent validation is provided. Location: Sections 3.2 and 3.3.
  • domain assumption Row-wise SpGEMM with hashtable sparse accumulator in original order is a fair baseline for practical speedup.
    The baseline is the authors' own implementation; established production libraries are not compared. Location: Section 4.1.
  • domain assumption The SuiteSparse selection criteria yield a representative sample of SpGEMM workloads.
    Selection of square, large matrices with group-level exclusions may bias results towards block-structured inputs. Location: Section 4.1 Datasets.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improving SpGEMM Performance Through Matrix Reordering and Cluster-wise Computation." pith.science (2026). https://pith.science/paper/MFXO2FDY

@misc{pith2026250721253,
  author       = {Pith},
  title        = {Pith review of: Improving SpGEMM Performance Through Matrix Reordering and Cluster-wise Computation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MFXO2FDY}},
  note         = {Machine review of arXiv:2507.21253}
}
read the original abstract

Sparse matrix-sparse matrix multiplication (SpGEMM) is a key kernel in many scientific applications and graph workloads. Unfortunately, SpGEMM is bottlenecked by data movement due to its irregular memory access patterns. Significant work has been devoted to developing row reordering schemes towards improving locality in sparse operations, but prior studies mostly focus on the case of sparse-matrix vector multiplication (SpMV). In this paper, we address these issues with hierarchical clustering for SpGEMM that leverages both row reordering and cluster-wise computation to improve reuse in the second input (B) matrix with a novel row-clustered matrix format and access pattern in the first input (A) matrix. We find that hierarchical clustering can speed up SpGEMM by 1.39x on average with low preprocessing cost (less than 20x the cost of a single SpGEMM on about 90% of inputs). Furthermore, we decouple the reordering algorithm from the clustered matrix format so they can be applied as independent optimizations. Additionally, this paper sheds light on the role of both row reordering and clustering independently and together for SpGEMM with a comprehensive empirical study of the effect of 10 different reordering algorithms and 3 clustering schemes on SpGEMM performance on a suite of 110 matrices. We find that reordering based on graph partitioning provides better SpGEMM performance than existing alternatives at the cost of high preprocessing time. The evaluation demonstrates that the proposed hierarchical clustering method achieves greater average speedup compared to other reordering schemes with similar preprocessing times.

Figures

Figures reproduced from arXiv: 2507.21253 by the authors.

Figure 1
Figure 1. Basic SpGEMM on row order (Gustavson, 1978) [ [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Speedup of row-wise SpGEMM after reordering, relative to the original matrix order. Fixed-length Cluster Variable-length Cluster 10−1 100 101 102 Speedup Original Shuffled Rabbit AMD RCM ND GP HP Gray Degree SlashBurn Hierarchical [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Cluster-wise SpGEMM with reordering, relative to row￾wise SpGEMM performance on original order. the context of SpGEMM. Without loss of generality, we focus on the row-wise SpGEMM where clustering and reordering are both applied to the 𝐴 matrix. For cluster-wise computation, we study three schemes to com￾bine the computation of multiple rows of the 𝐴 matrix to improve locality of reference to the 𝐵 matrix. First, we … view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Sparse matrix of Figure 1 in CSR format. [PITH_FULL_IMAGE:figures/full_fig_p003_4.png]
Figure 5
Figure 5. Figure 5: Clustering without changing order. Algorithm 1 ClusterWise_SpGEMM 1: // set matrix 𝐶 to ∅; 𝐶 in CSR_Cluster format 2: for all 𝑎𝑖∗ in matrix 𝐴 in parallel do 3: for all 𝑎𝑖𝑘 in cluster 𝑎𝑖∗ do 4: for all 𝑏𝑘 𝑗 in row 𝑏𝑘∗ do 5: for all 𝑎𝑖𝑘𝑙 in col 𝑎𝑖𝑘 do 6: 𝑐𝑖𝑗𝑙 ← 𝑐𝑖𝑗𝑙 + 𝑎𝑖…
Figure 6
Figure 6. Figure 6: Sparse matrix of Fig. 5 in [PITH_FULL_IMAGE:figures/full_fig_p005_6.png]
Figure 7
Figure 7. Figure 7: Hierarchical clustering. of the matrix. In such cases, variable-length clustering performs suboptimally, creating an excessive number of small clusters. Although row reordering using existing algorithms (discussed in Section 2) may achieve similar objectives, it introd…
Figure 8
Figure 8. Figure 8: Cluster-wise SpGEMM performance across selected datasets, relative to the row-wise SpGEMM on original matrix order. from BFS frontiers produced by CombBLAS [11] during BC compu￾tations. As the number of frontiers varies among datasets, we only take the first 10 forward…
Figure 9
Figure 9. Figure 9: Row-wise SpGEMM performance across selected datasets and reordering algorithms, relative to the original matrix order. fact that the effectiveness of reordering in SpGEMM is closely tied to the sparsity pattern of the input matrix. In contrast, algorithms such as Shuff…
Figure 10
Figure 10. Figure 10: Performance profile of the overhead of reordering. For each point (x,y) in this plot, the cost of reordering is amortized after x SpGEMM iterations for y fraction of input problems. iterations to amortize the overhead. Gray, AMD and ND reorderings strike a moderate ba…
Figure 11
Figure 11. Figure 11: Memory overhead in cluster-wise SpGEMM relative to row-wise SpGEMM. resulting in increased padding. Hierarchical clustering strikes a bal￾ance between these two, benefiting from reordering similar rows closer together to improve memory efficiency. Interestingly, in ma…

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. SparseDitto: Customizing GPU Kernels for Different Sparsity Patterns with LLM-Based Agentic System

    cs.DC 2026-08 conditional novelty 6.0 of 10

    SparseDitto uses LLM agents guided by structural matrix features and target-GPU measurements to generate custom CUDA kernels for SpMV, SpMM, and SpGEMM, beating cuSPARSE by 2.68x to 2.79x on average.

Reference graph

Works this paper leans on

54 extracted references · 42 canonical work pages · cited by 1 Pith paper

  1. [32]

    Peng Jiang, Changwan Hong, and Gagan Agrawal. 2020. A novel data trans- formation and execution strategy for accelerating sparse matrix multiplica- tion on GPUs. In Proceedings of the 25th ACM SIGPLAN Symposium on Prin- ciples and Practice of Parallel Programming (San Diego, California) (PPoPP ’20). Association for Computing Machinery, New York, NY, USA, ...

    arXiv 2020

  2. [40]

    Yusuke Nagasaka, Satoshi Matsuoka, Ariful Azad, and Aydın Buluç. 2018. High- Performance Sparse Matrix-Matrix Products on Intel KNL and Multicore Archi- tectures. In Proceedings of the 47th International Conference on Parallel Process- ing Companion. ACM, Eugene OR USA, 1–10. https://doi.org/10.1145/3229710. 3229720

    work page doi:10.1145/3229710 2018

  3. [1]

    [n. d.]. SparCity: An Optimization and Co-design Framework for Sparse Compu- tation. https://github.com/sparcityeu

    work page

  4. [2]

    Sandeep R Agrawal, Christopher M Dee, and Alvin R Lebeck. 2016. Exploiting accelerators for efficient high dimensional similarity search. ACM SIGPLAN Notices 51, 8 (2016), 1–12

    work page 2016

  5. [3]

    Patrick R Amestoy, Timothy A Davis, and Iain S Duff. 2004. Algorithm 837: AMD, an approximate minimum degree ordering algorithm. ACM Transactions on Mathematical Software (TOMS) 30, 3 (2004), 381–388

    work page 2004

  6. [4]

    Jun Arai, Hiroyuki Shiokawa, Takuya Yamamuro, Masashi Onizuka, and Shinya Iwamura. [n. d.]. Rabbit Order: Just-in-time Parallel Reordering for Fast Graph Analysis. https://github.com/araij/rabbit_order

    work page

  7. [5]

    Jun Arai, Hiroyuki Shiokawa, Takuya Yamamuro, Masashi Onizuka, and Shinya Iwamura. 2016. Rabbit Order: Just-in-Time Parallel Reordering for Fast Graph Analysis. In Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 22–31. https://doi.org/10.1109/IPDPS.2016. 15

    doi:10.1109/ipdps.2016 2016

  8. [6]

    Ariful Azad, Aydin Buluç, and John Gilbert. 2015. Parallel triangle counting and enumeration using matrix algebra. In 2015 IEEE International Parallel and Distributed Processing Symposium Workshop. IEEE, 804–811

    work page 2015

Show all 54 references
  1. [7]

    Ariful Azad, Georgios A Pavlopoulos, Christos A Ouzounis, Nikos C Kyrpides, and Aydin Buluç. 2018. HipMCL: a high-performance parallel implementation of the Markov clustering algorithm for large-scale networks. Nucleic acids research 46, 6 (2018), e33–e33

    2018

  2. [8]

    Vignesh Balaji, Neal C Crago, Aamer Jaleel, and Stephen W Keckler. 2023. Community-based matrix reordering for sparse linear algebra optimization. In 2023 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). IEEE, 214–223

    2023

  3. [9]

    Grey Ballard, Christopher Siefert, and Jonathan Hu. 2016. Reducing communi- cation costs for sparse matrix multiplication within algebraic multigrid. SIAM Journal on Scientific Computing 38, 3 (2016), C203–C231

    2016

  4. [10]

    D. Bates. 2006. https://sparse.tamu.edu/Bates

    2006

  5. [11]

    Aydın Buluç and John R Gilbert. 2011. The Combinatorial BLAS: Design, im- plementation, and applications. The International Journal of High Performance Computing Applications 25, 4 (2011), 496–509

    2011

  6. [12]

    Andrew Canning, Giulia Galli, Francesco Mauri, Alessandro De Vita, and Roberto Car. 1996. O(N) tight-binding molecular dynamics on massively parallel comput- ers: an orbital decomposition approach. Computer Physics Communications 94, 2-3 (1996), 89–102

    1996

  7. [13]

    Catalyurek and Cevdet Aykanat

    Umit V. Catalyurek and Cevdet Aykanat. 1999. Hypergraph-Partitioning- Based Decomposition for Parallel Sparse-Matrix Vector Multiplication. IEEE Transactions on Parallel and Distributed Systems 10, 7 (1999), 673–693. https: //doi.org/10.1109/71.780863

    1999 doi

  8. [14]

    Jou-An Chen, Hsin-Hsuan Sung, Ruifeng Zhang, Ang Li, and Xipeng Shen

  9. [15]

    Elizabeth Cuthill and James McKee. 1969. Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 1969 24th national conference . 157–172

    1969

  10. [16]

    Davis and Yifan Hu

    Timothy A. Davis and Yifan Hu. 2011. The university of Florida sparse matrix collection. ACM Trans. Math. Softw. 38, 1, Article 1 (Dec. 2011), 25 pages. https: //doi.org/10.1145/2049662.2049663

    2011

  11. [17]

    Feldmann, R

    P. Feldmann, R. Melville, and D. Long. 1996. https://sparse.tamu.edu/ATandT

    1996

  12. [18]

    Alan George. 1973. Nested dissection of a regular finite element mesh. SIAM journal on numerical analysis 10, 2 (1973), 345–363

    1973

  13. [19]

    Alan George and Joseph WH Liu. 1989. The evolution of the minimum degree ordering algorithm. Siam review 31, 1 (1989), 1–19

    1989

  14. [20]

    Alan George and Joseph W. H. Liu. 1979. An Implementation of a Pseudope- ripheral Node Finder. ACM Trans. Math. Softw. 5, 3 (Sept. 1979), 284–295. https://doi.org/10.1145/355841.355845

    1979

  15. [21]

    Gibbs, William G

    Norman E. Gibbs, William G. Poole, Jr., and Paul K. Stockmeyer. 1976. An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix. SIAM J. Numer. Anal. 13, 2 (April 1976), 236–250. https://doi.org/10.1137/0713023

    1976 doi

  16. [22]

    John R Gilbert, Cleve Moler, and Robert Schreiber. 1992. Sparse matrices in MATLAB: Design and implementation. SIAM journal on matrix analysis and applications 13, 1 (1992), 333–356

    1992

  17. [23]

    John R Gilbert, Steve Reinhardt, and Viral B Shah. 2006. High-performance graph algorithms from parallel sparse matrices. In International Workshop on Applied Parallel Computing. Springer, 260–269

    2006

  18. [24]

    John R Gilbert and Robert Endre Tarjan. 1986. The analysis of a nested dissection algorithm. Numerische mathematik 50, 4 (1986), 377–404. 11

    1986

  19. [25]

    Theodoros Gkountouvas, Vasileios Karakasis, Kornilios Kourtis, Georgios Goumas, and Nectarios Koziris. 2013. Improving the performance of the sym- metric sparse matrix-vector multiplication in multicore. In 2013 IEEE 27th Inter- national Symposium on Parallel and Distributed P...

    2013

  20. [26]

    Anshul Gupta. 1996. https://sparse.tamu.edu/Gupta

    1996

  21. [27]

    Fred G Gustavson. 1978. Two fast algorithms for sparse matrices: Multiplication and permuted transposition. ACM Transactions on Mathematical Software (TOMS) 4, 3 (1978), 250–269

    1978

  22. [28]

    Song Han, Huizi Mao, and William J Dally. 2016. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. In Proceedings of the 4th International Conference on Learning Representations (ICLR)

    2016

  23. [29]

    Guoming He, Haijun Feng, Cuiping Li, and Hong Chen. 2010. Parallel SimRank computation on large graphs with iterative aggregation. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 543–552

    2010

  24. [30]

    Yuxi Hong and Aydin Buluç. 2024. A Sparsity-Aware Distributed-Memory Algorithm for Sparse-Sparse Matrix Multiplication. In Proceedings of the In- ternational Conference for High Performance Computing, Networking, Storage, and Analysis (Atlanta, GA, USA) (SC ’24) . IEEE Press, ...

    2024 arXiv

  25. [31]

    Paul Jaccard. 1901. Étude comparative de la distribution florale dans une portion des Alpes et des Jura. Bull Soc Vaudoise Sci Nat 37 (1901), 547–579

    1901

  26. [33]

    George Karypis and Vipin Kumar. 1998. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM Journal on Scientific Computing 20, 1 (1998), 359–392. https://doi.org/10.1137/S1064827595287997

    1998 doi

  27. [34]

    Jeremy Kepner, David Bader, Aydın Buluç, John Gilbert, Timothy Mattson, and Henning Meyerhenke. 2015. Graphs, matrices, and the GraphBLAS: Seven good reasons. Procedia Computer Science 51 (2015), 2453–2462

    2015

  28. [35]

    Mohsen Koohi Esfahani, Peter Kilpatrick, and Hans Vandierendonck. 2021. Ex- ploiting in-Hub Temporal Locality in SpMV-based Graph Processing. In Proceed- ings of the 50th International Conference on Parallel Processing (Lemont, IL, USA) (ICPP ’21). Association for Computing Ma...

    2021

  29. [36]

    Jure Leskovec, Anand Rajaraman, and Jeffrey David Ullman. 2020. Mining of massive data sets. Cambridge university press

    2020

  30. [37]

    Yongsub Lim, U Kang, and Christos Faloutsos. 2014. SlashBurn: Graph Compres- sion and Mining beyond Caveman Communities.IEEE Transactions on Knowledge and Data Engineering 26, 12 (2014), 3077–3089. https://doi.org/10.1109/TKDE. 2014.2320716

    2014

  31. [38]

    Wai-Hung Liu and Andrew H Sherman. 1976. Comparative analysis of the Cuthill–McKee and the reverse Cuthill–McKee ordering algorithms for sparse matrices. SIAM J. Numer. Anal. 13, 2 (1976), 198–213

    1976

  32. [39]

    Johannes Sebastian Mueller-Roemer, Christian Altenhofen, and André Stork

  33. [41]

    Angshuman Parashar, Minsoo Rhu, Anurag Mukkara, Antonio Puglielli, Rang- harajan Venkatesan, Brucek Khailany, Joel Emer, Stephen W Keckler, and William J Dally. 2017. SCNN: An accelerator for compressed-sparse convo- lutional neural networks. ACM SIGARCH computer architecture ...

    2017

  34. [42]

    Juan C Pichel, David E Singh, and Jesús Carretero. 2008. Reordering algorithms for increasing locality on multicore processors. In 2008 10th IEEE International Conference on High Performance Computing and Communications. IEEE, 123–130

    2008

  35. [43]

    Ali Pinar and Michael T Heath. 1999. Improving performance of sparse matrix- vector multiplication. In Proceedings of the 1999 ACM/IEEE conference on Super- computing. 30–es

    1999

  36. [44]

    Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. 2007. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 76, 3 (2007), 036106

    2007

  37. [45]

    Viral B Shah. 2007. An interactive system for combinatorial scientific computing with an emphasis on programmer productivity . University of California, Santa Barbara

    2007

  38. [46]

    Tinney and John W

    William F. Tinney and John W. Walker. 1967. Direct solutions of sparse network equations by optimally ordered triangular factorization. Proc. IEEE 55, 11 (1967), 1801–1809

    1967

  39. [47]

    Nick Trefethen. 2008. https://sparse.tamu.edu/JGD_Trefethen

    2008

  40. [48]

    James D. Trotter. [n. d.]. Libmtx, High Performance Computing at Simula Re- search Laboratory. https://github.com/simulahpc/libmtx

  41. [49]

    James D Trotter, Sinan Ekmekçibaşı, Johannes Langguth, Tugba Torun, Emre Düzakın, Aleksandar Ilic, and Didem Unat. 2023. Bringing order to sparsity: A sparse matrix reordering study on multicore cpus. In Proceedings of the Inter- national Conference for High Performance Comput...

    2023

  42. [50]

    Emer, and Daniel Sanchez

    Guowei Zhang, Nithya Attaluri, Joel S. Emer, and Daniel Sanchez. 2021. Gamma: leveraging Gustavson’s algorithm to accelerate sparse matrix multiplication. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating S...

    2021

  43. [51]

    Haoran Zhao, Tian Xia, Chenyang Li, Wenzhe Zhao, Nanning Zheng, and Pengju Ren. 2020. Exploring better speculation and data locality in sparse matrix- vector multiplication on intel xeon. In 2020 IEEE 38th International Conference on Computer Design (ICCD). IEEE, 601–609

    2020

  44. [52]

    Haoran Zhao, Tian Xia, Chenyang Li, Wenzhe Zhao, Nanning Zheng, and Pengju Ren. 2020. Exploring Better Speculation and Data Locality in Sparse Matrix- Vector Multiplication on Intel Xeon. In 2020 IEEE 38th International Conference on Computer Design (ICCD) . IEEE, Hartford, CT...

    2020

  45. [2017]

    In Computer Graphics Forum, Vol

    Ternary sparse matrix representation for volumetric mesh subdivision and processing on GPUs. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 59–69

  46. [2025]

    In Proceedings of the 30th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (Las Vegas, NV, USA) (PPoPP ’25)

    Accelerating GNNs on GPU Sparse Tensor Cores through N:M Sparsity- Oriented Graph Reordering. In Proceedings of the 30th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (Las Vegas, NV, USA) (PPoPP ’25). Association for Computing Machinery, New Y...

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.