Abstract: 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.

Authorship

Download reference