Aug 2026· arXiv.org· Vol abs/2608.20855· 0 citations· 26 references
Computer Science
TL;DR
This work develops additive FFT techniques for polynomial evaluation over affine subspaces of binary extension fields and formalizes the notion of partial Cantor special bases and identifies parameter regimes in which both the von zur Gathen-Gerhard algorithm and the general-basis AFFT require fewer additions and multiplications than the first Gao-Mateer algorithm.
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.
This paper studies formal Laurent series, with particular emphasis on their continued-fraction and Laurent-series expansions. Knowledge of both expansions is important, for example, in the study of Kronecker-type sequences in uniform distribution theory and in the search for potential counterexamples to variants of Lit...
We study monic irreducible polynomials over $\mathbb{F}_q[T]$ whose non-leading digits, with respect to an arbitrary polynomial base $b(T)$, avoid a prescribed set of forbidden digits. Identifying the digit set with the ring $D=\mathbb{F}_q[T]/(b)$, we obtain an asymptotic formula for the number of such irreducible pol...
This paper investigates arithmetic conditions, over finite fields, for the invertibility of circulant matrices whose first row is $(a_0,\ldots,a_{n-1})$, in terms of linear constraints on the entries $a_0,\ldots,a_{n-1}$. The coefficients of such linear constraints are determined by field traces arising from Frobenius...
We present a new asymptotic matrix multiplication construction yielding $\omega<2.37115924$, and therefore an algorithm that multiplies two $n\times n$ matrices in $O(n^{2.37115924})$ arithmetic operations over the rationals, reals, or complex numbers. The construction improves the bound $2.371177$ of Dupont et al. wit...
We investigate an algebraic approach to the Syndrome Decoding Problem, based on a reformulation of the Hamming weight constraint and its integration with the Information Set Decoding paradigm. We begin with a systematic analysis of the Hamming variety, deriving its defining equations in terms of elementary symmetric fu...
R. La Scala, Marco Marchesin, S. Tiwari· arXiv.org· 0 citations
We develop Toeplitz infinite GMRES for solving large sparse analytic parameterized systems $A(s)x(s)=z$ at many parameter values. Our method exploits a block upper triangular Toeplitz structure in the companion Krylov sequence to construct the Arnoldi process and recover solution approximations without storing full Arn...
W. Gao, Fei Jiang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.