The Computational Complexity of the Chow Form

We present a bounded probability algorithm for the computation of the Chow forms of the equidimensional components of an algebraic variety. In particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety, since each equidimensional component is chara...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Jeronimo, G., Krick, T., Sabia, J., Sombra, M.
Formato:	JOUR
Materias:	Chow form Equidimensional decomposition of algebraic varieties Overdetermined polynomial equation system Sparse resultant Symbolic Newton algorithm Algorithms Computational methods Partial differential equations Polynomials Probability Set theory Bounded probability algorithm Computational complexity
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_16153375_v4_n1_p41_Jeronimo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_16153375_v4_n1_p41_Jeronimo
record_format	dspace
spelling	todo:paper_16153375_v4_n1_p41_Jeronimo2023-10-03T16:28:16Z The Computational Complexity of the Chow Form Jeronimo, G. Krick, T. Sabia, J. Sombra, M. Chow form Equidimensional decomposition of algebraic varieties Overdetermined polynomial equation system Sparse resultant Symbolic Newton algorithm Algorithms Computational methods Partial differential equations Polynomials Probability Set theory Bounded probability algorithm Chow form Computational complexity We present a bounded probability algorithm for the computation of the Chow forms of the equidimensional components of an algebraic variety. In particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety, since each equidimensional component is characterized by its Chow form. The expected complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence it improves (or meets in some special cases) the complexity of all previous algorithms for computing Chow forms. In addition to this, we clarify the probability and uniformity aspects, which constitutes a further contribution of the paper. The algorithm is based on elimination theory techniques, in line with the geometric resolution algorithm due to M. Giusti, J. Heintz, L. M. Pardo, and their collaborators. In fact, ours can be considered as an extension of their algorithm for zero-dimensional systems to the case of positive-dimensional varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows us to compute the Chow form of an equidimensional variety from a suitable zero-dimensional fiber. As an application, we obtain an algorithm to compute a subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, we derive an algorithm for the computation of the (unique) solution of a generic overdetermined polynomial equation system. Fil:Jeronimo, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Krick, T. 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. Fil:Sombra, M. 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_v4_n1_p41_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	Chow form Equidimensional decomposition of algebraic varieties Overdetermined polynomial equation system Sparse resultant Symbolic Newton algorithm Algorithms Computational methods Partial differential equations Polynomials Probability Set theory Bounded probability algorithm Chow form Computational complexity
spellingShingle	Chow form Equidimensional decomposition of algebraic varieties Overdetermined polynomial equation system Sparse resultant Symbolic Newton algorithm Algorithms Computational methods Partial differential equations Polynomials Probability Set theory Bounded probability algorithm Chow form Computational complexity Jeronimo, G. Krick, T. Sabia, J. Sombra, M. The Computational Complexity of the Chow Form
topic_facet	Chow form Equidimensional decomposition of algebraic varieties Overdetermined polynomial equation system Sparse resultant Symbolic Newton algorithm Algorithms Computational methods Partial differential equations Polynomials Probability Set theory Bounded probability algorithm Chow form Computational complexity
description	We present a bounded probability algorithm for the computation of the Chow forms of the equidimensional components of an algebraic variety. In particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety, since each equidimensional component is characterized by its Chow form. The expected complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence it improves (or meets in some special cases) the complexity of all previous algorithms for computing Chow forms. In addition to this, we clarify the probability and uniformity aspects, which constitutes a further contribution of the paper. The algorithm is based on elimination theory techniques, in line with the geometric resolution algorithm due to M. Giusti, J. Heintz, L. M. Pardo, and their collaborators. In fact, ours can be considered as an extension of their algorithm for zero-dimensional systems to the case of positive-dimensional varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows us to compute the Chow form of an equidimensional variety from a suitable zero-dimensional fiber. As an application, we obtain an algorithm to compute a subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, we derive an algorithm for the computation of the (unique) solution of a generic overdetermined polynomial equation system.
format	JOUR
author	Jeronimo, G. Krick, T. Sabia, J. Sombra, M.
author_facet	Jeronimo, G. Krick, T. Sabia, J. Sombra, M.
author_sort	Jeronimo, G.
title	The Computational Complexity of the Chow Form
title_short	The Computational Complexity of the Chow Form
title_full	The Computational Complexity of the Chow Form
title_fullStr	The Computational Complexity of the Chow Form
title_full_unstemmed	The Computational Complexity of the Chow Form
title_sort	computational complexity of the chow form
url	http://hdl.handle.net/20.500.12110/paper_16153375_v4_n1_p41_Jeronimo
work_keys_str_mv	AT jeronimog thecomputationalcomplexityofthechowform AT krickt thecomputationalcomplexityofthechowform AT sabiaj thecomputationalcomplexityofthechowform AT sombram thecomputationalcomplexityofthechowform AT jeronimog computationalcomplexityofthechowform AT krickt computationalcomplexityofthechowform AT sabiaj computationalcomplexityofthechowform AT sombram computationalcomplexityofthechowform
_version_	1807318069019672576

The Computational Complexity of the Chow Form

Ejemplares similares