CS Paper Radar

Spectral Analysis for Sparse Matrix Computation: Insights and Potential

Ruifeng Zhang, Xipeng Shen

cs.PF cs.LG ·submitted 2026-08-29 16:50 UTC · v1

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.

Comment
12 pages, 10 figures, 2 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Scaling Fourier-Based Sparse Matrix Analysis on GPUs

cs.PF ·2026-09-17 ·Ruifeng Zhang, Sai Krishna Teja Varma Manthena, Jiajia Li, Xipeng Shen
similarity 0.74
Abstract · 13 pages, 7 figures

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%.

0.19

Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure

cs.LG stat.ML ·2026-08-21 ·Lawrence K. Saul, Ningyuan Huang, Dennis Bollweg, Jeff Soules, Diana C. Halikias
similarity 0.63
Abstract

We investigate when a sparse nonnegative matrix can be recovered from a real-valued matrix of much lower rank by zeroing out its negative elements. The potential for such decompositions suggests a mathematical connection between sparsity and rank; we analyze a number of sparse matrices with this latent low-rank structure and use them to illustrate the geometric origins of this connection. Previous algorithms have discovered these decompositions via an alternating minimization over the factors of a low-rank matrix, but to do so, they have also needed to compute and store another matrix, neither sparse nor low-rank, that is the size of their product. We develop a stochastic, alternating least-squares algorithm that operates on smaller blocks of this dense matrix and scales as a result to much larger problems. We also show how to further accelerate this algorithm with sparse optimizations and customized CUDA kernels. As one example, we use the algorithm to analyze the sparse matrix of synaptic weights for the recently published $\textit{Drosphilia}$ connectome. The nonzero elements of this matrix, with 139,255 rows and columns, record the number of synapses between cells in the nervous system of a female fruit fly. Despite a slowly decaying spectrum of singular values, this matrix exhibits a latent low-rank structure that is predictive of cell categories across multiple levels of specificity.

0.38

FlashDiffusion: Fused Tiled Kernel Spectral Decomposition

cs.LG ·2026-09-18 ·Julio Candanedo
similarity 0.62
Abstract

Diffusion maps, and kernel methods more generally, provide an interpretable nonlinear spectral representation basis for geometric learning. In the geometric limit, small bandwidth, these matrices tend to be high rank and thus require materializing dense Gaussian kernels requires $O(N^2)$ memory. We introduce FlashDiffusion, a matrix-free method that evaluates dense Gaussian kernel blocks in fused GPU tiles and couples the eigensolver to an empirical $β$-flow that selects the finite-sample resolution scale. A continuation over sample size and bandwidth warm-starts increasingly expensive spectral solves from coarser resolutions.

0.23

Graph Learning with Spectral Connectivity Priors for Scarce Data

cs.LG eess.SP ·2026-09-23 ·Mingxiao Liu, Bahar Oveisgharan, Bingyan Zou, Gene Cheung, H. Vicky Zhao +1 more
similarity 0.61
Abstract · 5 pages, 1 figure. Submitted to IEEE ICASSP 2027

Learning a sparse graph from scarce data is practically important but challenging. Motivated by the desirable combination of local sparsity and strong global connectivity exhibited by expander-like graphs, we propose spectral connectivity-regularized graph learning (SCoGL), a framework that incorporates a family of Laplacian spectral priors to explicitly promote global connectivity. Specifically, SCoGL augments a combinatorial-Laplacian-constrained graphical lasso (GLASSO) objective over a target adjacency matrix $\mathbf{W}$ with a general connectivity prior computed from Laplacian eigenvalues. We derive gradients for several representative connectivity priors and develop a projected gradient descent (PGD) algorithm with Armijo backtracking to efficiently optimize $\mathbf{W}$. Experiments show that the proposed SCoGL variants improve graph recovery and enhance downstream tasks such as graph signal denoising when signal observations are scarce.

0.24

Sparse Integer Fourier Transform and Its Application In Machine Learning

cs.MS cs.LG ·2026-11-16 ·Jinyang Li, Jie Chen
similarity 0.60
Abstract

The Discrete Fourier transform, mainly implemented by Fast Fourier Transform (FFT), has been essential for numerous domains, such as digital signal processing and feature extraction in materials design. However, current FFT methods suffer from extensive non-trivial multiplications and twiddle-factor operations in the big data era. To improve the computational efficiency of FFT, this study proposes Sparse Integer Fourier Transform (SIFT), a method that leverages the fast computing of sparsity and small integers, and applies the Radix-n method to derive an FFT. The 2N-point DFT matrix in Radix-n FFT is decomposed into four sparse integer matrices. A diagonal matrix containing complex twiddle factors is efficiently approximated using an optimization strategy while the remaining matrices retain sparsity and integer entries. For radix-32 FFT, SIFT reduces the estimated arithmetic cost by 75%, with RMSE below $2.3765\times10^{-8}$ and MAPE below 0.01089%. We evaluate frequency extraction in a numerical test and an engineering case. In the numerical test, MAPE and RMSE are below 2.016% and $2.536\times10^{-6}$, respectively. For wind turbine fault diagnosis, SIFT extracts compact spectral features that retain fault information while reducing the classifier's input dimensionality relative to the full time series.

0.23

Selection, Representation, and Execution in Sparse Fourier Neural Operators

cs.LG math.NA ·2026-08-30 ·Abdul Qadir Ibrahim, Martin Burger
similarity 0.59
Abstract · 21 pages, 11 figures

Sparse representations are often expected to make models smaller and also reduce inference cost. For Fourier Neural Operators (FNOs), these objectives are not equivalent or do not always align: removing parts of the learned operator can leave the underlying transforms and dense computations unchanged, while changing the grid on which the model is evaluated can introduce overhead of its own. We therefore distinguish sparsity in the representation, in the stored parameters, in the theoretical operation count, and in measured runtime, and present an empirical study of several routes toward sparse FNOs that tests each transition between them separately. Coarsening the execution grid reduces the theoretical cost without reducing measured latency, and adding a correction term recovers accuracy at the cost of making the model slower. Even an 83\% parameter reduction remains slower than the dense baseline under ordinary execution. These results motivate a stricter definition of useful sparsity: the deployed operator must preserve solution accuracy and map its reduced support to a genuinely cheaper execution path.

0.38

Cost-free Spectral Estimation for Adaptive Newton--Schulz in Matrix Optimizers

cs.LG ·2026-09-27 ·Kristi Topollai, Anna Choromanska
similarity 0.59
Abstract

Matrix optimizers such as Muon transform each momentum matrix through an approximate orthogonalization, typically implemented by a small number of Newton-Schulz matrix multiplications. The quality and cost of this approximation depend strongly on the singular-value spectrum of its input, yet existing implementations use the same fixed polynomial routine for every layer and throughout training. We show that this uniform treatment is unnecessary: the computations in the Newton-Schulz method already reveal enough information to make the method adaptive. The Gram matrices formed inside Newton-Schulz iterations yield spectral moments through inexpensive scalar reductions, requiring no additional matrix multiplications. From these moments, we recover an estimate of the empirical singular-value distribution and use it to select a polynomial routine specialized to the current matrix. This turns Newton--Schulz orthogonalization into a spectrum-adaptive procedure that responds to differences across both layers and training time. On saved momentum matrices, spectral estimation substantially reduces orthogonalization error at a fixed iteration budget or reaches the same accuracy with fewer iterations, and in GPT pretraining up to 1B parameters it lowers the validation loss of two matrix optimizers. Our results suggest that matrix-function operations inside optimizers need not be designed for a conservative worst-case spectrum: they can cheaply measure the spectrum they are already processing and specialize computations accordingly.

0.15

Rethinking Sparse Formats for RISC-V: A Hierarchical Approach to High-Performance SpMV

cs.DC cs.PF ·2026-09-10 ·Anna Pirova, Anastasia Vodeneeva, Konstantin Kovalev, Alexander Ustinov, Maksim Zagriadskov +5 more
code/data similarity 0.59
Abstract

The sparse matrix-vector multiplication (SpMV) algorithm is a fundamental computational kernel of linear algebra and serves as a building block for numerous applications, primarily iterative solvers for systems of linear equations used in scientific and engineering simulations. This paper compares vectorized implementations of the SpMV algorithm across eight established sparse matrix storage formats and proposes a novel modification of the CSR format, Hierarchical CSR (HCSR), which enhances SpMV performance on RISC-V processors. Our SpMV implementations utilize RVV 1.0 intrinsics and are publicly available as an open-source C++ library named RVVLASparse. Computational experiments conducted on SpacemiT K1 and K3 RISC-V boards demonstrate that the proposed HCSR format achieves the shortest execution time among all considered formats across a broad class of sparse matrices. HCSR outperforms the best CSR implementation on 8 cores, yielding an average speedup for double precision of 19% on K1 (13% on K3) and for single precision of 36% on K1 (34% on K3).

0.35