Computing isolated roots of sparse polynomial systems in affine space

We present a symbolic probabilistic algorithm to compute the isolated roots in Cn of sparse polynomial equation systems. As some already known numerical algorithms solving this task, our procedure is based on polyhedral deformations and homotopies, but it amounts to solving a smaller number of squar...

Descripción completa

Detalles Bibliográficos
Autores principales: Herrero, M.I., Jeronimo, G., Sabia, J.
Formato: Artículo publishedVersion
Publicado: 2010
Materias:
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03043975_v411_n44-46_p3894_Herrero
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03043975_v411_n44-46_p3894_Herrero_oai
Aporte de:
id I28-R145-paper_03043975_v411_n44-46_p3894_Herrero_oai
record_format dspace
spelling I28-R145-paper_03043975_v411_n44-46_p3894_Herrero_oai2024-08-16 Herrero, M.I. Jeronimo, G. Sabia, J. 2010 We present a symbolic probabilistic algorithm to compute the isolated roots in Cn of sparse polynomial equation systems. As some already known numerical algorithms solving this task, our procedure is based on polyhedral deformations and homotopies, but it amounts to solving a smaller number of square systems of equations and in fewer variables. The output of the algorithm is a geometric resolution of a finite set of points including the isolated roots of the system. The complexity is polynomial in the size of the combinatorial structure of the system supports up to a pre-processing yielding the mixed cells in a subdivision of the family of these supports. © 2010 Elsevier B.V. All rights reserved. Fil:Herrero, M.I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Jeronimo, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Sabia, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf http://hdl.handle.net/20.500.12110/paper_03043975_v411_n44-46_p3894_Herrero info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Theor Comput Sci 2010;411(44-46):3894-3904 Algorithms Complexity Sparse polynomial systems Affine space Combinatorial structures Complexity Finite set Geometric resolution Homotopies Numerical algorithms Pre-processing Probabilistic algorithm Sparse polynomials System supports Systems of equations Algorithms Topology Polynomials Computing isolated roots of sparse polynomial systems in affine space info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03043975_v411_n44-46_p3894_Herrero_oai
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
topic Algorithms
Complexity
Sparse polynomial systems
Affine space
Combinatorial structures
Complexity
Finite set
Geometric resolution
Homotopies
Numerical algorithms
Pre-processing
Probabilistic algorithm
Sparse polynomials
System supports
Systems of equations
Algorithms
Topology
Polynomials
spellingShingle Algorithms
Complexity
Sparse polynomial systems
Affine space
Combinatorial structures
Complexity
Finite set
Geometric resolution
Homotopies
Numerical algorithms
Pre-processing
Probabilistic algorithm
Sparse polynomials
System supports
Systems of equations
Algorithms
Topology
Polynomials
Herrero, M.I.
Jeronimo, G.
Sabia, J.
Computing isolated roots of sparse polynomial systems in affine space
topic_facet Algorithms
Complexity
Sparse polynomial systems
Affine space
Combinatorial structures
Complexity
Finite set
Geometric resolution
Homotopies
Numerical algorithms
Pre-processing
Probabilistic algorithm
Sparse polynomials
System supports
Systems of equations
Algorithms
Topology
Polynomials
description We present a symbolic probabilistic algorithm to compute the isolated roots in Cn of sparse polynomial equation systems. As some already known numerical algorithms solving this task, our procedure is based on polyhedral deformations and homotopies, but it amounts to solving a smaller number of square systems of equations and in fewer variables. The output of the algorithm is a geometric resolution of a finite set of points including the isolated roots of the system. The complexity is polynomial in the size of the combinatorial structure of the system supports up to a pre-processing yielding the mixed cells in a subdivision of the family of these supports. © 2010 Elsevier B.V. All rights reserved.
format Artículo
Artículo
publishedVersion
author Herrero, M.I.
Jeronimo, G.
Sabia, J.
author_facet Herrero, M.I.
Jeronimo, G.
Sabia, J.
author_sort Herrero, M.I.
title Computing isolated roots of sparse polynomial systems in affine space
title_short Computing isolated roots of sparse polynomial systems in affine space
title_full Computing isolated roots of sparse polynomial systems in affine space
title_fullStr Computing isolated roots of sparse polynomial systems in affine space
title_full_unstemmed Computing isolated roots of sparse polynomial systems in affine space
title_sort computing isolated roots of sparse polynomial systems in affine space
publishDate 2010
url http://hdl.handle.net/20.500.12110/paper_03043975_v411_n44-46_p3894_Herrero
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03043975_v411_n44-46_p3894_Herrero_oai
work_keys_str_mv AT herreromi computingisolatedrootsofsparsepolynomialsystemsinaffinespace
AT jeronimog computingisolatedrootsofsparsepolynomialsystemsinaffinespace
AT sabiaj computingisolatedrootsofsparsepolynomialsystemsinaffinespace
_version_ 1809356906601381888