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

id	todo:paper_16153375_v9_n1_p1_Jeronimo
record_format	dspace
spelling	todo:paper_16153375_v9_n1_p1_Jeronimo2023-10-03T16:28:17Z Deformation techniques for sparse systems Jeronimo, G. Matera, G. Solernó, P. Waissbein, A. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, G. Matera, G. Solernó, P. Waissbein, A. 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.
format	JOUR
author	Jeronimo, G. Matera, G. Solernó, P. Waissbein, A.
author_facet	Jeronimo, G. Matera, G. Solernó, P. Waissbein, A.
author_sort	Jeronimo, G.
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
url	http://hdl.handle.net/20.500.12110/paper_16153375_v9_n1_p1_Jeronimo
work_keys_str_mv	AT jeronimog deformationtechniquesforsparsesystems AT materag deformationtechniquesforsparsesystems AT solernop deformationtechniquesforsparsesystems AT waissbeina deformationtechniquesforsparsesystems
_version_	1807322719234031616

Deformation techniques for sparse systems

Ejemplares similares