Numeric vs. Symbolic homotopy algorithms in polynomial system solving: A case study

MARIANO DE LEO; EZEQUIEL DRATMAN; GUILLERMO MATERA

JOURNAL OF COMPLEXITY

ACADEMIC PRESS INC ELSEVIER SCIENCE

Lugar: Amsterdam; Año: 2005 vol. 21 p. 502 - 531

0885-064X

We consider a family of polynomial systems which arises in the analysis of the stationary solutions of a standard discretization of certain semilinear second order parabolic partial differential equations.We prove that this family is well?conditioned from the numeric point of view, and ill?conditioned from the symbolic point of view. We exhibit a polynomial?time numeric algorithm solving any member of this family, which significantly contrasts the exponential behaviour of all known symbolic algorithms solving a generic instance of this family of systems.