Scalable GPU method boosts sparse matrix spectral analysis efficiency
Scaling Fourier-Based Sparse Matrix Analysis on GPUs
Performance
Summary
Analyzing large, sparse matrices—like those used in networks and machine learning—is difficult because they're huge and mostly empty. The authors created a new way to use fast Fourier transforms (FFT) on graphics cards that handles these big sparse matrices more efficiently and with less memory. Their method also includes smart ways to compress data so the calculations run faster without losing much accuracy. This makes it easier to understand the global structure of large graphs and complex data.
What this means in practice
- •For machine learning engineers: Process large graph-based datasets faster and with less GPU memory when building graph neural networks using spectral features.
- •For scientific computing teams: Analyze global structures of large sparse matrices efficiently on GPUs for simulations and scientific models involving large-scale graphs.
Authors
Ruifeng Zhang, Sai Krishna Teja Varma Manthena, Jiajia Li, Xipeng Shen
Abstract
Sparse computations are important workloads in applications such as scientific computing, graph neural networks (GNNs), and machine learning. While many sparse operations can benefit from modern GPUs, the sparsity pattern remains important to performance because it affects memory coalescing, block organization, and load balancing. Previous studies show that spectral signatures can help analyze the global structure of sparse matrices. The fast Fourier transform (FFT) is commonly used to extract spectral signatures, and efficient GPU FFT libraries are available. However, sparse matrices, especially adjacency matrices for large graphs, tend to be very large and sparse. Existing dense-matrix-based FFT implementations are difficult to scale up, making the spectral patterns of these matrices difficult to obtain. We therefore propose a three-fold research approach comprising a lossless Binary-Sparse FFT (BS-FFT) and two compression methods: Elastic BS-FFT, which reuses the BS-FFT pipeline on a sampled frequency grid, and density-map-based spatial compression. Experiments show that BS-FFT reduces GPU memory use by 2.9--11.6 times relative to dense cuFFT and completes all 15 GNN adjacency matrices where dense cuFFT completes 6 on a 40 GB A100. Elastic BS-FFT and Density Map compression reduce GPU computation time by 2.0--1466.4 times relative to BS-FFT with spectral feature error of only 0.16% to 11.56% across the sampling rates from 6.25% to 0.0061%.