New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems
New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems
复制标题
单变量多项式近似的新数据结构及其在根隔离、数值多点评估和其他问题中的应用
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
G. Moroz
中科院分区：
文献类型：
--
作者：
G. Moroz
我们提出了一个新的数据结构，以准确有效地近似于$ d $的多项式$ f $ d $，作为其属性的列表。根部隔离和近似多点评估的问题也导致了一个新的几何标准，以检测不良条件的多项式，这特别暗示了多项式的零的标准条件数在模量的数量小于1/2或大于2的根数中。给定一个多项式$ f $ d $ $ d $║f║1=σ|复杂的根或评估$ D $点可以通过准线性数量的算术操作来完成。 - 条件多项式和所需的准确性较低。 d（τ + m））位操作，其中（。）表示我们省略对数因素。 in（d（τ + log） κ）位操作。具有随机兼容性的高度多项式的mpsolve。
We present a new data structure to approximate accurately and efficiently a polynomial $f$ of degree $d$ given as a list of coefficients fi. Its properties allow us to improve the state-of-the-art bounds on the bit complexity for the problems of root isolation and approximate multi-point evaluation. This data structure also leads to a new geometric criterion to detect ill-conditioned polynomials, implying notably that the standard condition number of the zeros of a polynomial is at least exponential in the number of roots of modulus less than 1/2 or greater than 2. Given a polynomial $f$ of degree $d$ with ║f║1 = Σ | fi| ≤ 2τ for τ ≥ 1, isolating all its complex roots or evaluating it at $d$ points can be done with a quasi-linear number of arithmetic operations. However, considering the bit complexity, the state-of-the-art algorithms require at least d3/2 bit operations even for well-conditioned polynomials and when the accuracy required is low. Given a positive integer $m$, we can compute our new data structure and evaluate $f$ at $d$ points in the unit disk with an absolute error less than 2−m in Õ(d(τ + m)) bit operations, where Õ(.) means that we omit logarithmic factors. We also show that if κ is the absolute condition number of the zeros of f, then we can isolate all the roots of $f$ in Õ(d(τ + log κ)) bit operations. Moreover, our algorithms are simple to implement. For approximating the complex roots of a polynomial, we implemented a small prototype in Python/NumPy that is an order of magnitude faster than the state-of-the-art solver MPSolve for high degree polynomials with random coefficients.
登录
查看更多内容
DOI：
10.1007/978-3-642-38896-5
发表时间：
2013-08
期刊：
--
影响因子：
--
作者：
Peter Bürgisser;F. Cucker
通讯作者：
Peter Bürgisser;F. Cucker
DOI：
10.1007/978-3-319-96418-8_28
发表时间：
2018
期刊：
International Congress on Mathematical Software (ICMS
影响因子：
--
作者：
Imbach, Rémi;Pan, Victor;Yap, Chee
通讯作者：
Yap, Chee
一种在多项式平均时间内计算多项式系统近似根的确定性算法
影响因子：
3
作者：
P. Lairez
通讯作者：
P. Lairez
DOI：
10.1090/mcom/2985
发表时间：
2015
期刊：
Math. Comput.
影响因子：
--
作者：
Todor Bilarev;Magnus Aspenberg;Dierk Schleicher
通讯作者：
Dierk Schleicher
DOI：
10.1145/3373207.3404063
发表时间：
2020
期刊：
International Symposium on Symbolic and Algebraic Computation
影响因子：
--
作者：
Imbach, Rémi;Pan, Victor Y.
通讯作者：
Pan, Victor Y.