Search Results for « Multivariate multipoint evaluation »

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field \(\mathbb {F}\) that outputs the evaluations of an m -variate polynomial of degree less than d in each variable at N points in time, \(\begin{equation*} (d^m+N)^{1+o(1)}\cdot {{\sf poly}}(m,d,\log |\mathbb {F}|), \end{equation*}\) for all \(m\in \mathbb {N}\) and all sufficiently large \(d\in \mathbb {N}\) . A previous work of Kedlaya and Umans (FOCS 2008 and SICOMP 2011) achieved the same time complexity when the number of variables m is at most \(d^{o(1)}\) and had left the problem of removing this condition as an open problem. A recent work of Bhargava, Ghosh, Kumar, and Mohapatra (STOC 2022) answered this question when the underlying field is not too large and has characteristic less than \(d^{o(1)}\) . In this work, we remove this constraint on the number of variables over all finite fields, thereby answering the question of Kedlaya and Umans over all finite fields. Our algorithm relies on a non-trivial combination of ideas from three seemingly different previously known algorithms for multivariate multipoint evaluation, namely the algorithms of Kedlaya and Umans, that of Björklund, Kaski, and Williams (IPEC 2017 and Algorithmica 2019), and that of Bhargava, Ghosh, Kumar, and Mohapatra, together with a result of Bombieri and Vinogradov from analytic number theory about the distribution of primes in an arithmetic progression. We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and, in particular, avoids the use of the Bombieri–Vinogradov theorem. However, it requires a mild assumption that the field size is bounded by an exponential tower in d of bounded height . More specifically, our second algorithm solves the multivariate multipoint evaluation problem over a finite field \(\mathbb {F}\) in time, \(\begin{equation*} (d^m+N)^{1+o(1)}\cdot {{\sf poly}}(m,d,\log |\mathbb {F}|), \end{equation*}\) for all \(m\in \mathbb {N}\) and all sufficiently large \(d\in \mathbb {N}\) , provided that the size of the finite field \(\mathbb {F}\) is at most \((\exp (\exp (\exp (\cdots (\exp (d)))))\) , where the height of this tower of exponentials is fixed.

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem are also closely related to fast algorithms for other natural algebraic questions such as polynomial factorization and modular composition. And while nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck [ 7 ], fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state-of-the-art for this problem, Umans [ 25 ] and Kedlaya & Umans [ 16 ] gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields, respectively, provided that the number of variables n is at most \(d^{o(1)}\) where the degree of the input polynomial in every variable is less than d . They also stated the question of designing fast algorithms for the large variable case (i.e., \(n \notin d^{o(1)}\) ) as an open problem. In this work, we show that there is a deterministic algorithm for multivariate multipoint evaluation over a field \(\mathbb {F}_{q}\) of characteristic p , which evaluates an n -variate polynomial of degree less than d in each variable on N inputs in time \(\begin{equation*} \left((N + d^n)^{1 + o(1)}\text{poly}(\log q, d, n, p)\right), \end{equation*}\) provided that p is at most d o (1) , and q is at most (exp (exp (exp (...(exp ( d ))))), where the height of this tower of exponentials is fixed. When the number of variables is large (e.g., n ∉ d o (1) ), this is the first nearly linear time algorithm for this problem over any (large enough) field. Our algorithm is based on elementary algebraic ideas, and this algebraic structure naturally leads to the following two independently interesting applications: — We show that there is an algebraic data structure for univariate polynomial evaluation with nearly linear space complexity and sublinear time complexity over finite fields of small characteristic and quasipolynomially bounded size. This provides a counterexample to a conjecture of Miltersen [ 21 ] who conjectured that over small finite fields, any algebraic data structure for polynomial evaluation using polynomial space must have linear query complexity. — We also show that over finite fields of small characteristic and quasipolynomially bounded size, Vandermonde matrices are not rigid enough to yield size-depth tradeoffs for linear circuits via the current quantitative bounds in Valiant’s program [ 26 ]. More precisely, for every fixed prime p , we show that for every constant ɛ > 0, and large enough n , the rank of any \(n \times n\) Vandermonde matrix V over the field \(\mathbb {F}_{p^a}\) can be reduced to ( n /exp (Ω (poly(ɛ)log 0.53 n ))) by changing at most n Θ (ɛ) entries in every row of V , provided a ≤ poly(log n ). Prior to this work, similar upper bounds on rigidity were known only for special Vandermonde matrices. For instance, the Discrete Fourier Transform matrices and Vandermonde matrices with generators in a geometric progression [ 9 ].

Let a1, . . . , am be distinct elements of a field and let Z(X) = Πi(X − ai). We study the total arithmetic complexity of the canonical Bézout pair sZ + tZ′ = 1, deg t < m, deg s < m − 1. The standard product-tree route uses O(MF(m) logm) field operations. Even when MF(m) = O(m logm), this is O(m log2 m) rather than O(m logm). Our main result identifies the missing logarithm. Over an infinite field of characteristic zero, in the generic rational straight-line-program model, computing all coefficients of (s, t) is equivalent, up to O(MF(m)) operations, to arbitrary-node multipoint evaluation and to interpolation. The new direction rests on an explicit quasi-linear reconstruction of Z from (s, t) on a nonempty Zariski-open set. It also transfers Strassen’s Ω(m logm) nonscalar lower bound for elementary symmetric functions to the Bézout problem, showing that the requested order would be optimal. The reconstruction is genuinely characteristic-dependent: in characteristic p, the squarefree polynomials Xp + cX + d all have the same canonical pair (0, c−1) for fixed c ̸= 0. Thus the all-field, all-input O(m logm) question is not resolved here; it is reduced generically in characteristic zero to the corresponding arbitrary-node evaluation problem.