We design nearly-linear time numerical algorithms for the problem of multivariate multipoint evaluation over the fields of rational, real and complex numbers. We consider both \emph{exact} and \emph{approximate} versions of the algorithm. The input to the algorithms are (1) coefficients of an $m$-variate polynomial $f$ with degree $d$ in each variable, and (2) points $a_1,..., a_N$ each of whose coordinate has value bounded by one and bit-complexity $s$. * Approximate version: Given additionally an accuracy parameter $t$, the algorithm computes rational numbers $\beta_1,\ldots, \beta_N$ such that $|f(a_i) - \beta_i| \leq \frac{1}{2^t}$ for all $i$, and has a running time of $((Nm + d^m)(s + t))^{1 + o(1)}$ for all $m$ and all sufficiently large $d$. * Exact version (when over rationals): Given additionally a bound $c$ on the bit-complexity of all evaluations, the algorithm computes the rational numbers $f(a_1), ... , f(a_N)$, in time $((Nm + d^m)(s + c))^{1 + o(1)}$ for all $m$ and all sufficiently large $d$. . Prior to this work, a nearly-linear time algorithm for multivariate multipoint evaluation (exact or approximate) over any infinite field appears to be known only for the case of univariate polynomials, and was discovered in a recent work of Moroz (FOCS 2021). In this work, we extend this result from the univariate to the multivariate setting. However, our algorithm is based on ideas that seem to be conceptually different from those of Moroz (FOCS 2021) and crucially relies on a recent algorithm of Bhargava, Ghosh, Guo, Kumar & Umans (FOCS 2022) for multivariate multipoint evaluation over finite fields, and known efficient algorithms for the problems of rational number reconstruction and fast Chinese remaindering in computational number theory.
翻译:我们设计了几乎线性时间的数值算法,用于求解有理、实数和复数域上的多元多点求值问题。我们考虑了算法的“精确”和“近似”两个版本。输入算法的是一个 $m$ 变量,每个变量的次数为 $d$ 的多项式 $f$ 的系数,以及 $a_1,...,a_N$ 使得它们每个坐标的值都在 $[-1, 1]$ 区间内,且位数复杂度为 $s$ 的点。
* 近似版本:额外给定一个精度参数 $t$,算法计算有理数 $\beta_1,\ldots, \beta_N$,使得对于所有的 $i$,$|f(a_i) - \beta_i| \leq \frac{1}{2^t}$,并且运行时间对于所有充分大的 $d$ 和所有 $m$ 为 $((Nm + d^m)(s + t))^{1 + o(1)}$。
* 精确版本(当在有理数域上时):额外给定一个界限 $c$,限制了所有求值的位数复杂度,算法计算出有理数 $f(a_1), ... , f(a_N)$,并且运行时间对于所有充分大的 $d$ 和所有 $m$ 为 $((Nm + d^m)(s + c))^{1 + o(1)}$。 在此之前,针对任意无限域的多元多点求值问题,只有单变量多点情况的几乎线性时间算法已经被发现并在 Moroz (FOCS 2021) 中提出。在本文中,我们将该结果从单变量推广到多元情况。但是,我们的算法基于的思路似乎与 Moroz (FOCS 2021) 中的思路有所不同,并且关键地依赖于 Bhargava, Ghosh, Guo, Kumar & Umans (FOCS 2022) 在有限域上进行多元多点求值的一种最近算法,以及计算数论中的快速有理数重构和中国剩余定理的已知高效算法。