Fast linear homotopy to find approximate zeros of polynomial systems (Q626447)

The authors consider the problem of finding an approximate zero of systems of polynomial equations and present a new algorithm which is based on the idea of homotopy methods. They prove the main theorem which states that the average running time of the algorithm is \(O(d^{3/2}nN(N+n^3))\), where \(N\) is the input size, \(n+1\) is the number of unknowns and \(d\) is the maximum of the degrees. Moreover, the average number of homotopy steps is at most \(Cd^{3/2}nN\), where \(C\leq 71\pi/\sqrt{2}\) is a constant. The authors show that the method can be applied to approximate several or all solutions of non-degenerate systems. The paper is very well written.