Pith. sign in

REVIEW 3 major objections 5 minor 58 references

Popcorn: Accelerating Kernel K-means on GPUs through Sparse Linear Algebra

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read Reformulating kernel k-means as SpMM and SpMV yields a GPU implementation that is up to 2.6x faster than a dense GPU baseline and 123.8x faster than a CPU one, with under 50 lines of handwritten CUDA.

desk verdict Clean sparse-linear-algebra reformulation of kernel k-means with a real artifact, but the headline speedups are measured against a single-threaded MATLAB baseline and an in-house CUDA baseline. read the letter →

arxiv 2501.05587 v1 pith:BCPWBVGM submitted 2025-01-09 cs.DC

Julian Bellavita , Thomas Pasquali , Laura Del Rio Martin , Flavio Vella , Giulia Guidi This is my paper · ORCID
classification cs.DC
keywords SparseMatrixKernelK-MeansGPUSpMMMVCUDAcuClustering
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

Kernel k-means finds non-linearly separable clusters but costs O($n^{2}$) per iteration, making it slow on CPUs even for medium datasets. This paper claims that recasting the algorithm's core distance computation as sparse linear algebra removes the main obstacle to a fast GPU version. The key identity writes the point-centroid distance matrix as D = -2 K V^T + \tilde{P} + \tilde{C}, where V is a cluster-selection matrix with exactly one nonzero per column, so K V^T becomes a sparse-dense matrix multiplication (SpMM) and the centroid norms become one sparse matrix-vector product (SpMV). On this basis the authors built Popcorn, the first open-source GPU kernel k-means, relying on cuSPARSE and cuBLAS routines rather than hand-tuned kernels. They report up to 123.8x speedup over a single-threaded CPU implementation and up to 2.6x over an in-house dense CUDA baseline on six real-world datasets.

What carries the argument

The central object is the sparse selection matrix V, a k x n cluster-membership matrix with exactly one nonzero per column (the entry 1/|L_j| for each point in cluster j), which converts the three expensive steps of kernel k-means into tuned library calls. The distance identity D = -2 K V^T + \tilde{P} + \tilde{C} turns the per-iteration bottleneck into an SpMM (K V^T); the centroid norms, which would otherwise require forming centroids in feature space, become the diagonal of V K V^T and are recovered from one SpMV V z with no extra computation beyond assembling z from entries of the SpMM output. A second load-bearing mechanism is the runtime decision between GEMM and SYRK for computing B = \hat{P}\hat{P}^T (and hence the kernel matrix K), selected by the ratio n/d against a tunable threshold. Together these choices let cuSPARSE and cuBLAS carry almost all of the computation, which the paper argues yields both high performance and portability.

What would settle it

An independent, carefully tuned dense GPU kernel k-means that matches or beats Popcorn's per-iteration distance computation on most of the six datasets would falsify the claim that the SpMM/SpMV formulation, rather than cuSPARSE's tuning, drives the speedup.

Watch

Extended reading notes

Core claim

The paper's central claim is that kernel k-means can be formulated almost entirely as SpMM and SpMV, and that this formulation is enough to build a fast GPU implementation with little manual programming effort. Concretely, the pairwise distance matrix in feature space is D = -2 K V^T + \tilde{P} + \tilde{C}, where K is the kernel matrix, V is a k x n selection matrix whose (j,i) entry is 1/|L_j| when point i lies in cluster j and zero otherwise, and \tilde{P} and \tilde{C} are row-norm matrices. Because V has exactly one nonzero per column, K V^T is an SpMM, and the centroid norms—the diagonal of V K V^T—can be obtained from a single SpMV V z, where z is assembled from entries of the already-computed SpMM output. This eliminates the need to form centroids in feature space or to write optimized reduction kernels, and it turns the choice of kernel-matrix computation (GEMM vs SYRK) into a tunable ratio-based decision. The paper presents Popcorn as the first open-source GPU implementation of kernel k-means and reports speedups up to 123.8x over the PRMLT CPU implementation and up to 2.6x over a dense CUDA baseline on six libSVM datasets.

Load-bearing premise

The comparison assumes the in-house CUDA baseline and the single-threaded PRMLT CPU implementation are fair, representative stand-ins for well-tuned non-sparse kernel k-means; if either is substantially slower than an independently tuned implementation, the reported 123.8x and 2.6x speedups overstate Popcorn's advantage.

Editorial extensions

If this is right

  • Popcorn's per-iteration distance computation runs 1.5x–2.6x faster than the dense hand-written CUDA baseline on the tested datasets, and the speedup grows with the number of clusters k.
  • The SpMV-based centroid-norm computation means each iteration costs O(n^2) for the SpMM plus O(n) for the SpMV, with no separate pass over the kernel matrix to compute cluster centroids.
  • On datasets with large n and small d, the GEMM-based kernel computation is up to 3.2x faster than the SYRK-based one, while for n close to d the SYRK-based one is up to 2.4x faster, so Popcorn's ratio-based auto-selection between the two contributes to its overall speedup.
  • Because nearly all computation is offloaded to cuSPARSE and cuBLAS, Popcorn uses fewer than 50 lines of hand-written CUDA and, the authors argue, inherits performance improvements in those libraries without additional engineering.

Reading between the lines

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

  • Going beyond the paper: the same V-matrix trick should carry over to other kernel-based algorithms that repeatedly compute distances to moving centroids or prototypes—kernel fuzzy c-means, online kernel clustering, or self-organizing maps—turning their inner loops into SpMM/SpMV as well.
  • Implicit consequence: the GEMM-vs-SYRK threshold is calibrated on the A100 GPU used in the experiments; on other GPU architectures the crossover point may shift, so Popcorn's 'automatic' strategy still needs per-platform tuning before the claimed ease of use fully generalizes.
  • Editorial inference: since the speedup over the dense baseline is largely attributed to cuSPARSE's tuned SpMM, the advantage could shrink on libraries or architectures where a careful dense reduction kernel uses shared memory more aggressively—the paper's own roofline data show Popcorn sometimes has lower arithmetic intensity than the baseline.
  • Testable extension: applying Popcorn's formulation to approximate kernel matrices (for example Nyström or random Fourier features) would preserve the SpMM/SpMV structure while cutting the O(n^2) kernel-matrix cost, potentially extending GPU kernel k-means beyond single-GPU memory.
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

3 major / 5 minor

Summary. The paper reformulates kernel k-means so that the per-iteration distance computation is expressed through sparse linear algebra: after forming the dense kernel matrix K, the distances to centroids are D = -2 K V^T + \tilde{P} + \tilde{C}, where V is a sparse cluster-selection matrix, and the centroid norms are obtained without forming centroids via an SpMV V z (Equations 10, 14, 15). The authors present Popcorn, a CUDA implementation built on cuSPARSE and cuBLAS, including a GEMM-versus-SYRK selection policy for computing K, and they evaluate it on six real-world datasets against an in-house dense CUDA baseline and the PRMLT MATLAB CPU implementation. The paper claims speedups of up to 123.8x over the CPU implementation and up to 2.6x over the GPU baseline, and it makes the artifact publicly available.

Significance. The algebraic derivation in Section 3 is clean and internally consistent, and the SpMV-based computation of centroid norms from the diagonal of V K V^T is a genuinely nice observation. The design choice of reducing hand-written CUDA to a few simple kernels while relying on cuSPARSE and cuBLAS is plausible and aligns with the paper's productivity argument. The artifact description is unusually detailed and appears reproducible. However, the quantitative central claims are currently supported by weak baselines: the CPU comparison uses a single-threaded MATLAB toolbox, and the GPU comparison uses an in-house implementation that is not validated against any external reference. The pairwise-distance experiment in Section 5.5 gives the fairest evidence for the sparse-formulation benefit (1.5-2.6x over the hand-written baseline), but the headline full-algorithm speedups combine this with an orthogonal BLAS-routine selection policy. The mathematical contribution is sound; the empirical interpretation needs recalibration.

major comments (3)
  1. [Section 1 and Section 5.4] The abstract and Section 1 describe the comparison as being against 'the fastest CPU implementation of Kernel K-means', but Section 5.4 states that the PRMLT implementation is a 'single-threaded CPU version of Kernel K-means'. A single-threaded MATLAB toolbox is not an established fastest CPU solver, so the up-to-123.8x speedup does not support the claim that Popcorn is fast relative to a realistic CPU implementation. Please compare against a multithreaded CPU kernel k-means (for example, one built on BLAS or at least a C++ implementation), or rephrase the claim to specify exactly what baseline was used and avoid the word 'fastest'.
  2. [Section 5.3 and Section 5.6] The GPU baseline is an in-house CUDA implementation whose kernels are described but not validated against any independent GPU kernel k-means. The full-algorithm speedup in Figure 7 therefore conflates two separate effects: the benefit of SpMM/SpMV for pairwise distances and the benefit of the GEMM/SYRK selection strategy for building K. Section 5.5 isolates the pairwise-distance contribution, but Section 5.6 reports a combined number. Please either validate the baseline against a published or otherwise stronger dense GPU implementation, or decompose the full-algorithm speedup so that the sparse-linear-algebra contribution is not overstated.
  3. [Section 5.2] The GEMM-versus-SYRK threshold t is reported as architecture-dependent and tuned on the A100, and the experiments show that the best choice depends on the n/d ratio. This means the kernel-construction speedups are specific to one GPU and one CUDA version. Since the dynamic selection is listed as a main contribution, please report the sensitivity of the reported speedups to this threshold, or at least state explicitly which t value was used for each dataset and whether the conclusions change for nearby thresholds.
minor comments (5)
  1. [Appendix A.5] The artifact description maps speedup-cuda.png, distances-speedup.png, and speedup-popcorn.png to Figures 4, 5, and 8 in the paper, but the corresponding figures in the main text are Figures 3, 4, and 7. Please correct the cross-references.
  2. [Section 4.5] There is a typo in 'offload most of the computation to in Kernel K-means library routines'; 'to in' should be 'to the'.
  3. [Section 4.5] The word 'embarassingly' should be 'embarrassingly' in the sentence describing the hand-written kernels.
  4. [Section 5.2] The rule for selecting GEMM versus SYRK is stated as 'ratio greater than 100' for GEMM and 'less than 100' for SYRK, leaving the ratio exactly equal to 100 unspecified; a simple tie-breaking rule or inequality direction would remove the ambiguity.
  5. [Table 1] The table of symbols omits \tilde{P}, \tilde{C}, and the vector z used in Algorithm 2 and Section 3.3; adding them would make the notation easier to follow.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the kernel k-means reformulation is a self-contained algebraic derivation, and the reported speedups are measurements, not predictions from fitted parameters.

full rationale

The paper's central derivation is an algebraic identity. Starting from the feature-space distance decomposition in Equation 2, it defines the selection matrix V (Equation 7), observes that centroids satisfy C = VP (Equation 8), and substitutes K = PP^T to obtain the distance update D = -2KV^T + P~ + C~ (Equation 10). This is a self-contained mathematical reduction, not a fitted or self-referential step. The centroid-norm computation is likewise derived from the identity (VKV^T)_ii = ||c_i||^2 and from the structural property that V has exactly one nonzero per column, leading to the SpMV formulation in Equations 13-15. No parameter is fitted to data and then presented as a prediction of the algorithm's behavior. The GEMM/SYRK switching threshold t is empirically tuned on the target hardware ('The appropriate value of t is architecture-dependent, so we leave it as a tunable parameter'), but this only selects between two BLAS routines for computing the kernel matrix; it is an implementation-level tuning choice, not a quantity whose prediction is the paper's claim. The reported speedups against PRMLT and the in-house CUDA baseline are measurements; one may question whether PRMLT is a representative fast CPU implementation or whether the in-house baseline is optimally tuned, but those are benchmarking-validity concerns, not circularity. Citations to prior work, including Guidi et al. on sparse-matrix genomics and Baydoun et al. on GPU kernel k-means, are contextual and do not carry the weight of the derivation. No self-citation chain, uniqueness theorem, or definitional equivalence forces the paper's conclusions. The algorithmic contribution is therefore self-contained and non-circular.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new physical or conceptual entities. The selection matrix V is a standard assignment encoding, and the vector z is an optimization of an existing computation, not a new entity.

free parameters (1)
  • GEMM/SYRK selection threshold t = 100 (ratio n/d on A100)
    Chosen empirically in Section 5.2 as the ratio above which the GEMM-based kernel computation is faster than SYRK-based on the test platform; it is architecture-dependent and does not affect the mathematical formulation.
assumptions (3)
  • domain assumption Each point belongs to exactly one cluster at every iteration, so V has exactly one nonzero per column.
    This property is the basis for the SpMV trick in Section 3.3 that extracts diagonal entries of V K V^T without forming the full k by n product.
  • domain assumption The kernel matrix K does not depend on cluster assignments and can be computed once before iterations.
    Used in Algorithm 2 line 1 and Section 3.2; true for the polynomial and Gaussian kernels considered because they depend only on the fixed input points.
  • standard math The squared feature-space distance formula D = -2 K V^T + tilde{P} + tilde{C} is a valid rearrangement of the kernel distance computation.
    Derived in Section 3.1 from the expansion of the norm and the identity C = V P; standard kernel k-means material.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Popcorn: Accelerating Kernel K-means on GPUs through Sparse Linear Algebra." pith.science (2026). https://pith.science/paper/BCPWBVGM

@misc{pith2026250105587,
  author       = {Pith},
  title        = {Pith review of: Popcorn: Accelerating Kernel K-means on GPUs through Sparse Linear Algebra},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BCPWBVGM}},
  note         = {Machine review of arXiv:2501.05587}
}
read the original abstract

K-means is a popular clustering algorithm with significant applications in numerous scientific and engineering areas. One drawback of K-means is its inability to identify non-linearly separable clusters, which may lead to inaccurate solutions in certain cases. Kernel K-means is a variant of classical K-means that can find non-linearly separable clusters. However, it scales quadratically with respect to the size of the dataset, taking several minutes to cluster even medium-sized datasets on traditional CPU-based machines. In this paper, we present a formulation of Kernel K-means using sparse-dense matrix multiplication (SpMM) and sparse matrix-vector multiplication (SpMV), and we show that our formulation enables the rapid implementation of a fast GPU-based version of Kernel K-means with little programming effort. Our implementation, named Popcorn, is the first open-source GPU-based implementation of Kernel K-means. Popcorn achieves a speedup of up to 123.8x over a CPU implementation of Kernel K-means and a speedup of up to 2.6x over a GPU implementation of Kernel K-means that does not use sparse matrix computations. Our results support the effectiveness of sparse matrices as tools for efficient parallel programming.

Figures

Figures reproduced from arXiv: 2501.05587 by the authors.

Figure 1
Figure 1. Computing the diagonal of VKVT using SpMV. Vz =        ∥c1 ∥ 2 . . . ∥ck ∥ 2        (15) V is a sparse matrix with exactly 𝑛 nonzeros, so this matrix￾vector product can be computed with SpMV while only re￾quiring O (𝑛) work. The previous approach of explicitly cal￾culating VKVT and extracting the diagonal requires O (𝑛𝑘) work. Note that KVT is already computed in the first term of Equation 10, meaning … view at source ↗
Figure 2
Figure 2. Comparison of the kernel matrix computation for synthetic data with SYRK and with GEMM. significant for (𝑛 = 50000, 𝑑 = 100), where the GEMM-based algorithm is 3.2× faster than the SYRK-based algorithm. For datasets where 𝑛 and 𝑑 are similar, the SYRK-based algorithm is up to 2.4× faster. Overall, these experiments suggest that for our specific platform, it is best to use the GEMM-based algorithm when the ratio betw… view at source ↗
Figure 4
Figure 4. shows the speedup of Popcorn’s pairwise dis￾tances algorithm over that of the baseline CUDA implemen￾tation. Popcorn is consistently between 1.5× to 2.6× faster than the baseline CUDA implementation, except for the SCO￾TUS dataset at 𝑘 = 50, where the speedup is 1.1× due to the small number of points in this dataset, i.e., 𝑛 = 6400 [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figures from the paper (4 more)
Figure 5
Figure 5. Figure 5: Comparison of throughput between the pairwise distances algorithm of Popcorn and the baseline CUDA implementation for varying 𝑘. from 1.6× to 2.6× for 𝑘 = 100. Overall, Popcorn is consis￾tently faster than our baseline CUDA implementation. These speedups are due to a c…
Figure 6
Figure 6. Figure 6: Roofline plots comparing pairwise distances algorithm of Popcorn and the baseline CUDA implementation [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]
Figure 7
Figure 7. Figure 7: Popcorn speedup over baseline CUDA implemen￾tation varying 𝑘 [PITH_FULL_IMAGE:figures/full_fig_p012_7.png]
Figure 8
Figure 8. Figure 8: Runtime breakdown of Popcorn on each dataset with varying 𝑘. The letter dataset is excluded because it has very small runtimes. node embedding. Azad et al. [53] parallelize Markov Cluster￾ing across distributed memory using sparse general matrix multiply (SpGEMM). Arfa…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

58 extracted references · 53 canonical work pages

  1. [1]

    Environmental and economic clustering of indonesian provinces: In- sights from k-means analysis

    Teuku Rizky Noviandy, Irsan Hardi, Zahriah Zahriah, Rahmi Sofyan, Novi Reandy Sasmita, Iin Shabrina Hilal, and Ghalieb Mutig Idroes. Environmental and economic clustering of indonesian provinces: In- sights from k-means analysis. Leuser Journal of Environmental Studies , 2(1):41–51, 2024

    work page 2024

  2. [2]

    Interdependence between human capital determinants and economic development: K-means regional clustering approach for czechia and poland

    Michał Wielechowski, Denys Cherevyk, Katarzyna Czech, Pavel Ko- tyza, Łukasz Grzęda, and Lubos Smutka. Interdependence between human capital determinants and economic development: K-means regional clustering approach for czechia and poland. Entrepreneurial Business and Economics Review , 9(4):173–194, 2021

    work page 2021

  3. [3]

    K-means-based feature learning for protein sequence classification

    Paul Melman and Usman W Roshan. K-means-based feature learning for protein sequence classification. Proceedings of the BICOB, Las Vegas, NV, USA, pages 19–21, 2018

    work page 2018

  4. [4]

    Randomly pivoted cholesky: Practical approximation of a kernel matrix with few entry evaluations

    Yifan Chen, Ethan N Epperly, Joel A Tropp, and Robert J Webber. Randomly pivoted cholesky: Practical approximation of a kernel matrix with few entry evaluations. arXiv preprint arXiv:2207.06503, 2022

    arXiv 2022

  5. [5]

    Multiplying matrices without multiply- ing

    Davis Blalock and John Guttag. Multiplying matrices without multiply- ing. In International Conference on Machine Learning , pages 992–1004. PMLR, 2021

    work page 2021

  6. [6]

    Kernel k-means: spectral clustering and normalized cuts

    Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: spectral clustering and normalized cuts. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 551–556, 2004

    2004

  7. [7]

    Localized data fusion for kernel k-means clustering with application to cancer biology

    Mehmet Gönen and Adam A Margolin. Localized data fusion for kernel k-means clustering with application to cancer biology. In Z. Ghahra- mani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems , volume 27. Curran Associates, Inc., 2014

    work page 2014

  8. [8]

    The classification of diabetes mellitus using kernel k-means

    MARTHA Alamsyah, ZUMROTUN Nafisah, E Prayitno, AM Afida, and EM Imah. The classification of diabetes mellitus using kernel k-means. In Journal of Physics: Conference Series , volume 947, page 012003. IOP Publishing, 2018

    work page 2018

Show all 58 references
  1. [9]

    A kernel <i>k</i>-means-based method and attribute selections for diabetes diagnosis

    Tru Cao, Chau Vo, Son Nguyen, Atsushi Inoue, and Duanning Zhou. A kernel <i>k</i>-means-based method and attribute selections for diabetes diagnosis. Journal of Advanced Computational Intelligence and Intelligent Informatics, 24(1):73–82, 2020

    2020

  2. [10]

    An Application of Predicting Student Performance Using Kernel K-Means and Smooth Support Vector Machine

    Sajadin Sembiring. An Application of Predicting Student Performance Using Kernel K-Means and Smooth Support Vector Machine . PhD thesis, UMP, 2012

    2012

  3. [11]

    Smart agriculture system based on internet of things using kernel k-means with support vector machine

    Junhong Zhong and Qi Lai. Smart agriculture system based on internet of things using kernel k-means with support vector machine. In 2024 Second International Conference on Data Science and Information System (ICDSIS), pages 1–4, 2024

    2024

  4. [12]

    Sar image change detection based on multiple kernel k-means clustering with local-neighborhood information

    Lu Jia, Ming Li, Peng Zhang, Yan Wu, and Huahui Zhu. Sar image change detection based on multiple kernel k-means clustering with local-neighborhood information. IEEE Geoscience and Remote Sensing Letters, 13(6):856–860, 2016

    2016

  5. [13]

    Performance analysis and cpu vs gpu comparison for deep learning

    Ebubekir BUBER and Banu DIRI. Performance analysis and cpu vs gpu comparison for deep learning. In 2018 6th International Conference on Control Engineering & Information Technology (CEIT) , pages 1–6, 2018

    2018

  6. [14]

    Kaufman, and S

    Zhe Fan, Feng Qiu, A. Kaufman, and S. Yoakum-Stover. Gpu cluster for high performance computing. In SC ’04: Proceedings of the 2004 ACM/IEEE Conference on Supercomputing, pages 47–47, 2004

    2004

  7. [15]

    Trends of cpu, gpu and fpga for high-performance computing

    Mario Vestias and Horácio Neto. Trends of cpu, gpu and fpga for high-performance computing. In 2014 24th International Conference on Field Programmable Logic and Applications (FPL) , pages 1–6. IEEE, 2014

    2014

  8. [16]

    Detailed analysis and optimiza- tion of cuda k-means algorithm

    Martin Kruliš and Miroslav Kratochvíl. Detailed analysis and optimiza- tion of cuda k-means algorithm. InProceedings of the 49th International Conference on Parallel Processing , ICPP ’20, New York, NY, USA, 2020. Association for Computing Machinery

    2020

  9. [17]

    Cpu and gpu parallelized kernel k-means

    Mohammed Baydoun, Hassan Ghaziri, and Mohammed Al-Husseini. Cpu and gpu parallelized kernel k-means. The Journal of Supercom- puting, 74(8):3975–3998, 2018

    2018

  10. [18]

    Rapidsai/raft: Raft contains fundamental widely-used algo- rithms and primitives for data science, graph and machine learning., 2022

    Rapidsai. Rapidsai/raft: Raft contains fundamental widely-used algo- rithms and primitives for data science, graph and machine learning., 2022

    2022

  11. [19]

    src-d/kmcuda: 6.0.0-1, 2017

    Vadim Markovtsev and Máximo Cuadros. src-d/kmcuda: 6.0.0-1, 2017

    2017

  12. [20]

    Scalable parallel programming with cuda: Is cuda the parallel programming model that application developers have been waiting for? Queue, 6(2):40–53, 2008

    John Nickolls, Ian Buck, Michael Garland, and Kevin Skadron. Scalable parallel programming with cuda: Is cuda the parallel programming model that application developers have been waiting for? Queue, 6(2):40–53, 2008

    2008

  13. [21]

    Automatic Tuning of CUDA Execution Parameters for Stencil Processing, pages 209–228

    Katsuto Sato, Hiroyuki Takizawa, Kazuhiko Komatsu, and Hiroaki Kobayashi. Automatic Tuning of CUDA Execution Parameters for Stencil Processing, pages 209–228. Springer New York, New York, NY, 2010

    2010

  14. [22]

    Yuri Torres, Arturo Gonzalez-Escribano, and Diego R. Llanos. Un- derstanding the impact of cuda tuning techniques for fermi. In 2011 International Conference on High Performance Computing & Simulation , pages 631–639, 2011

    2011

  15. [23]

    cuSPARSE, 2024

    NVIDIA Corporation. cuSPARSE, 2024. https://docs.nvidia.com/cuda/ cusparse

    2024

  16. [24]

    cuBLAS, 2024

    NVIDIA Corporation. cuBLAS, 2024. https://docs.nvidia.com/cuda/ cublas

    2024

  17. [25]

    S. Lloyd. Least squares quantization in pcm. IEEE Transactions on Information Theory, 28(2):129–137, 1982

    1982

  18. [26]

    k-means++: the advantages of careful seeding

    David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA ’07, page 1027–1035, USA,

  19. [27]

    Kernel methods for pattern analysis

    John Shawe-Taylor and Nello Cristianini. Kernel methods for pattern analysis. Cambridge university press, 2004

    2004

  20. [28]

    Thrust: A productivity-oriented library for cuda, 2012

    Nathan Bell and Jared Hoberock. Thrust: A productivity-oriented library for cuda, 2012

    2012

  21. [29]

    Libsvm: A library for sup- port vector machines

    Chih-Chung Chang and Chih-Jen Lin. Libsvm: A library for sup- port vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1–27, 2011

    2011

  22. [30]

    Learning features in deep architectures with unsupervised kernel k-means

    Karl Ni and Ryan Prenger. Learning features in deep architectures with unsupervised kernel k-means. In 2013 IEEE Global Conference on Signal and Information Processing , pages 981–984, 2013

    2013

  23. [31]

    Rudnicky

    Rong Zhang and A.I. Rudnicky. A large scale clustering scheme for kernel k-means. In 2002 International Conference on Pattern Recognition, volume 4, pages 289–292 vol.4, 2002

    2002

  24. [32]

    Pattern recognition and machine learning toolbox

    Mo Chen. Pattern recognition and machine learning toolbox. https: //github.com/PRML/PRMLT, 2024. Retrieved July 30, 2024

    2024

  25. [33]

    Roofline: an insightful visual performance model for multicore architectures

    Samuel Williams, Andrew Waterman, and David Patterson. Roofline: an insightful visual performance model for multicore architectures. Commun. ACM, 52(4):65–76, apr 2009

    2009

  26. [34]

    NVIDIA Nsight Compute, 2024

    NVIDIA Corporation. NVIDIA Nsight Compute, 2024. https://docs. nvidia.com/nsight-compute/index.html

    2024

  27. [35]

    Using the triangle inequality to accelerate k-means

    Charles Elkan. Using the triangle inequality to accelerate k-means. In Proceedings of the 20th international conference on Machine Learning (ICML-03), pages 147–153, 2003

    2003

  28. [36]

    Accelerating lloyd’s algorithm for k-means clustering

    Greg Hamerly and Jonathan Drake. Accelerating lloyd’s algorithm for k-means clustering. Partitional clustering algorithms, pages 41–78, 2015

    2015

  29. [37]

    A parallel implementation of k-means clustering on gpus

    Reza Farivar, Daniel Rebolledo, Ellick Chan, and Roy H Campbell. A parallel implementation of k-means clustering on gpus. In Pdpta, volume 13, pages 212–312, 2008

    2008

  30. [38]

    Efficient k-means on gpus

    Clemens Lutz, Sebastian Breß, Tilmann Rabl, Steffen Zeuch, and Volker Markl. Efficient k-means on gpus. In Proceedings of the 14th Interna- tional Workshop on Data Management on New Hardware , pages 1–3, 2018

    2018

  31. [39]

    Speeding up k-means algorithm by gpus

    You Li, Kaiyong Zhao, Xiaowen Chu, and Jiming Liu. Speeding up k-means algorithm by gpus. Journal of Computer and System Sciences , 79(2):216–229, 2013. PPoPP ’25, March 1–5, 2025, Las Vegas, NV, USA Julian Bellavita ∗, Thomas Pasquali, Laura Del Rio Martin, Flavio Vella∗, and...

    2013

  32. [40]

    Large scale k-means clustering using gpus

    Mi Li, Eibe Frank, and Bernhard Pfahringer. Large scale k-means clustering using gpus. Data Mining and Knowledge Discovery, 37(1):67– 109, 2023

    2023

  33. [41]

    Ap- proximate kernel k-means: Solution to large scale kernel clustering

    Radha Chitta, Rong Jin, Timothy C Havens, and Anil K Jain. Ap- proximate kernel k-means: Solution to large scale kernel clustering. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining , pages 895–903, 2011

    2011

  34. [42]

    Sparse kernel k-means for high- dimensional data

    Xin Guan and Yoshikazu Terada. Sparse kernel k-means for high- dimensional data. Pattern Recognition, 144:109873, 2023

    2023

  35. [43]

    Kernel penalized k-means: A feature selection method based on kernel k- means

    Sebastián Maldonado, Emilio Carrizosa, and Richard Weber. Kernel penalized k-means: A feature selection method based on kernel k- means. Information sciences, 322:150–160, 2015

    2015

  36. [44]

    Lacc: A linear-algebraic algorithm for finding connected components in distributed memory

    Ariful Azad and Aydın Buluç. Lacc: A linear-algebraic algorithm for finding connected components in distributed memory. In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS) , pages 2–12. IEEE, 2019

    2019

  37. [45]

    Algorithm 1000: Suitesparse: Graphblas: Graph algorithms in the language of sparse linear algebra

    Timothy A Davis. Algorithm 1000: Suitesparse: Graphblas: Graph algorithms in the language of sparse linear algebra. ACM Transactions on Mathematical Software (TOMS) , 45(4):1–25, 2019

    2019

  38. [46]

    The combinatorial blas: Design, implementation, and applications

    Aydın Buluç and John R Gilbert. The combinatorial blas: Design, implementation, and applications. The International Journal of High Performance Computing Applications, 25(4):496–509, 2011

    2011

  39. [47]

    Sparse tensor algebra as a parallel programming model

    Edgar Solomonik and Torsten Hoefler. Sparse tensor algebra as a parallel programming model. arXiv preprint arXiv:1512.00066, 2015

    2015 arXiv

  40. [48]

    Parallel string graph construction and transi- tive reduction for de novo genome assembly

    Giulia Guidi, Oguz Selvitopi, Marquita Ellis, Leonid Oliker, Katherine Yelick, and Aydın Buluç. Parallel string graph construction and transi- tive reduction for de novo genome assembly. In2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS) , pages 51...

    2021

  41. [49]

    Distributed-memory parallel contig gener- ation for de novo long-read genome assembly

    Giulia Guidi, Gabriel Raulet, Daniel Rokhsar, Leonid Oliker, Katherine Yelick, and Aydin Buluc. Distributed-memory parallel contig gener- ation for de novo long-read genome assembly. In Proceedings of the 51st International Conference on Parallel Processing , pages 1–11, 2022

    2022

  42. [50]

    Bella: Berkeley efficient long-read to long-read aligner and overlapper

    Giulia Guidi, Marquita Ellis, Daniel Rokhsar, Katherine Yelick, and Aydın Buluç. Bella: Berkeley efficient long-read to long-read aligner and overlapper. In SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21), pages 123–134. SIAM, 2021

    2021

  43. [51]

    Reducing com- munication in graph neural network training

    Alok Tripathy, Katherine Yelick, and Aydın Buluç. Reducing com- munication in graph neural network training. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1–14. IEEE, 2020

    2020

  44. [52]

    Scalable node embedding algorithms using distributed sparse matrix operations

    Isuru Ranawaka and Ariful Azad. Scalable node embedding algorithms using distributed sparse matrix operations. In 2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) , pages 1199–1201. IEEE, 2024

    2024

  45. [53]

    Hipmcl: a high-performance parallel implementation of the markov clustering algorithm for large-scale networks

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

    2018

  46. [54]

    Efficient sphere detector algorithm for massive mimo using gpu hardware accelerator

    Mohamed-Amine Arfaoui, Hatem Ltaief, Zouheir Rezki, Mohamed- Slim Alouini, and David Keyes. Efficient sphere detector algorithm for massive mimo using gpu hardware accelerator. Procedia Computer Science, 80:2169–2180, 2016

    2016

  47. [55]

    Leveraging gpu tensor cores for double precision euclidean distance calculations

    Benoit Gallet and Michael Gowanlock. Leveraging gpu tensor cores for double precision euclidean distance calculations. In 2022 IEEE 29th International Conference on High Performance Computing, Data, and Analytics (HiPC), pages 135–144. IEEE, 2022

    2022

  48. [56]

    Toward capturing genetic epistasis from multivariate genome-wide association studies using mixed-precision kernel ridge regression

    Hatem Ltaief, Rabab Alomairy, Qinglei Cao, Jie Ren, Lotfi Slim, Thorsten Kurth, Benedikt Dorschner, Salim Bougouffa, Rached Ab- delkhalak, and David E Keyes. Toward capturing genetic epistasis from multivariate genome-wide association studies using mixed-precision kernel ridge...

    2024 arXiv

  49. [57]

    Human activity recognition based on parallel approximation kernel k-means algorithm

    Ahmed AM Jamel and Bahriye Akay. Human activity recognition based on parallel approximation kernel k-means algorithm. Computer Systems Science & Engineering , 35(6), 2020. Appendix A Artifact Description A.1 Availability Our artifact is available at Zenodo https://doi.org/10.5...

    2020

  50. [2007]

    Society for Industrial and Applied Mathematics

Pith tools

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