Greatest common divisors of polynomials given by straight-line programs
Greatest common divisors of polynomials given by straight-line programs
复制标题
直线规划给出的多项式的最大公约数
DOI：
--
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
E. Kaltofen
中科院分区：
文献类型：
--
作者：
E. Kaltofen
开发了由直线程序表示的多元多项式的算法。首先，它表明大多数代数算法可以概率地应用于由直线计算给出的数据。例如，通过对随机素数取模进行随机评估可以方便地测试此类有理数值数据是否为零。然后，构建确定单变量中多元多项式系数的辅助算法。第一个主要结果是一种生成输入多项式最大公约数的算法，全部以直线表示。第二个结果显示如何从相应的有理函数中找到简化的分子和分母的直线程序。该构造的算法和最大公约数算法都在通常系数域的随机多项式时间内，并输出直线程序，该程序以可控的高概率正确地确定所请求的答案。运行时间是二进制输入大小、输入度为一元数以及故障概率倒数的对数的多项式函数。有理函数分子和分母的直线规划算法意味着每个有度有界有理函数都可以快速并行计算，即以多项式大小和多对数深度计算。
Algorithms on multivariate polynomials represented by straight-line programs are developed. First, it is shown that most algebraic algorithms can be probabilistically applied to data that are given by a straight-line computation. Testing such rational numeric data for zero, for instance, is facilitated by random evaluations modulo random prime numbers. Then, auxiliary algorithms that determine the coefficients of a multivariate polynomial in a single variable are constructed. The first main result is an algorithm that produces the greatest common divisor of the input polynomials, all in straight-line representation. The second result shows how to find a straight-line program for the reduced numerator and denominator from one for the corresponding rational function. Both the algorithm for that construction and the greatest common divisor algorithm are in random polynomial time for the usual coefficient fields and output a straight-line program, which with controllably high probability correctly determines the requested answer. The running times are polynomial functions in the binary input size, the input degrees as unary numbers, and the logarithm of the inverse of the failure probability. The algorithm for straight-line programs for the numerators and denominators of rational functions implies that every degree-bounded rational function can be computed fast in parallel, that is, in polynomial size and polylogarithmic depth.