Fast Linear Homotopy to Find Approximate Zeros of Polynomial Systems
Fast Linear Homotopy to Find Approximate Zeros of Polynomial Systems
复制标题
快速线性同伦求多项式系统的近似零点
DOI：
10.1007/s10208-010-9078-9
复制
发表时间：
2011
影响因子：
3
通讯作者：
L. M. Pardo
中科院分区：
文献类型：
--
作者：
C. Beltrán;L. M. Pardo
我们证明了一个新的复杂性，即平均值，对于多项式方程的系统近似零，该方法的平均数量几乎是线性的（密集编码）。我们证明该方法还可以用于近似非脱位系统的几个或所有解决方案，并证明可以在系统数字中的bézout数字和多项式中的bézout数字中执行最后一个任务输入的大小，平均。
We prove a new complexity bound, polynomial on the average, for the problem of finding an approximate zero of systems of polynomial equations. The average number of Newton steps required by this method is almost linear in the size of the input (dense encoding). We show that the method can also be used to approximate several or all the solutions of non-degenerate systems, and prove that this last task can be done in running time which is linear in the Bézout number of the system and polynomial in the size of the input, on the average.