Amortized multi-point evaluation of multivariate polynomials
type: Item
instance of: scholarly article
title: Amortized multi-point evaluation of multivariate polynomials
author: Joris van der Hoeven
author: Grégoire Lecerf
published in: Journal of Complexity
publication date: 2022-11-23T00:00:00Z
review text: This paper develops an algorithm to evaluate a polynomial \(P\) with an arbitrary number of variables at an arbitrary set of points (encoded in a tuple denoted by \(\alpha\)). The key step to the evaluation algorithm is a newly introduced \textit{quasi-reduction} of \(P\), which in principle reduces some fixed set of monomials with respect to a finite set \((B_i)_{i\in I}\). The \(B_i\) are chosen from the vanishing ideal \(\mathcal{I}_{\alpha}:=\left\lbrace A : A(\alpha)=0 \right\rbrace\) of \(\alpha\) so that \(P(\alpha)=R(\alpha)\) in \(P=Q_1B_1+\cdots + Q_{\ell} B_{\ell} + R\) for some computed \(Q_1,\ldots,Q_{\ell},R\) in the corresponding polynomial ring. The \(B_i\) can be pre-computed by solving a linear system \(B_i(\alpha)=0\). The algorithm is then applied recursively on the quasi-reduced polynomial on each half of \(\alpha\). The final result is derived by concatenating the results of all recursive evaluations. The difficulties inherent in the above procedure stem from general difficulties working with a full (possibly irregularly shaped) Gröbner basis of \(\mathcal{I}_{\alpha}\). This issue is addressed in the paper by working simultaneously with several orderings on the monomials, in which different orderings are assigned admissible weights. The resulting combination of these orderings is termed \textit{heterogenous}. The weights can be selected to optimize the efficiency of the algorithm depending on the degree of the polynomial we wish to reduce. Thus, the polynomials that qualify as input for an ``efficient'' quasi-reduction is bounded in its degree. Under these conditions, the \(B_i\) are then chosen according to the admissible weights in the heterogenous ordering. The authors also deduce a bound for the size of the reduced polynomials, address lower dimenional ``border'' monomials, and give complexity analysis for the quasi-reduction algorithm.
reviewed by: Elaine Wong
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 13P10
zbMATH DE Number: 7622340
zbMATH Keywords: multi-point evaluation
zbMATH Keywords: multivariate polynomial
zbMATH Keywords: Gröbner bases
zbMATH Keywords: complexity
MaRDI profile type: Publication
full work available at URL: j.jco.2022.101693
OpenAlex ID: W4225642243
cites work: Fast modular transforms
cites work: Q4660643
cites work: On fast multiplication of polynomials over arbitrary algebras
cites work: Q4115605
cites work: Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
cites work: Polynomial Multiplication over Finite Fields in Time \( O(n \log n \)
cites work: Relax, but don't be too lazy
cites work: On the Complexity of Multivariate Polynomial Division
cites work: On the bit-complexity of sparse polynomial and series multiplication
cites work: Accelerated tower arithmetic
cites work: Fast multivariate multi-point evaluation revisited
cites work: Fast amortized multi-point evaluation
cites work: On the complexity exponent of polynomial system solving
cites work: Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
cites work: Fast Polynomial Factorization and Modular Composition
cites work: Algorithme de Brill-Noether et codes de Goppa
cites work: Q4607951
cites work: Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation
cites work: Algorithms – ESA 2004
cites work: Q3708893
cites work: What Can (and Can't) we Do with Sparse Polynomials?
cites work: Fast multiplication of polynomials over fields of characteristic 2
cites work: Fast multiplication of large numbers
DOI: 10.1016/J.JCO.2022.101693
description: scientific article; zbMATH DE number 7622340