Amortized multi-point evaluation of multivariate polynomials
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.
- Accelerated tower arithmetic
- Algorithme de Brill-Noether et codes de Goppa
- Algorithms – ESA 2004
- Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
- Fast amortized multi-point evaluation
- Fast modular transforms
- Fast multiplication of large numbers
- Fast multiplication of polynomials over fields of characteristic 2
- Fast multivariate multi-point evaluation revisited
- Fast polynomial factorization and modular composition
- Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
- Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation
- scientific article; zbMATH DE number 3935185 (Why is no real title available?)
- scientific article; zbMATH DE number 3539809 (Why is no real title available?)
- scientific article; zbMATH DE number 2151179 (Why is no real title available?)
- Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
- On fast multiplication of polynomials over arbitrary algebras
- On the bit-complexity of sparse polynomial and series multiplication
- On the complexity exponent of polynomial system solving
- On the complexity of multivariate polynomial division
- Polynomial multiplication over finite fields in time O(n n)
- Relax, but don't be too lazy
- What can (and can't) we do with sparse polynomials?
- Fast amortized multi-point evaluation
- Fast multivariate multi-point evaluation revisited
- Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation
- Algorithms – ESA 2004
- Efficient evaluation of large polynomials
- Sparse tensors and subdivision methods for finding the zero set of polynomial equations
- Fast multivariate multipoint evaluation over all finite fields
- Fast, algebraic multivariate multipoint evaluation in small characteristic and applications
This page was built for publication: Amortized multi-point evaluation of multivariate polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2099269)
