Sparse computations are fundamental to scientific computing, graph analytics, and machine learning, yet their performance is highly sensitive to the diverse sparsity and patterns. This is because cache reuse, memory coalescing, and load balancing depend critically on the sparsity patterns. This work gives the first known exploration of the connections between sparse matrix computation and spectral analysis by treating sparse matrices as two-dimensional signals and analyzing their frequency-domain representations through Fast Fourier Transform. We show that spectral signatures uncover global structural characteristics that are not sufficiently captured by conventional spatial statistics and provide complementary information for understanding sparse computation performance. Experiments on incorporating spectral features into machine-learning-based SpMV format selection demonstrate the usefulness of such spectral analysis over a state-of-the-art spatial-only model. By uncovering the principled connections between spectral characteristics and sparse matrix computations, this work introduces a novel analytical perspective into sparse computation, and provides a new approach to enhancing the current sparse structure characterization and optimization. On pruned LLM decoding, adding spectral features improves kernel selection and yields 1.035--1.245× kernel speedups.
Figures & tables
Figure 1. Illustration of the three FFT features used in this work: Radial energy, Directional energy, and spectrum Entropy. The background images for Radial and Directional, as well as the images used for Entropy, are FFT magnitude spectra obtained by shifting the zero-frequency component to the origin and applying log scaling. Schematic of radial rings, directional sectors, and entropy over FFT magnitude spectra.
Figure 2. Canonical sparsity patterns (left) and their corresponding FFT log-magnitude spectra after shifting zero-frequency component to the center (right). The sparse matrices size is 1024×1024 . For visualization clarity, a Gaussian smoothing is applied to the spectra to enhance thin high-energy structures without altering the underlying frequency characteristics. Six synthetic sparsity patterns paired with their shifted log-magnitude FFT spectra.
Figure 3. Effect of intra-structure sparsity and noise on a sparse matrix with diagonal band (width=33). The original matrix size is 1024×1024 and the density map size is 128×128 . A diagonal-band matrix and spectrum under controlled deletion and noise, before and after density-map aggregation.
Figure 4. Clustering of matrices by radial energy (a), directional energy (b), and spectral entropy (c). CiF denotes cluster i for feature F . Each panel shows cluster representatives with their compressed 256×256 density maps and magnitude spectra. Three grids of representative sparse matrices and spectra grouped by radial energy, directional energy, and entropy.
Figure 5. Clustering using combination of all features. Balanced K-means is applied to avoid tiny communities. Representative sparse matrices and FFT spectra from balanced clustering over combined spectral features.
Figure 6. Distribution of samples across clusters. The x-axis represents the low-frequency energy ratio, computed as the sum of the first four radial-energy bins; The y-axis denotes spectral entropy. The size of each point is proportional to the directional strength in the 45∘ sector of the sparse matrix. Scatterplot of low-frequency energy and entropy, with color denoting cluster and point size denoting diagonal directional strength.
Figure 7. Distribution of the best kernels for the 1,170 SuiteSparse SpMV matrices. Only classes with ≥ 5 samples are retained for training. Pie chart showing the best-kernel distribution for the SpMV benchmark suite.
Feature set
Tolerant Acc.
Strict Acc.
#Feat
Base
0.615
0.564
4
Spectral (FFT)
0.723
0.650
24
Spatial (WISE)
0.757
0.676
84
Spatial+Spectral
0.793
0.701
104
Table 1. SpMV format selection accuracy (strict and 5% tolerance). Adding spectral features to the spatial baseline improves tolerant accuracy by 3.6 percentage points.
Figure 8. SpMV speedup of model-predicted formats. Left: speedup versus each fixed baseline kernel ( y=1 indicates parity). Right: per-matrix speedup versus CSR, sorted in ascending order of low-frequency energy ratio. A bar chart of model-selected SpMV speedups and a per-matrix speedup plot sorted by spectral energy.
Pruning Method
Sparsity
Spatial Acc.
Spatial+Spectral Acc.
Speedup
Magnitude
80%
73.18%
83.64%
1.110 ×
Magnitude
90%
82.95%
86.52%
1.035 ×
WANDA
80%
82.20%
95.53%
1.245 ×
WANDA
90%
68.79%
75.15%
1.073 ×
Overall
80/90%
76.78%
85.21%
1.087 ×
Table 2. SpMV format selection results for pruned LLM decode. Acc denotes tolerant accuracy. Speedup compares Spatial+Spectral model’s kernel runtime against Spatial model.
Figure 9. Top-10 FFT features for SpMV Spectral models. Left: SuiteSparse; right: LLM-matrices. Two side-by-side ranked bar charts of the ten most important FFT features for SuiteSparse and pruned-LLM SpMV Spectral predictors.
Figure 10. Four case-study examples in the same sparse-matrix/FFT format where Spectral models select the fastest kernel while Spatial models miss. Four sparse-matrix and FFT pairs arranged two per row: two SuiteSparse SpMV cases followed by two pruned-LLM SpMV cases.
Sparse matrix computation performance on GPU depends on how representation and execution schedule match the input structure and target hardware. No single implementation consistently dominates across sparsity patterns, operators, and hardwares. Existing sparse compilers and specialized systems cannot cover all of them simultaneously. We present SparseDitto, an agentic sparse compilation framework for sparse matrix computation on GPUs. It jointly synthesizes representation, execution schedule, and hardware mapping in a unified compilation plan. Structural analysis and a learned template-ranking prior guide architecture-aware synthesis. LLM-guided lowering realizes each plan as CUDA code, while target-GPU profiling drives plan refinement. SparseDitto covers multiple operators, e.g., SpMV, SpMM, and SpGEMM, and various representations within one framework. It can also automatically adapt to different hardwares. Across various SuiteSparse matrices, SparseDitto achieves geometric-mean speedups over cuSPARSE of 2.68× on an NVIDIA RTX PRO 6000 and 2.79× on an NVIDIA H200 (up to 146.61×). Its generated SpMM kernels accelerate full-batch GCN training by up to 3.39×.
Shiyang Li, Guangyan Sun, Jinwei Tang +3
University of Minnesota Minneapolis, MN, USA · Northeastern University Boston, MA, USA
Large Language Models (LLMs) achieve strong performance across many domains, but their efficiency is limited by the quadratic cost of attention with respect to prompt length. Sparse attention reduces this cost by retaining only a small fraction of query-key interactions to approximate the full attention matrix. However, existing methods are trapped in a mathematically wrong view: they simply keep large scalar entries or high-mass regions of the attention matrix. This treats the attention matrix as a bag of values, ignoring that it is used as a structured matrix whose entries jointly determine the attention output through multiplication with value vectors. We argue that this is the core conceptual issue: sparse attention should be formulated as matrix approximation, not as blindly choosing the largest values from a bag of entries. Based on this view, we propose Matrix Approximation Sparse Attention (MASA). MASA replaces raw attention-mass ranking with a closed-form score that measures how much each sparse unit reduces matrix-product approximation error. As a theory-grounded plug-in correction, MASA can be added to existing sparse attention frameworks without changing their sparse kernels or budgets. Extensive experiments across multiple sparse attention methods, benchmarks, and LLM backbones show consistent accuracy gains, supporting both MASA and the matrix-approximation view of sparse attention.
Rearranging the rows or columns of a sparse matrix using an appropriate ordering can significantly reduce fill-ins, i.e., new nonzeros introduced during matrix factorization, decreasing memory usage and runtime. However, finding an ordering that minimizes fill-ins is NP-complete. Existing approaches, including graph-theoretic and deep learning methods, rely on surrogate objectives without theoretical guarantees. The Fill-Path Theorem reveals a direct and intrinsic relationship between fill-in generation and the sparse structure of the matrix as path triplet inequalities. Here we first employ a multigrid graph network to capture structural information for each vertex. We then derive a triplet sampling strategy based on inequalities. Finally, we introduce an end-max chain loss function to reduce the number of triplets whose predicted scores satisfy these inequalities. Experimental evaluations on the publicly available SuiteSparse matrix collection demonstrate the superiority of the proposed method in terms of both fill-in reduction and speedup in LU factorization time.
Ziwei Li, Tao Yuan, Fangfang Liu +3
Institute of Software, Chinese Academy of Sciences, Beijing, China