Spectral Analysis for Sparse Matrix Computation: Insights and Potential

Ruifeng Zhang; Xipeng Shen

cs.PFAug 29, 2026

Spectral Analysis for Sparse Matrix Computation: Insights and Potential

Authors: Ruifeng Zhang, Xipeng Shen

Organizations: North Carolina State University Raleigh, North Carolina, USA

Abstract

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 $\times$ 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\times 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\times 1024$ and the density map size is $128\times 128$ . A diagonal-band matrix and spectrum under controlled deletion and noise, before and after density-map aggregation.

Panel of Figure 4 — Figure 4. Clustering of matrices by radial energy (a), directional energy (b), and spectral entropy (c). $C_{i}^{F}$ denotes cluster $i$ for feature $F$ . Each panel shows cluster representatives with their compressed $256{\times}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^{\circ}

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 $\geq$ 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 $\times$
Magnitude	90%	82.95%	86.52%	1.035 $\times$
WANDA	80%	82.20%	95.53%	1.245 $\times$
WANDA	90%	68.79%	75.15%	1.073 $\times$
Overall	80/90%	76.78%	85.21%	1.087 $\times$

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 Multiplication

See all 10 papers

SparseDitto: An Agentic Sparse Compilation Framework through Architecture-Aware Synthesis on GPUs
Aug 5, 2026Shiyang Li, Guangyan Sun, Jinwei Tang +3GPU Kernel Optimization High-Performance Computing
University of Minnesota Minneapolis, MN, USA · Northeastern University Boston, MA, USA
Sparse Attention Is Matrix Approximation, Not Choosing from a Bag of Values
Oct 7, 2026Fang Wan, Xufeng Liu, Fan Li +1Sparse Attention Efficient Attention
Stony Brook University · Duke University
Self-Supervised Learning for Sparse Matrix Reordering
May 17, 2026Ziwei Li, Tao Yuan, Fangfang Liu +3
Institute of Software, Chinese Academy of Sciences, Beijing, China

Aug 5, 2026J/K move · Enter open · S save

SparseDitto: An Agentic Sparse Compilation Framework through Architecture-Aware Synthesis on GPUs

Shiyang Li, Guangyan Sun, Jinwei Tang, Yanzhi Wang+2

University of Minnesota Minneapolis, MN, USA · Northeastern University Boston, MA, USA

GPU Kernel Optimization High-Performance Computing GPU Kernel Generation Sparse Matrix Multiplication

Open paper AskPDF arXiv

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\times

on an NVIDIA RTX PRO 6000 and

2.79\times

on an NVIDIA H200 (up to 146.61

\times

). Its generated SpMM kernels accelerate full-batch GCN training by up to

3.39\times

Abstract

Sparse Matrix Multiplication

Explore similar work

SparseDitto: An Agentic Sparse Compilation Framework through Architecture-Aware Synthesis on GPUs

Sparse Attention Is Matrix Approximation, Not Choosing from a Bag of Values

Self-Supervised Learning for Sparse Matrix Reordering