A continuation method to solve polynomial systems and its complexity (Q621308)

Continuation methods for solving systems of polynomial equations approximate solutions to a given system by continuing one or more known solutions of simpler systems. \textit{M. Shub} [Found. Comput. Math. 9, No.~2, 171--178 (2009; Zbl 1175.65060)] obtained a new upper bound for the number of steps needed to continue a known zero \(\eta_{0}\) of a system \(f_{0}\) to a zero \(\eta_{T}\) of an input system \(f_{T}\), following the path of pairs \((f_{t}, \eta_{t})\), where \(f_t\), \(t\in[0,T]\) is a polynomial system and \(f_{t}(\eta_{t}) = 0\). It is 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 \((f_{t}, \eta_{t})\) in the so-called condition metric. The aim of this paper is to introduce an algorithm which satisfies the complexity bounds proved by Shub.