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, Gabriela Tali, Matera, Guillermo, Solerno, Pablo Luis
Publicado:	2009
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:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v9_n1_p1_Jeronimo 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

id	paper:paper_16153375_v9_n1_p1_Jeronimo
record_format	dspace
spelling	paper:paper_16153375_v9_n1_p1_Jeronimo2023-06-08T16:25:24Z Deformation techniques for sparse systems Jeronimo, Gabriela Tali Matera, Guillermo Solerno, Pablo Luis 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 Complexity Homotopy algorithms Mixed volume Newton-Hensel lifting Non-Archimedean height Probabilistic algorithm Space curve Sparse systems Algorithms Deformation 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. Fil:Jeronimo, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Matera, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Solernó, P. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2009 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v9_n1_p1_Jeronimo http://hdl.handle.net/20.500.12110/paper_16153375_v9_n1_p1_Jeronimo
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	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 Complexity Homotopy algorithms Mixed volume Newton-Hensel lifting Non-Archimedean height Probabilistic algorithm Space curve Sparse systems Algorithms Deformation
spellingShingle	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 Complexity Homotopy algorithms Mixed volume Newton-Hensel lifting Non-Archimedean height Probabilistic algorithm Space curve Sparse systems Algorithms Deformation Jeronimo, Gabriela Tali Matera, Guillermo Solerno, Pablo Luis Deformation techniques for sparse systems
topic_facet	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 Complexity Homotopy algorithms Mixed volume Newton-Hensel lifting Non-Archimedean height Probabilistic algorithm Space curve Sparse systems Algorithms Deformation
description	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.
author	Jeronimo, Gabriela Tali Matera, Guillermo Solerno, Pablo Luis
author_facet	Jeronimo, Gabriela Tali Matera, Guillermo Solerno, Pablo Luis
author_sort	Jeronimo, Gabriela Tali
title	Deformation techniques for sparse systems
title_short	Deformation techniques for sparse systems
title_full	Deformation techniques for sparse systems
title_fullStr	Deformation techniques for sparse systems
title_full_unstemmed	Deformation techniques for sparse systems
title_sort	deformation techniques for sparse systems
publishDate	2009
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v9_n1_p1_Jeronimo http://hdl.handle.net/20.500.12110/paper_16153375_v9_n1_p1_Jeronimo
work_keys_str_mv	AT jeronimogabrielatali deformationtechniquesforsparsesystems AT materaguillermo deformationtechniquesforsparsesystems AT solernopabloluis deformationtechniquesforsparsesystems
_version_	1768545849138216960

Deformation techniques for sparse systems

Ejemplares similares