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...

Descripción completa

Detalles Bibliográficos
Publicado: 2014
Materias:
Degeneracy locus
Degree of varieties
Polynomial equation solving
Pseudo-polynomial complexity
Algorithms
Coordinate functions
Degeneracy loci
Descending chain
Elimination problem
Polynomial complexity
Polynomial-time algorithms
Polynomial approximation
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v15_n1_p159_Bank
http://hdl.handle.net/20.500.12110/paper_16153375_v15_n1_p159_Bank
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_16153375_v15_n1_p159_Bank
record_format dspace
spelling paper:paper_16153375_v15_n1_p159_Bank2023-06-08T16:25:21Z Degeneracy Loci and Polynomial Equation Solving 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. 2014 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v15_n1_p159_Bank 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
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.
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
publishDate 2014
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v15_n1_p159_Bank
http://hdl.handle.net/20.500.12110/paper_16153375_v15_n1_p159_Bank
_version_ 1768544430134919168

Ejemplares similares