A continuation method to solve polynomial systems and its complexity
A continuation method to solve polynomial systems and its complexity
复制标题
求解多项式系统及其复杂度的连续方法
作者：
C. Beltrán
在最近的工作Shub（发现。9：171-178，2009），Shub获得了将系统f0的已知零η0延续到输入系统fT的零ηT所需的步数的新上界，遵循对（ft，ηt）的路径，其中$${f_t，tin[0，T]}$$是多项式系统并且ft（ηt）= 0。他证明，如果一个可以选择的步长在一个最佳的方式，那么步骤的数量基本上是有界的路径的长度（英尺，ηt）在所谓的条件度量。然而，Shub（Found. Comput. 171-178，2009）不是建设性的。我们给出了一个明确的描述，达到复杂性的界限，包括步长的选择的算法。
In a recent work Shub (Found. Comput. Math. 9:171–178, 2009), Shub obtained a new upper bound for the number of steps needed to continue a known zero η0 of a system f0, to a zero ηT of an input system fT, following the path of pairs (ft, ηt), where $${f_t,tin[0,T]}$$ is a polynomial system and ft(ηt) = 0. He proved that if one can choose the step-size in an optimal way, then the number of steps is essentially bounded by the length of the path of (ft, ηt) in the so-called condition metric. However, the proof of that result in Shub (Found. Comput. Math. 9:171–178, 2009) is not constructive. We give an explicit description of an algorithm which attains that complexity bound, including the choice of step-size.