A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time
A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time
复制标题
一种在多项式平均时间内计算多项式系统近似根的确定性算法
DOI：
10.1007/s10208-016-9319-7
复制
发表时间：
2017
影响因子：
3
通讯作者：
P. Lairez
中科院分区：
文献类型：
--
作者：
P. Lairez
我们描述了一个确定性算法，计算一个近似的根ofn复杂的多项式方程innknowns在平均多项式时间相对于输入的大小，在Blum-Shub-Smale模型与平方根。它依赖于Beltrán和Pardo算法的去随机化，并对Smale的第17个问题给出了确定性的肯定回答。其主要思想是利用输入本身所包含的随机性。
We describe a deterministic algorithm that computes an approximate root ofncomplex polynomial equations innunknowns in average polynomial time with respect to the size of the input, in the Blum–Shub–Smale model with square root. It rests upon a derandomization of an algorithm of Beltrán and Pardo and gives a deterministic affirmative answer to Smale’s 17th problem. The main idea is to make use of the randomness contained in the input itself.
登录
查看更多内容
DOI：
10.1007/978-3-642-38896-5
发表时间：
2013-08
期刊：
--
影响因子：
--
作者：
Peter Bürgisser;F. Cucker
通讯作者：
Peter Bürgisser;F. Cucker
快速线性同伦求多项式系统的近似零点
影响因子：
3
作者：
C. Beltrán;L. M. Pardo
通讯作者：
L. M. Pardo
求解多项式系统及其复杂度的连续方法
影响因子：
2.1
作者：
C. Beltrán
通讯作者：
C. Beltrán
关于贝佐特定理和复杂性理论的一些评论
影响因子：
3
作者：
M. Shub
通讯作者：
M. Shub
特征对问题的稳定多项式时间算法
DOI：
10.4171/jems/789
发表时间：
2018
期刊：
arXiv: Numerical Analysis
影响因子：
--
作者：
D. Armentano;C. Beltrán;P. Bürgisser;F. Cucker;M. Shub
通讯作者：
M. Shub