Title
Deformation Techniques for Sparse Systems
Authors
Gabriela Jerónimo, Guillermo Matera, Pablo Solerno and Ariel Waissbein
In
Foundations of Computational Mathematics, Volume 9 , Issue 1 (January 2009).
Pages
1-50
Date published
2009-01
ISSN :1615-3375

: Keywords

sparse systems, mixed volume, homotopic continuation, elimination

Abstract

We exhibit a probabilistic symbolic algorithm for solving zero-dimensional sparse systems. Our algorithm combines a symbolic homotopy procedure, based on a flat deformation of a certain morphism of affine varieties, with the polyhedral deformation of Huber and Sturmfels. The complexity of our algorithm is cubic in the size of the combinatorial structure of the input system. This size is mainly represented by the cardinality and mixed volume of Newton polytopes of the input polynomials and an arithmetic analogue of the mixed volume associated to the deformations under consideration.

Attachments