Degeneracy Loci and Polynomial Equation Solving
Let (Formula presented.) be a smooth, equidimensional, quasi-affine variety of dimension (Formula presented.) over (Formula presented.), and let (Formula presented.) be a (Formula presented.) matrix of coordinate functions of (Formula presented.), where (Formula presented.). The pair (Formula presen...
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_16153375_v15_n1_p159_Bank |
| Aporte de: |
| id |
todo:paper_16153375_v15_n1_p159_Bank |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_16153375_v15_n1_p159_Bank2023-10-03T16:28:13Z Degeneracy Loci and Polynomial Equation Solving Bank, B. Giusti, M. Heintz, J. Lecerf, G. Matera, G. Solernó, P. Degeneracy locus Degree of varieties Polynomial equation solving Pseudo-polynomial complexity Algorithms Coordinate functions Degeneracy loci Degree of varieties Descending chain Elimination problem Polynomial complexity Polynomial equation solving Polynomial-time algorithms Polynomial approximation Let (Formula presented.) be a smooth, equidimensional, quasi-affine variety of dimension (Formula presented.) over (Formula presented.), and let (Formula presented.) be a (Formula presented.) matrix of coordinate functions of (Formula presented.), where (Formula presented.). The pair (Formula presented.) determines a vector bundle (Formula presented.) of rank (Formula presented.) over (Formula presented.). We associate with (Formula presented.) a descending chain of degeneracy loci of (Formula presented.) (the generic polar varieties of (Formula presented.) represent a typical example of this situation). The maximal degree of these degeneracy loci constitutes the essential ingredient for the uniform, bounded-error probabilistic pseudo-polynomial-time algorithm that we will design and that solves a series of computational elimination problems that can be formulated in this framework. We describe applications to polynomial equation solving over the reals and to the computation of a generic fiber of a dominant endomorphism of an affine space. © 2014, SFoCM. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_16153375_v15_n1_p159_Bank |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Degeneracy locus Degree of varieties Polynomial equation solving Pseudo-polynomial complexity Algorithms Coordinate functions Degeneracy loci Degree of varieties Descending chain Elimination problem Polynomial complexity Polynomial equation solving Polynomial-time algorithms Polynomial approximation |
| spellingShingle |
Degeneracy locus Degree of varieties Polynomial equation solving Pseudo-polynomial complexity Algorithms Coordinate functions Degeneracy loci Degree of varieties Descending chain Elimination problem Polynomial complexity Polynomial equation solving Polynomial-time algorithms Polynomial approximation Bank, B. Giusti, M. Heintz, J. Lecerf, G. Matera, G. Solernó, P. Degeneracy Loci and Polynomial Equation Solving |
| topic_facet |
Degeneracy locus Degree of varieties Polynomial equation solving Pseudo-polynomial complexity Algorithms Coordinate functions Degeneracy loci Degree of varieties Descending chain Elimination problem Polynomial complexity Polynomial equation solving Polynomial-time algorithms Polynomial approximation |
| description |
Let (Formula presented.) be a smooth, equidimensional, quasi-affine variety of dimension (Formula presented.) over (Formula presented.), and let (Formula presented.) be a (Formula presented.) matrix of coordinate functions of (Formula presented.), where (Formula presented.). The pair (Formula presented.) determines a vector bundle (Formula presented.) of rank (Formula presented.) over (Formula presented.). We associate with (Formula presented.) a descending chain of degeneracy loci of (Formula presented.) (the generic polar varieties of (Formula presented.) represent a typical example of this situation). The maximal degree of these degeneracy loci constitutes the essential ingredient for the uniform, bounded-error probabilistic pseudo-polynomial-time algorithm that we will design and that solves a series of computational elimination problems that can be formulated in this framework. We describe applications to polynomial equation solving over the reals and to the computation of a generic fiber of a dominant endomorphism of an affine space. © 2014, SFoCM. |
| format |
JOUR |
| author |
Bank, B. Giusti, M. Heintz, J. Lecerf, G. Matera, G. Solernó, P. |
| author_facet |
Bank, B. Giusti, M. Heintz, J. Lecerf, G. Matera, G. Solernó, P. |
| author_sort |
Bank, B. |
| title |
Degeneracy Loci and Polynomial Equation Solving |
| title_short |
Degeneracy Loci and Polynomial Equation Solving |
| title_full |
Degeneracy Loci and Polynomial Equation Solving |
| title_fullStr |
Degeneracy Loci and Polynomial Equation Solving |
| title_full_unstemmed |
Degeneracy Loci and Polynomial Equation Solving |
| title_sort |
degeneracy loci and polynomial equation solving |
| url |
http://hdl.handle.net/20.500.12110/paper_16153375_v15_n1_p159_Bank |
| work_keys_str_mv |
AT bankb degeneracylociandpolynomialequationsolving AT giustim degeneracylociandpolynomialequationsolving AT heintzj degeneracylociandpolynomialequationsolving AT lecerfg degeneracylociandpolynomialequationsolving AT materag degeneracylociandpolynomialequationsolving AT solernop degeneracylociandpolynomialequationsolving |
| _version_ |
1807317150320295936 |