CS Paper Radar

On the Additive FFT Techniques over Binary Extension Fields

Susanta Samanta, Mohammadtaghi Badakhshan, Guang Gong

cs.CR ·submitted 2026-08-21 08:20 UTC · v1
unusual

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.

Closest papers

Nearest neighbours by meaning across the whole index.

32-point DFT Approximations Based on Minimal Frobenius Error and DFT Symmetries

eess.SP math.NA ·2026-09-01 ·L. Andrade-Silva, W. A. S. Aleixo, R. J. Cintra
similarity 0.60
Abstract · 10 pages, 2 figures, 5 tables

This work introduces low-complexity, multiplierless approximations for the 32-point discrete Fourier transform. The proposed methods are obtained by minimizing the Frobenius error compared against the DFT matrix over a set of trivial multipliers. A row-wise, symmetry-constrained parameterization is employed to reduce the search space size, rendering the task computationally tractable. The resulting approximations could outperform the reference method in the literature according to energy-based error measurements. A sparse matrix factorization is provided for efficient computation; the arithmetic costs are 152 real additions and 34 bit-shifts only.

0.23

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

A Fast Algorithm for Subspace Convolution

cs.DS cs.CC ·2026-11-09 ·Shlomo A. Perles, Omri Weinstein
theorycode/data similarity 0.60
Abstract · 35 pages, 2 figures. Code, experiments, and Lean 4 formalizations: https://github.com/shlomi-perles/subspace-convolution

A cornerstone result in Boolean lattice theory is the subset-zeta transform, which computes the $f$-weighted subset summation problem $(Z f)(B)=\sum_{A\subseteq B}f(A)$ for all $ B\subseteq[n]$ in $O(N \log N)$ additions instead of the naïve $O(3^n) = O(N^{\log_2 3})$, where $N=2^n$. This paper studies the algebraic analogue of this problem--the subspace summation problem--where subsets are replaced by linear subspaces in $\mathbb{F}_q^n$. Surprisingly, we show that this problem admits a similar $Θ_q(N_q \log N_q)$-time algorithm, where $N_q$ is the number of subspaces. This improves substantially (in both theory and practice) over lattice-based algorithms ([BHK+16, KKW16]), which are known to be optimal for addition-only algorithms over $\mathbb R$. We prove similar runtimes for inversion, rank-constrained sums and span convolution. We describe two main applications: Fast linear algebra on Grassmann graphs: Matrix--vector multiplication for arbitrary distance-invariant kernels on $N$-vertex Grassmann graphs in $O_q(N\log N)$ arithmetic operations, together with fast spectral projections and exact solutions of the corresponding linear systems. Graph coloring of low binary cut-rank graphs: An $n^{2^{r^2/4+O(1)}}$-time algorithm for computing the chromatic number and chromatic polynomial of an $n$-vertex graph, given a rank-decomposition of width $r$. We also give quantitative reductions from satisfiability and monotone constraint problems. Experiments show speedups in measured running time of up to $18$ over the covering-pair algorithm for the zeta transform, $190$ over Poisson summation for rank-constrained sums, and $22$ over the distance-matrix recurrence for Grassmann kernel multiplication. Lean 4 formalizations of the transform identities, arithmetic operation bounds, and graph-coloring constructions accompany the paper [PW26].

0.28

Improved Exact and Approximate Quantum Fourier Transforms from Multiplication

cs.CC quant-ph ·2026-11-04 ·Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh
similarity 0.59
Abstract · 16 pages

In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorithms and phase estimation (which in itself has been used as a primitive in various quantum algorithms). In fact most of the well known quantum algorithms can be divided into two classes, QFT based algorithms and search based algorithms. The usual circuit for QFT (covered in almost every basic quantum algorithms course) needs $O(q^2)$ gates (and $O(q)$ qubits) to perform the exact Fourier transform over $\mathbb{F}_{2^q}$. Cleve and Watrous (FOCS 2000) improved this gate count to $O(q (\log q)^2 (\log \log q))$ using the integer multiplication algorithm in $O(n (\log n) (\log \log n))$ time for two $n$-bit integers (best known at that time). Our first main result shows that this gate count can be improved to $O(q (\log q))$. In fact, if there is a multiplication circuit, to multiply two $n$-bit integers, with $O(n (\log n)^α)$ gates; we get a QFT circuit with $O(q (\log q)^α)$ gates (improving upon $O(q (\log q)^{α+ 1})$) gates from the construction of Cleve and Watrous). Given the recent claim by OpenAI about integer multiplication, this opens up the possibility of having a QFT circuit with $o \left( q (\log q)\right)$ gates. On approximating the QFT over $\ZZ/(2^q \ZZ)$, the result of Ahokas, Cleve and Hales (ERATO 2003) showed that an approximating circuit can be built with $O \left( q (\log \log(q/\varepsilon))^{α+1} \right)$ gates, where $ε$ is the approximating parameter. Our second main result again improves this to $O \left( q (\log \log(q/\varepsilon))^α \right)$ gates.

0.25

The rank of 3x3 matrix multiplication over F2 is 23

cs.CC math.RA ·2026-10-08 ·Tejasvi Singh Tomar
theorycode/data similarity 0.56
Abstract · 18 pages. Kernel-only Lean proof: https://github.com/tejasvi/rank333-f2-kernel (archived at https://doi.org/10.5281/zenodo.23304899). Lean p…

The rank of the tensor of $3\times 3$ matrix multiplication over the field with two elements is at most $23$ by Laderman's algorithm, and Rudich and Rousseau recently proved that it is at least $22$. We prove that it equals $23$. Hence Laderman's algorithm uses the fewest multiplications among all bilinear algorithms over $\mathbb{F}_2$ and among all bilinear algorithms with integer coefficients. The proof uses the substitution method in the form developed by D'Ambrosio, Wang and Yang et al., which bounds the number of first factors of a decomposition that lie in a given subspace of the space of first factors. We sharpen these bounds for $111$ of Wang's $496$ classes of subspaces, constrain the ranks of the first factors through a $27\times 27$ flattening of the tensor, and list, up to symmetry, all sets of $22$ first factors that satisfy these constraints. An exact completion search shows that none of them is the set of first factors of a decomposition. The computation emits certificates, which are checked in the Lean 4 proof assistant. In one formal proof the largest checks are evaluated as compiled code, and in a second one the kernel evaluates every check, so that its final theorem depends only on the three standard axioms of Lean. The Lean proofs build on the formalization of Rudich and Rousseau and import their table of bounds and their reduction for block algorithms.

0.22

Fast matrix multiplication via recursive $\langle$ 4x4x4:48 $\rangle$ algorithms into practice

cs.SC ·2026-09-10 ·Jean-Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic, Joshua Stapleton, Petr Tichavský
similarity 0.55
Abstract

We present a fast algorithm for multiplying two 4x4 matrices using 48 multiplications and 204 other operations (addition, subtraction or scaling by a constant) over any ring containing an inverse of 2. Applied recursively, this algorithm reaches a cost bound with leading term (7+3/8)n^{\log_4(48)}. Alternative basis decompositions of this algorithm further reduce this to (6+13/32)n^{\log_4(48)}, with square change of bases, and then to (5+2/3)n^{\log_4(48)}, using rectangular encodings with inner dimensions 24 and 32. The conversion costs of these alternative basis variants are included as lower-order terms.

0.24

Block basis reduction for linear codes in non-Hamming metrics

cs.IT cs.DM ·2026-10-19 ·N. S. Kolesnikov, S. A. Novoselov
similarity 0.55
Abstract

In this paper, we generalize the code basis reduction to non-Hamming metrics. We propose a block basis reduction (BKZ) algorithm for codes that works for all coordinate-additive metrics. Our algorithm is a generalization of the algorithm of Ghentiyala and Stephens-Davidowitz, which in turn is an adaptation of the famous BKZ algorithm for lattices to linear codes and the Hamming metric. For block size~$2$ (LLL), we propose a polynomial-time algorithm with complexity~$\mathcal{O}(n^4 q^3)$ operations in~$\mathbb{F}_q$, where~$n$ is the length of the code and~$q$ is the alphabet size. For the Lee metric we provide an implementation of our algorithms and present experimental results on finding low Lee weight codewords.

0.27

A 51-Addition Alternative-Basis Kernel for Rank-23 $3\times3$ Matrix Multiplication

cs.DS cs.CCcs.SC ·2026-09-26 ·Joshua Stapleton, Andrew Perminov
code/data similarity 0.54
Abstract · 7 pages. Certificate and verification code: https://github.com/Joshua-Stapleton/51-addition-alt-basis-3x3-rank23

We give a rank-23 algorithm for $3\times3$ matrix multiplication using 51 additions and subtractions in alternative bases. The input and output conversions require five further additions, giving 56 additions in ordinary coordinates. The construction combines linear-program reduction with a search over sparse basis changes, and the resulting programs are distributed as a machine-checkable certificate. We verify correctness by exact coefficient expansion and distinguish the kernel cost from the cost of a complete multiplication.

0.47