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) 在有限域上进行多元多点求值的一种最近算法,以及计算数论中的快速有理数重构和中国剩余定理的已知高效算法。

0
下载
关闭预览

相关内容

IEEE计算机科学基础研讨会(FOCS)是由IEEE计算机学会计算数学基础技术委员会(TCMF)主办的旗舰会议,涵盖了广泛的理论计算机科学。它每年秋季举行,并与每年春季举行的由ACM SIGACT赞助的姊妹会议——计算理论年度研讨会(STOC)配对。官网链接:http://ieee-focs.org/
【2023新书】使用Python进行统计和数据可视化,554页pdf
专知会员服务
126+阅读 · 2023年1月29日
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
72+阅读 · 2022年6月28日
专知会员服务
159+阅读 · 2020年1月16日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
AI/ML/DNN硬件加速设计怎么入门?
StarryHeavensAbove
10+阅读 · 2018年12月4日
数据分析师应该知道的16种回归技术:弹性网络回归
数萃大数据
91+阅读 · 2018年8月16日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
国家自然科学基金
1+阅读 · 2016年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月25日
Arxiv
0+阅读 · 2023年5月24日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
AI/ML/DNN硬件加速设计怎么入门?
StarryHeavensAbove
10+阅读 · 2018年12月4日
数据分析师应该知道的16种回归技术:弹性网络回归
数萃大数据
91+阅读 · 2018年8月16日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
相关基金
国家自然科学基金
1+阅读 · 2016年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员