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...
| Autores principales: | , , |
|---|---|
| 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 |