On the complexity of solving generalized Pham systems

EZEQUIEL DRATMAN; GUILLERMO MATERA; ARIEL WAISSBEIN

COMPUTATIONAL COMPLEXITY

BIRKHAUSER VERLAG AG

Lugar: BASEL; Año: 2009 vol. 18 p. 105 - 154

1016-3328

We discuss the complexity of robust symbolic algorithms solving a significant class of zero--dimensional square polynomial systems, called generalized Pham systems, which represent the class of zero--dimensional homogeneous complete--intersection systems with "no points at infinity´´. Our notion of robustness models the behavior of all known universal methods for solving (parametric) polynomial systems avoiding unnecessary branchings and allowing the solution of certain limit problems. We first show that any robust algorithm solving generalized Pham systems has necessarily polynomial complexity in the Bézout number of the system under consideration. Then we exhibit a robust probabilistic algorithm which solves generalized Pham systems with quadratic complexity in the Bézout number of the input system. The algorithm consists in a series of homotopies deforming the input system into a system which is "easy to solve´´, together with a "projection algorithm´´ which allows to move the solutions of the known instance to the solutions of an arbitrary instance along the parameter space.