Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-033 | 24th March 2023 17:53

Fast Numerical Multivariate Multipoint Evaluation

RSS-Feed




Revision #1
Authors: Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, Ramprasad Saptharishi
Accepted on: 24th March 2023 17:53
Downloads: 238
Keywords: 


Abstract:

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 $\mathbf{a}_1,\ldots, \mathbf{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(\mathbf{a}_i) - \beta_i} \leq \sfrac{1}{2^t}$ for all $i$, and has a running time of $\left((Nm + d^m)(s + t)\right)^{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(\mathbf{a}_1), \ldots, f(\mathbf{a}_N)$, in time $\left((Nm + d^m)(s + c)\right)^{1 + o(1)}$ for all $m$ and all sufficiently large $d$.

Our results also naturally extend to the case when the input is over the field of real or complex numbers under an appropriate standard model of representation of field elements in such fields.

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 [Proc. 62nd 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 and crucially relies on a recent algorithm of Bhargava, Ghosh, Guo, Kumar & Umans [Proc. 63rd 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.



Changes to previous version:

Fixing some references, and a few cosmetic changes


Paper:

TR23-033 | 24th March 2023 17:05

Fast Numerical Multivariate Multipoint Evaluation





TR23-033
Authors: Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, Ramprasad Saptharishi
Publication: 24th March 2023 17:06
Downloads: 172
Keywords: 


Abstract:

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 $\mathbf{a}_1,\ldots, \mathbf{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(\mathbf{a}_i) - \beta_i} \leq \sfrac{1}{2^t}$ for all $i$, and has a running time of $\left((Nm + d^m)(s + t)\right)^{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(\mathbf{a}_1), \ldots, f(\mathbf{a}_N)$, in time $\left((Nm + d^m)(s + c)\right)^{1 + o(1)}$ for all $m$ and all sufficiently large $d$.

Our results also naturally extend to the case when the input is over the field of real or complex numbers under an appropriate standard model of representation of field elements in such fields.

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 [Proc. 62nd 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 and crucially relies on a recent algorithm of Bhargava, Ghosh, Guo, Kumar & Umans [Proc. 63rd 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.



ISSN 1433-8092 | Imprint