Fast Dominance Estimation Clustering (FastDEC) is an efficient variant of Density Peak Clustering (DPC) that achieves high clustering quality through dominance-based density estimation, but remains constrained by the computational cost of exact k-nearest-neighbor (k-NN) construction and dominance component (DC) processing. We present SymWarp-FastDEC, a GPU-accelerated implementation of FastDEC. At its core is SymTrikNN, an exact self-k-NN kernel that exploits search symmetry using upper-triangular traversal and warp-cooperative top-k selection. We also introduce WP-DC, a warp-parallel DC reduction algorithm designed for modern GPUs. Combined with memory-adaptive execution planning and stream scheduling, WP-DC eliminates DC reduction as a runtime bottleneck. Experiments on synthetic and real-world datasets show that SymWarp-FastDEC produces clustering outputs identical to the original FastDEC on all evaluated equivalence benchmarks. Compared with a FastDEC variant using FAISS GpuIndexFlatL2 for exact k-NN search, our approach achieves approximately 1.7x to 4.9x higher end-to-end performance, with the advantage generally increasing with dimensionality. Compared with the original single-threaded Python FastDEC implementation, speedups reach approximately 2.5 x 10^4 in a very high-dimensional case where its k-d-tree-based search degrades; this extreme result is not representative of typical acceleration.
Figures & tables
Figure 1: The grid of point blocks used by the exact self- k -NN kernel. (a) Because the reference set and query set are identical, only the upper-triangular and diagonal tiles ( j≥i ) are computed. Each computed tile is reused, through a second (reverse) selection pass, for its transposed position rather than recomputed, reducing the number of GEMM calls by approximately one half. Diagonal tiles ( i=j ) require updates only once. (b) Detail of a computed tile. A single GEMM computes the −2QR⊤ term for the entire tile, which is combined with precomputed squared norms to form the distance tile. The resulting distances are then processed by two independent warp-cooperative kernels that update the top- k heaps of both the query block and the reference block from the same computation.
d2(q,r)=νq+νr−2xq⊤xr.
Algorithm 8 Warp-Cooperative Top- k Selection
Dataset
syn_1m_1536d
glove_1.2m_300d
deep_2m_96d
mnist_2m_784d
syn_2m_1536d
deep_5m_96d
mnist_8m_784d
syn_10m_64d
syn_10m_512d
Runtime (s)
66.66
30.82
41.57
128.79
240.78
236.77
2121.55
814.36
2278.88
DC reduction (s)
0.11
0.04
0.20
3.18
0.31
0.66
156.14
1.55
2.84
DC reduction (%)
0.17
0.13
0.48
2.47
0.13
0.28
7.36
0.19
0.12
Table 1: Runtime of SymWarp-FastDEC and time spent in Dominance Component (DC) reduction across large-scale datasets (all with at least 1M instances), ordered by number of points. DC reduction (%) denotes the proportion of total runtime consumed by the DC reduction step.
Figure 4
Dataset
syn_50k_16384d
img_200k_32x32
syn_500k_64d
deep_500k_96d
mnist_500k_784d
syn_500k_4096d
Runtime (s)
2.38
2.37
2.95
3.66
9.42
42.75
DC reduction (s)
0.04
0.02
0.01
0.02
0.10
0.10
DC reduction (%)
1.68
0.84
0.34
0.55
1.06
0.23
Table 2: Runtime of SymWarp-FastDEC and time spent in Dominance Component (DC) reduction across smaller datasets of varying dimensionality, ordered by number of points and then by dimensionality. DC reduction (%) denotes the proportion of total runtime consumed by the DC reduction step.
Dataset
syn_50k_2d
syn_50k_4d
syn_50k_8d
syn_50k_512d
mnist_70k_2d
mnist_70k_784d
symwarp runtime (s)
0.12
0.12
0.12
0.21
0.16
0.33
wp-dc runtime (s)
0.005
0.003
0.003
0.004
0.010
0.010
wp-dc proportion (%)
4.17
2.50
2.50
1.90
6.25
3.03
pycpu runtime (s)
7.69
6.67
9.10
2098.24
15.51
5125.48
py-dc runtime (s)
7.18
5.59
2.88
2.29
14.84
14.91
py-dc proportion (%)
93.37
83.81
31.65
0.11
95.68
0.29
Table 3: Contribution of Dominance Component (DC) reduction to total runtime in the GPU-accelerated ( wp-dc , within SymWarp-FastDEC ) and CPU-based ( py-dc , within FastDEC-pycpu ) implementations. Runtime and the proportion of total runtime consumed by DC reduction are reported, with datasets ordered by number of points and then by dimensionality.
Figure 4: DC reduction overhead and total runtime for the GPU-accelerated implementation ( wp-dc , in SymWarp-FastDEC ) and the CPU-based implementation ( py-dc , in FastDEC-pycpu ) across six datasets with varying dimensionalities. The lines (left axis) show the percentage of total runtime spent on DC reduction, while the bars (right axis, logarithmic scale) show the corresponding total runtimes.
Algorithm
70k_2d
70k_784d
100k_784d
500k_784d
1m_784d
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
0.51
1.00×
4.50
1.00×
8.87
1.00×
220.66
1.00×
889.33
1.00×
faissgpu
0.37
1.38×
1.05
4.29×
1.66
5.34×
25.67
8.60×
96.38
9.23×
symwarp
0.16
3.19×
0.33
13.64×
0.56
15.84×
9.42
23.42×
35.34
25.16×
Table 4: Runtime ( T , in seconds) comparison across MNIST subsets. Speedup (SUP) is computed relative to the knncuda baseline. The fastest runtime for each dataset is shown in bold.
Figure 9
Algorithm
50d
100d
200d
300d
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
340.68
1.00×
405.68
1.00×
539.57
1.00×
702.07
1.00×
faissgpu
35.76
9.53×
40.63
9.98×
58.59
9.21×
78.24
8.97×
symwarp
16.49
20.66×
18.72
21.67×
24.14
22.35×
30.82
22.78×
Table 5: Runtime ( T , in seconds) comparison across GloVe datasets. Speedup (SUP) is computed relative to the knncuda baseline. The fastest runtime for each dataset is shown in bold.
Algorithm
200k_96d
500k_96d
1m_96d
2m_96d
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
6.25
1.00×
33.94
1.00×
151.31
1.00×
799.65
1.00×
faissgpu
1.60
3.91×
6.87
4.94×
23.98
6.31×
88.03
9.08×
symwarp
0.94
6.65×
3.66
9.27×
11.72
12.91×
41.57
19.24×
Table 6: Runtime ( T , in seconds) comparison across Deep1B subsets. Speedup (SUP) is computed relative to the knncuda baseline. The fastest runtime for each dataset is shown in bold.
Figure 12
Algorithm
8x8
8x16
16x16
16x32
32x32
32x64
64x64
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
5.27
1.00×
7.99
1.00×
13.50
1.00×
24.73
1.00×
47.35
1.00×
92.74
1.00×
183.62
1.00×
faissgpu
1.62
3.25×
1.84
4.34×
2.54
5.31×
3.92
6.31×
6.58
7.20×
13.45
6.90×
26.29
6.98×
symwarp
0.71
7.42×
0.81
9.86×
1.00
13.50×
1.45
17.06×
2.37
19.98×
4.10
22.62×
7.02
26.16×
Table 7: Runtime ( T , in seconds) comparison across image-patch datasets. Speedup (SUP) is computed relative to the knncuda baseline. The fastest runtime for each dataset is shown in bold.
Algorithm
syn_5k_64d
syn_200k_512d
syn_200k_784d
syn_500k_64d
syn_500k_784d
syn_1m_64d
syn_5m_64d
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
0.21
1.00×
25.37
1.00×
37.38
1.00×
32.92
1.00×
232.48
1.00×
157.51
1.00×
8632.29
1.00×
faissgpu
0.20
1.05×
3.63
6.99×
5.32
7.03×
6.15
5.35×
27.62
8.42×
21.48
7.33×
494.69
17.45×
symwarp
0.01
21.00×
1.44
17.62×
1.90
19.67×
2.95
11.16×
9.96
23.34×
9.86
15.97×
209.29
41.25×
Table 8: Runtime ( T , in seconds) comparison on synthetic datasets. Speedup (SUP) is computed relative to the knncuda baseline. The fastest runtime for each dataset is shown in bold.
Figure 15
Dataset
Instances
Dimensions
Size (GB)
deep_5m_96d
5m
96
1.92
syn_10m_64d
10m
64
2.56
syn_1m_1536d
1m
1536
6.14
mnist_2m_784d
2m
784
6.27
syn_2m_1536d
2m
1536
12.29
syn_10m_512d
10m
512
20.48
Table 9: Dataset statistics and storage size.
Algorithm
deep_5m_96d
syn_10m_64d
syn_1m_1536d
mnist_2m_784d
syn_2m_1536d
syn_10m_512d
mnist_8m_784d
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
6925.58
1.00×
39260.30
1.00×
1776.60
1.00×
3676.36
1.00×
7355.30
1.00×
97236.40
1.00×
74407.90
1.00×
faissgpu
525.83
13.17×
1886.65
20.81×
191.62
9.27×
368.77
9.97×
745.33
9.87×
6594.34
14.75×
5985.10
12.43×
symwarp
236.77
29.25×
814.36
48.21×
66.66
26.65×
128.79
28.55×
240.78
30.55×
2278.88
42.67×
2121.55
35.07×
Table 10: Runtime ( T , in seconds) comparison on large-scale datasets. Speedup (SUP) is computed relative to the knncuda baseline. The fastest runtime for each dataset is shown in bold.
Algorithm
16d
32d
64d
128d
256d
512d
1024d
2048d
4096d
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
20.03
1.00×
23.71
1.00×
32.46
1.00×
49.87
1.00×
84.85
1.00×
157.00
1.00×
300.80
1.00×
587.10
1.00×
1159.20
1.00×
faissgpu
4.72
4.24×
5.01
4.73×
5.25
6.18×
7.04
7.08×
10.97
7.73×
18.54
8.47×
34.34
8.76×
65.54
8.96×
129.40
8.96×
symwarp
2.65
7.56×
2.89
8.20×
3.01
10.78×
3.60
13.85×
4.70
18.05×
7.24
21.69×
12.32
24.42×
22.48
26.12×
42.75
27.12×
Table 11: Runtime ( T , in seconds) comparison on synthetic datasets with 500k instances. Speedup (SUP) is computed relative to the knncuda baseline. The fastest runtime for each dimensionality is shown in bold.
Figure 19
Algorithm
2d
32d
256d
1024d
2048d
4096d
8192d
16384d
32768d
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
pycpu
7.69
1.00×
123.66
1.00×
1174.51
1.00×
3933.25
1.00×
7562.34
1.00×
14834.52
1.00×
29426.31
1.00×
58314.25
1.00×
–
–
knncuda
0.43
17.88×
0.47
263.11×
1.08
1087.51×
3.20
1229.14×
5.98
1264.61×
11.55
1284.37×
22.69
1296.88×
45.28
1287.86×
91.64
1.00×
faissgpu
0.31
24.81×
0.32
386.44×
0.44
2669.34×
0.88
4469.60×
1.44
5251.63×
2.73
5433.89×
6.08
4839.85×
10.77
5414.51×
21.29
4.30×
symwarp
0.12
64.08×
0.12
1030.50×
0.15
7830.07×
0.26
15127.88×
0.39
19390.62×
0.69
21499.30×
1.24
23730.90×
2.38
24501.79×
4.65
19.71×
Table 12: Runtime ( T , in seconds) comparison on synthetic datasets with 50k instances. Speedup (SUP) is computed relative to the pycpu baseline. At 32768d, speedup is computed relative to knncuda because pycpu did not complete. The fastest runtime for each dataset is shown in bold.
Algorithm
deep_200k_96d
deep_500k_96d
mnist_70k_2d
mnist_70k_784d
T
SUP
T
SUP
T
SUP
T
SUP
pycpu
9543.81
1.00×
58307.94
1.00×
15.51
1.00×
5125.48
1.00×
knncuda
6.25
1527.01×
33.94
1717.97×
0.51
30.41×
4.50
1139.00×
faissgpu
1.60
5964.88×
6.87
8487.33×
0.37
41.92×
1.05
4881.41×
symwarp
0.94
10152.99×
3.66
15931.13×
0.16
96.94×
0.33
15531.76×
Table 13: Runtime ( T , in seconds) comparison on Deep1B and MNIST datasets. Speedup (SUP) is computed relative to the pycpu baseline. The fastest runtime for each dataset is shown in bold.
Figure 22
Algorithm
k=5
k=25
k=50
k=100
k=200
k=300
k=400
k=500
k=600
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
394.25
1.00×
441.31
1.00×
472.63
1.00×
619.69
1.00×
1007.56
1.00×
1471.92
1.00×
1991.05
1.00×
2569.18
1.00×
3175.71
1.00×
faissgpu
52.15
7.56×
52.54
8.40×
53.92
8.77×
56.46
10.98×
65.12
15.47×
76.12
19.34×
84.65
23.52×
92.33
27.83×
111.77
28.41×
symwarp
22.52
17.51×
23.46
18.81×
24.76
19.09×
26.41
23.46×
30.34
33.21×
35.11
41.92×
41.48
48.00×
47.22
54.41×
56.08
56.63×
Table 14: Runtime ( T , in seconds) Comparison on the GloVe Dataset ( 1.2M instances, 200 dimensions) with Number of Clusters Fixed at c=25 , Varying Number of Nearest Neighbors k . Speedup (SUP) is computed relative to the knncuda baseline. The fastest runtime per column is shown in bold.
Algorithm
k=4
k=8
k=16
k=32
k=64
k=128
k=256
k=512
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
212.62
1.00×
211.32
1.00×
213.04
1.00×
222.35
1.00×
221.19
1.00×
236.52
1.00×
273.19
1.00×
359.40
1.00×
faissgpu
27.52
7.73×
25.74
8.21×
25.28
8.43×
25.52
8.71×
26.14
8.46×
27.60
8.57×
30.10
9.08×
37.12
9.68×
symwarp
11.76
18.08×
9.86
21.43×
9.31
22.88×
9.48
23.45×
10.04
22.03×
10.48
22.57×
11.74
23.27×
13.56
26.50×
Table 15: Runtime ( T , in seconds) Comparison on the MNIST Dataset (500K instances, 784 dimensions) with Number of Clusters Fixed at c=10 , Varying Number of Nearest Neighbors k . Speedup (SUP) is computed relative to the knncuda baseline. The fastest runtime per column is shown in bold.
Figure 25
Algorithm
k=5
k=25
k=50
k=100
k=200
k=300
k=400
k=500
k=600
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
46.19
1.00×
46.51
1.00×
46.65
1.00×
47.48
1.00×
49.50
1.00×
52.06
1.00×
54.40
1.00×
57.36
1.00×
60.06
1.00×
faissgpu
6.72
6.87×
6.96
6.68×
7.15
6.52×
7.48
6.35×
8.25
6.00×
8.94
5.82×
9.65
5.64×
10.27
5.59×
11.13
5.40×
symwarp
2.17
21.29×
2.37
19.62×
2.56
18.22×
2.86
16.60×
3.40
14.56×
4.13
12.61×
4.78
11.38×
5.27
10.88×
5.96
10.08×
Table 16: Runtime ( T , in seconds) comparison on the image-patch dataset with 200k instances and 32×32 dimensions. The number of clusters is fixed at c=64 , while the number of nearest neighbors k is varied. Speedups (SUP) are computed relative to knncuda . The fastest runtime per column is shown in bold.
Algorithm
k=10
k=20
k=40
k=80
k=160
k=320
k=640
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
38.55
1.00×
41.87
1.00×
54.69
1.00×
52.37
1.00×
72.14
1.00×
124.11
1.00×
236.21
1.00×
faissgpu
6.87
5.61×
7.08
5.91×
7.27
7.52×
8.01
6.54×
9.42
7.66×
13.42
9.25×
23.04
10.25×
symwarp
3.21
12.01×
3.36
12.46×
3.59
15.23×
4.21
12.44×
4.83
14.94×
7.38
16.82×
12.45
18.97×
Table 17: Runtime ( T , in seconds) Comparison on Synthetic Dataset (500K instances, 128 dimensions) with Number of Clusters Fixed at c=30 , Varying Number of Nearest Neighbors k . Speedup (SUP) is computed relative to the knncuda baseline. The fastest runtime per column is shown in bold.
Figure 28
Algorithm
c=5
c=25
c=50
c=100
c=200
c=400
c=800
c=1600
c=3200
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
427.90
1.00×
429.05
1.00×
429.33
1.00×
428.75
1.00×
428.75
1.00×
428.91
1.00×
429.16
1.00×
429.06
1.00×
430.02
1.00×
faissgpu
54.40
7.87×
54.63
7.85×
54.24
7.92×
54.25
7.90×
54.38
7.88×
54.63
7.85×
55.08
7.79×
54.98
7.80×
56.03
7.67×
symwarp
23.20
18.44×
23.19
18.50×
23.21
18.50×
23.21
18.47×
23.19
18.49×
23.46
18.28×
23.83
18.01×
23.83
18.01×
24.89
17.28×
Table 18: Runtime ( T , in seconds) comparison on the GloVe 1.2M×200 d dataset with k=20 for varying numbers of clusters ( c ). Speedup (SUP) is reported relative to the knncuda baseline. The best runtime for each value of c is shown in bold.
Algorithm
c=5
c=25
c=50
c=100
c=200
c=400
c=800
c=1600
c=3200
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
225.11
1.00×
225.04
1.00×
225.19
1.00×
225.01
1.00×
225.02
1.00×
224.94
1.00×
225.21
1.00×
225.21
1.00×
225.23
1.00×
faissgpu
25.82
8.72×
25.79
8.73×
25.15
8.95×
26.14
8.61×
26.09
8.62×
26.13
8.61×
26.03
8.65×
26.36
8.54×
26.34
8.55×
symwarp
9.51
23.67×
9.52
23.64×
9.49
23.73×
9.46
23.79×
9.58
23.49×
9.52
23.63×
9.52
23.66×
9.76
23.07×
9.78
23.03×
Table 19: Runtime ( T , in seconds) comparison on the MNIST 500k×784 d dataset with k=32 for varying numbers of clusters ( c ). Speedup (SUP) is reported relative to the knncuda baseline. The best runtime for each value of c is shown in bold.
Figure 31
Algorithm
c=4
c=8
c=16
c=32
c=64
c=128
c=256
c=512
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
46.95
1.00×
47.07
1.00×
48.02
1.00×
48.00
1.00×
47.98
1.00×
47.99
1.00×
48.01
1.00×
48.03
1.00×
faissgpu
6.92
6.78×
6.96
6.76×
6.97
6.89×
6.97
6.89×
7.05
6.81×
7.06
6.80×
7.10
6.76×
7.09
6.77×
symwarp
2.36
19.89×
2.42
19.45×
2.46
19.52×
2.51
19.12×
2.54
18.89×
2.53
18.97×
2.60
18.47×
2.60
18.47×
Table 20: Runtime ( T , in seconds) comparison on the 32×32 image-patch dataset ( 200k instances, 1024 dimensions) with k=45 for varying numbers of clusters ( c ). Speedup (SUP) is reported relative to the knncuda baseline. The best runtime for each value of c is shown in bold.
Algorithm
c=4
c=8
c=16
c=32
c=64
c=128
c=256
c=512
c=1024
c=2048
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
T
SUP
knncuda
42.65
1.00×
42.61
1.00×
42.57
1.00×
42.61
1.00×
42.61
1.00×
42.59
1.00×
42.56
1.00×
42.58
1.00×
42.62
1.00×
42.63
1.00×
faissgpu
7.02
6.08×
7.00
6.09×
6.99
6.09×
7.00
6.09×
7.01
6.08×
6.99
6.09×
7.00
6.08×
7.01
6.07×
7.14
5.97×
7.13
5.98×
symwarp
3.33
12.81×
3.32
12.83×
3.32
12.82×
3.32
12.83×
3.31
12.87×
3.31
12.87×
3.31
12.86×
3.31
12.86×
3.44
12.39×
3.45
12.36×
Table 21: Runtime ( T , in seconds) comparison on the synthetic 500k×128 d dataset with k=18 for varying numbers of clusters ( c ). Speedup (SUP) is reported relative to the knncuda baseline. The best runtime for each value of c is shown in bold.
Figure 21: Impact of the number of clusters c on the runtime of knncuda , faissgpu , and symwarp on the synthetic dataset (500K instances, 128 dimensions) with the number of nearest neighbors fixed at k=18 . Runtime is reported on a logarithmic scale.
Dataset
N
k
c
k NN agreement (%)
DCs matched
Centers matched
ARI
Spiral
312
7
3
100.00
7/7
3/3
1
Flame
240
5
2
99.58
20/20
2/2
1
banana-ball
2,000
11
3
99.95
73/73
3/3
1
R15
600
33
15
100.00
15/15
15/15
1
S2
5,000
31
15
99.30
17/18
14/15
1
MFCCs
7,195
25
10
99.68
46/46
10/10
1
Table 22: Output agreement between SymWarp-FastDEC and FastDEC-pycpu across nine dataset configurations. N denotes the number of data points, k the number of nearest neighbors per point, and c the requested number of clusters. All ARI values are exactly 1 (identical partitions). † The number of DCs equals c , so every DC becomes a center and the significance ranking is not exercised.
Dataset
(k,c)
Sfit
ARI
mnist_70k_784d
(25,10)
1.36×
0.999975
mnist_500k_784d
(25,10)
1.79×
0.986866
deep_2m_96d
(50,80)
1.16×
0.996665
GloVe 200d
(45,20)
1.37×
0.995019
64x64 patches
(25,64)
1.89×
0.999719
syn_10m_64d
(32,25)
1.13×
0.728461
Table 23: TF32 versus FP32 SymWarp-FastDEC : fit-time speedup Sfit=TFP32/TTF32 and ARI between the full FP32 and TF32 partitions. ARI compares the two precisions with each other, not with ground-truth labels. Only syn_500k_16d yields an identical partition.
We present Flash-GMM, a fused Triton kernel for efficient computation of Gaussian Mixture Models (GMMs) over large-scale data in a single GPU pass. By eliminating the need to materialize the full responsibility matrix in GPU memory, Flash-GMM achieves a \textbf{20×} speedup over existing implementations and enables training on datasets more than \textbf{100×} larger than previously feasible on one device. To demonstrate its impact, we integrate Flash-GMM into the IVF coarse quantizer for approximate nearest-neighbor (ANN) search. We show that soft GMM clustering is now a viable drop-in replacement for k-means, and that GMM responsibilities can be leveraged to assign border vectors to multiple clusters. Our approach reaches fixed recall targets with up to 1.7× fewer distance computations, or equivalently, yields +2--12 recall@10 at matched computational cost. We release the kernel as an open-source project.
Memory-efficient scaling on clustering problems without sacrificing statistical accuracy is of central interest for large-scale data analysis and machine learning problems. Nonnegative low-rank (NLR) matrix factorization for K-means is a scalable clustering method, which connects to semidefinite relaxations with optimal average-case exact recovery guarantees. However, a direct GPU implementation of NLR requires multiple large factor-sized buffers and substantial data movements that are essentially memory-bound. In this paper, we introduce GEM-KMeans, a spectrally normalized yet mathematically equivalent NLR formulation that fuses the gradient update, nonnegative projection, and sufficient statistics for normalization and iterate movement into a matrix-multiplication epilogue. Instead of retaining three massive factor-sized arrays, our IO-aware GPU implementation materializes only one single factor with small tile-reduction arrays as additional storage in the High Bandwidth Memory (HBM). We derive explicit memory costs and spectrally normalized smoothness bounds for optimizing the clustering objective function. Accurate clustering is demonstrated at massive scales on synthetic and real datasets, where performance gains of GEM-KMeans over existing GPU-accelerated Lloyd's algorithms involve data-dependent runtime tradeoffs.
Peng Xu, Nihar Koganti, Volodymyr Kindratenko +1
Department of Statistics, University of Illinois Urbana-Champaign · Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign · National Center for Supercomputing Applications, University of Illinois Urbana-Champaign +3
This work addresses community detection in temporal networks through GPU-accelerated extensions of spectral clustering and modularity-based algorithms originally designed for static graphs. Built on the NVIDIA RAPIDS ecosystem, the framework enables the characterization and tracking of communities in snapshot-based dynamic graphs, either by Leiden greedy optimization with multi-GPU support via Dask-based workload distribution, or eigendecomposition of a symmetric Bethe-Hessian operator. Our multislice modularity backend achieves up to roughly three orders of magnitude speedup over the CPU reference under an equal-work budget, depending on graph density and snapshot count, while preserving compatibility with existing graph analytics pipelines. We demonstrate its applicability on real-world and synthetic datasets, facilitating exploratory analysis of structural network properties over time. Such capabilities are relevant across several application domains, such as epidemic spreading, financial systems, cybersecurity, and trajectory and mobility analysis. We release our implementation as free and open-source software, including Python bindings through the NetworkX-Temporal library for ease of use and zero-code acceleration with existing codebases.
Nelson Aloysio Reis de Almeida Passos, Emanuele Carlini, Salvatore Trani
University of Pisa, Dept. of Computer Science, 56127 Pisa PI, Italy · National Research Council, 56124 Pisa PI, Italy