Amortized multi-point evaluation of multivariate polynomials (Q2099269)

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.