Fast, algebraic multivariate multipoint evaluation in small characteristic and applications
Fast, algebraic multivariate multipoint evaluation in small characteristic and applications
复制标题
DOI：
10.1145/3519935.3519968
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Vishwas Bhargava;Sumanta K Ghosh;Mrinal Kumar;C. K. Mohapatra
中科院分区：
文献类型：
--
作者：
Vishwas Bhargava;Sumanta K Ghosh;Mrinal Kumar;C. K. Mohapatra
多点求值是一种计算任务，对给定输入集上的系数列表给出的多项式求值。该问题的快速算法除了本身是计算机代数中一个自然而基本的问题外，还与多项式分解、模合成等其他自然代数问题的快速算法密切相关。由于Borodin和Moenck的工作，近五十年来，几乎线性的时间算法已经为多点评估的单变量实例而闻名，而多变量版本的快速算法却很难实现。极大地提高国家的艺术问题,乌曼和Kedlaya &乌曼给了近线性时间算法这一问题领域的小特点和在有限的所有字段分别提供变量n是最多的数量做(1)输入每一个变量的多项式的程度小于d。他们还说的问题设计快速算法对于大变量(即n∉(1))作为一个开放的问题。在这项工作中，我们证明了存在一种确定性算法，用于特征p的域Fq上的多元多点评估，该算法在时间（N + dn）1 + o(1)（logq, d， N, p）上的N个输入的每个变量中评估一个小于d度的N变量多项式，前提是p最多为do(1)，并且q最多为exp(⋯exp(d)))))，其中该指数塔的高度是固定的。当变量数目较大时（如n∈do(1)），这是第一个在任何（足够大的）域上处理此问题的近似线性时间算法。我们的算法基于初等代数思想，这种代数结构自然会导致以下两个独立有趣的应用。我们证明了在小特征和拟多项式有界大小的有限域上存在一种具有近线性空间复杂度和次线性时间复杂度的单变量多项式计算的代数数据结构。这为Milterson猜想提供了一个反例，Milterson猜想在小的有限域上，使用多项式空间进行多项式求值的任何代数数据结构都必须具有线性查询复杂性。我们还表明，在小特征和准多项式有界大小的有限域上，Vandermonde矩阵不够刚性，无法通过Valiant程序中的当前定量界限为线性电路提供尺寸深度权衡。更准确地说，对于每一个固定素数p，我们证明了对于每一个常数n > 0，并且n足够大，任何n × n范德蒙德矩阵V在域pa上的秩可以简化为(n/exp（Ω（(n)√logn）），只要在V的每一行中最多改变nΘ(n)个元素，假设a≤(logn)。在此工作之前，类似的刚性上界仅为特殊的Vandermonde矩阵所知。例如，离散傅里叶变换矩阵和Vandermonde矩阵的几何级数生成器。
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 like 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, fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state of art for this problem, Umans and Kedlaya & Umans 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 do(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 ∉ do(1)) as an open problem. In this work, we show that there is a deterministic algorithm for multivariate multipoint evaluation over a field Fq of characteristic p which evaluates an n-variate polynomial of degree less than d in each variable on N inputs in time (N + dn)1 + o(1)(logq, d, n, p) provided that p is at most do(1), and q is at most (exp(⋯ (exp(d)))), where the height of this tower of exponentials is fixed. When the number of variables is large (e.g. n ∉ do(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 Milterson 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. More precisely, for every fixed prime p, we show that for every constant є > 0, and large enough n, the rank of any n × n Vandermonde matrix V over the field pa can be reduced to (n/exp(Ω((є)√logn))) by changing at most nΘ(є) entries in every row of V, provided a ≤ (logn). 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.