Robust Algorithms For Generalized Pham Systems

We discuss the complexity of robust symbolic algorithms solving a significant class of zero–dimensional square polynomial systems with rational coefficients over the complex numbers, 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 complexity at least polynomial 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.

Authors and Affiliations

1. Instituto de Ciencias, Universidad Nacional Gral. Sarmiento, J.M. Gutiérrez 1150, 1613, Los Polvorines, Argentina

   Ezequiel Dratman

2. Instituto del Desarrollo Humano, Universidad Nacional Gral. Sarmiento, J.M. Gutiérrez 1150, 1613, Los Polvorines, Argentina

   Guillermo Matera

3. CONICET, Buenos Aires, Argentina

   Guillermo Matera

4. CoreLabs, CORE Security Technologies, Humboldt 1967, C1414CTU, Buenos Aires, Argentina

   Ariel Waissbein

5. Doctorado en Ingeniería, Instituto Tecnológico de Buenos Aires, Av. Eduardo Madero 399, C1106ACD, Buenos Aires, Argentina

   Ariel Waissbein

Corresponding author

Correspondence to Ezequiel Dratman.

Manuscript received 22 May 2007

Reprints and permissions