Deformation techniques for sparse systems

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 algori...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Jeronimo, G., Matera, G., Solernó, P., Waissbein, A.
Formato: JOUR
Materias:
Complexity
Geometric solutions
Mixed volume
Newton-Hensel lifting
Non-Archimedean height
Polyhedral deformations
Probabilistic algorithms
Puiseux expansions of space curves
Sparse system solving
Symbolic homotopy algorithms
Homotopy algorithms
Probabilistic algorithm
Space curve
Sparse systems
Algorithms
Deformation
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_16153375_v9_n1_p1_Jeronimo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
Descripción
Sumario: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. © 2008 SFoCM.

Ejemplares similares