CS Paper Radar

Certificate-Governed CRT Sparse FFT: Verified Global-Label Candidate Construction under Explicit Decoding Models

Aaron R. Flouro, Shawn P. Chadwick

eess.SP cs.DS ·submitted 2026-09-28 01:24 UTC · v1

Abstract

We present a deterministic CRT-based sparse Fourier architecture for exact recovery of noiseless, on-grid, at-most-\(k\)-sparse spectra with an engineered transform length. The transform length \(N\) is selected as an exact product of small pairwise-coprime stage primes, allowing each stage to use transforms whose size scales with the sparsity rather than the ambient dimension. Three co-prime-increment time shifts provide a one-sided singleton-consistency screen: every genuine singleton passes, while passing collision bins remain provisional candidates. Each candidate bin is mapped by a total label-emission rule to at most one global frequency label, and per-stage label sets are intersected, yielding a deterministic \(O(k)\) candidate bound for every input. Candidate construction uses \(O(k\log N)\) samples. In a comparison real-RAM model with exact arithmetic and exact phase evaluation but without unit-cost root-index decoding, it requires \(O(k\log^2 N/\log k)\) arithmetic operations; in a stronger root-index-oracle model the arithmetic cost is \(O(k\log N)\). Under all-stage genuine-singleton survival, the candidate set contains the true support. Exactness, however, does not depend on that survival condition: a consecutive-sample residual verifier accepts a sparse reconstruction only when it is exact, and all failures route to a dense FFT. The resulting hybrid algorithm therefore returns the exact spectrum for every input in the stated noiseless, on-grid, at-most-\(k\)-sparse model, with \(O(N\log N)\) worst-case runtime. The verified sparse path additionally incurs an \(O(k^2)\) verifier cost in the root-index-oracle model. Neither computational model is a bit-complexity model.

Comment
42 pages, 1 figure, 6 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Sparse Integer Fourier Transform and Its Application In Machine Learning

cs.MS cs.LG ·2026-11-16 ·Jinyang Li, Jie Chen
similarity 0.55
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

A Numerical Refinement of an Exact Discrete Fourier Transform Bound

cs.CC cs.DS ·2026-10-31 ·Zhihao Yao, Sichao Liu
theory similarity 0.53
Abstract

We refine the numerical bounds in Kartal's instantiation of Sussman's exact discrete Fourier transform construction. For every integer n >= 1, the resulting algorithm computes the length-n transform with work O(n (log n)^(1 - delta)), where delta = 0.0030201659. The bound holds in an exact complex-arithmetic RAM model with a supplied canonical root of unity. This final exponent saving exceeds the earlier certified parameter C_0 = 0.00302016 by 5.9 x 10^(-9). We retain the underlying circuit, tighten rational bounds for sums of powers of its block and target ranks, and increase the fixed tensor power from 7760 to 11640. These bounds establish the inequalities for Sussman's recursion at the intermediate certificate parameter C = 0.00302016595. The gap C - delta absorbs the overhead of recursion and Fourier reduction. The resulting transform theorem is proved in Lean and checked against the reference problem statement.

0.25

Exact Factorisation and Fast Computation of Invertible Constant-Q Transforms

eess.SP cs.SDeess.ASmath.NA ·2026-09-24 ·Facundo Franchino, Eloi Moliner, Vesa Välimäki
similarity 0.53
Abstract · 5 pages, 2 figures, 2 tables. Submitted to ICASSP 2027

The constant-Q transform (CQT) represents audio on a logarithmic frequency axis. Its nonstationary Gabor formulation is exactly invertible, but the unequal numbers of time coefficients in its bands complicate GPU computation. An exact factorisation combines spectral selection, conjugation, windowing, and reordering into a fixed map between one packed Fourier transform and the shorter band inverse transforms. The factors give waveform reconstruction, real adjoints for backpropagation, and bounds on arithmetic depth and block width; overlapping slices permit streaming with bounded memory. Tests on two GPU models show that Flash-CQT reduces analysis-synthesis round-trip time by factors of two to eight relative to a baseline computing the same CQT. The proposed implementation also uses over 30% less peak temporary workspace and reaches a negligible reconstruction error, with a signal-to-noise ratio of about 130 dB, in single-precision floating-point arithmetic. These advances make Flash-CQT a practical, computationally efficient front end for spectral analysis and modern audio machine-learning systems.

0.28

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

Memory Bandwidth, Not FLOPs: Profiling and Accelerating Query-Based Segmentation Decoders on Edge GPUs

cs.AR cs.LGcs.PFeess.IV ·2026-09-29 ·Oliver Busemann, Torben Töniges, Martin Atzmueller
published similarity 0.52
Abstract · Accepted at the British Machine Vision Conference (BMVC) 2026. Supplementary material included

Query-based segmentation models achieve strong performance even under real-time inference on workstation GPUs. On edge devices, however, we show their transformer decoders are deeply memory-bandwidth-bound, a bottleneck invisible to standard FLOP analysis that worsens with input resolution and limited DRAM bandwidth. An FP16 roofline analysis with tensor-core GEMMs active and hardware DRAM counters shows that the non-tensor-core aggregates of FastInst and Mask2Former reach only $2.5\%$ to $6\%$ of the CUDA-core ridge yet account for $53\%$ to $70\%$ of decoder time and $61\%$ to $71\%$ of decoder bytes. The largest individual kernels sustain up to $90\%$ of nominal peak DRAM bandwidth, effectively saturating the memory bus. The bottleneck is therefore not primarily low GEMM intensity, but cross-kernel activation traffic. CompactInst addresses this bottleneck using parameter-free spatial pooling at $4{\times}$, which reduces the bytes moved within the transformer decoder, while a two-convolution refinement head recovers spatial detail. Under TensorRT FP16 on Jetson Orin Nano, CompactInst delivers decoder speedups from $2.35{\times}$ to $4.74{\times}$ and model speedups from $1.57{\times}$ to $2.62{\times}$ as input resolution grows, while closely matching accuracy ($-0.4$ AP on COCO val2017, $+0.2$ AP on Cityscapes test). A heavier variant with $2.57{\times}$ more decoder FLOPs still runs its decoder $1.74{\times}$ faster on the most bandwidth-constrained device, confirming at the deployment level that decoder bytes, not FLOPs, govern latency.

0.31

FORGE: Procedural Weight Generation for Sparse MoE Inference

cs.AR cs.DCcs.LG ·2026-10-12 ·Chanyoung Moon, Travis Pence, Daisuke Yamada, Jiaqi Mo, Yanxin Zhang +2 more
top venue similarity 0.52
Abstract · 16 pages. Accepted to ASPLOS 2027

We introduce FORGE (Fast On-chip Rotor Generation for Experts), a procedural weight generation system for Sparse Mixture-of-Experts (MoE) inference. Rather than storing and loading every expert weight tensor from HBM, we show how a compact accelerator inside each Streaming Multiprocessor can regenerate them on-the-fly from $O(\log^2 d)$ rotor parameters per projection. Per replaced layer, gigabytes of stored expert weights are approximated with under a megabyte of seeds. This addresses the dual memory bottleneck of autoregressive Sparse MoE decode, where per-expert FFN operations are HBM-bandwidth-bound at small routed-token counts and the aggregate expert footprint forces multi-node Expert Parallelism (EP) with all-to-all traffic. We realize the approach as the Rotor Generation Unit (RGU), a fixed-function datapath that generates FFN weight tiles without competing with Tensor Core execution. With 30% of the MoE FFN layers replaced across five Sparse MoE models, we estimate 1.3-2.8x higher system throughput at matched GPU count and 1.10-1.15x lower per-user decode latency at short context. In exchange, downstream accuracy on three model families falls below that of the same model fine-tuned without rotor replacement, and the replacement ratio controls this tradeoff. FORGE also expands KV cache capacity by 1.2-2.6x. It is agnostic to the bit width at which weights are stored, so it can compose with quantization. The RGU is fully implemented/verified in SystemVerilog at ~0.9% SM area overhead (0.032 mm^2/SM, 7nm).

0.37

On the Additive FFT Techniques over Binary Extension Fields

cs.CR ·2026-08-21 ·Susanta Samanta, Mohammadtaghi Badakhshan, Guang Gong
unusual similarity 0.51
Abstract

Motivated by Bailey's four-step FFT algorithm (1989), we develop additive FFT techniques for polynomial evaluation over affine subspaces of binary extension fields. Our key insight is that the Taylor expansion with respect to vanishing polynomials of subspaces provides a structural counterpart to Bailey's matrix formulation. It decomposes an additive FFT (AFFT) into independent sub-AFFTs associated with the columns and rows of a matrix. We first present a general-basis AFFT that applies to any ordered basis and any split of the dimension, providing a unified baseline for measuring the gains from specialization. We then specialize the framework to the Cantor special basis and obtain two AFFT algorithms. The first supports an arbitrary decomposition of the AFFT dimension and exploits the Cantor special basis structure to perform the Taylor expansion stage without finite field multiplications. The second uses a decomposition that preserves the binomial form of the relevant subspace polynomials. It requires exactly $\frac{1}{2}n\log_2 n$ multiplications, together with a closed-form addition count determined by the binary representation of $m$. Our implementation results show that this algorithm is faster than the LCH AFFT over a Cantor special basis in 37 of the 42 configurations tested across two hardware platforms. This performance advantage stems from its fully recursive structure, which provides memory locality by design and avoids separate basis-conversion and evaluation stages. Finally, in a separate analysis, we formalize the notion of partial Cantor special bases and identify parameter regimes in which both the von zur Gathen-Gerhard algorithm and our general-basis AFFT require fewer additions and multiplications than the first Gao-Mateer algorithm.

0.27

Hardware-Native Joint Sparse-Quantization for Trillion-Scale Mixture-of-Experts

cs.AR cs.AIcs.LG ·2026-09-29 ·Kwanhee Lee, Namhoon Lee, Dan Alistarh
similarity 0.51
Abstract

Mixture-of-Experts (MoE) architectures allow frontier language models to scale to trillions of parameters, but their deployment is constrained by massive memory footprints and memory-bandwidth limitations. Although modern accelerators provide Sparse Tensor Cores (SpTCs) that reduce weight storage and increase throughput through low-precision semi-structured sparsity, exploiting them for MoEs remains challenging because of substantial model-quality degradation and the lack of grouped sparse GEMM primitives. We present an end-to-end hardware-software co-design framework that compresses expert weights into hardware-native, low-precision sparse representations and accelerates their execution on SpTCs. Algorithmically, our framework relaxes discrete semi-structured support selection through continuous reparameterization, enabling differentiable joint optimization with quantized weights under a router-weighted reconstruction objective and scalable expert-parallel compression. Systemically, we develop a custom grouped sparse GEMM kernel tailored to low-precision sparse MoE inference on SpTCs. Across MoE models ranging from 30 billion to one trillion parameters, our framework improves state-of-the-art joint sparse-quantization accuracy by up to 4.35 percentage points while preserving 96.09% of the original model's performance. On NVIDIA B200 GPUs, our kernel outperforms the vendor baseline by up to $1.65\times$, increasing serving throughput by $1.18\times$ and reducing end-to-end latency by up to $4.03\times$. These results establish hardware-software co-design as a practical path toward scalable and efficient MoE deployment.

0.21