Deformation Techniques for Efficient Polynomial Equation Solving
Suppose we are given a parametric polynomial equation system encoded by an arithmetic circuit, which represents a generically flat and unramified family of zero-dimensional algebraic varieties. Let us also assume that there is given the complete description of the solution of a particular unramified...
Guardado en:
Autores principales: | , , , , |
---|---|
Formato: | Artículo publishedVersion |
Lenguaje: | Inglés |
Publicado: |
2000
|
Materias: | |
Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0885064X_v16_n1_p70_Heintz |
Aporte de: |
id |
paperaa:paper_0885064X_v16_n1_p70_Heintz |
---|---|
record_format |
dspace |
spelling |
paperaa:paper_0885064X_v16_n1_p70_Heintz2023-06-12T16:48:17Z Deformation Techniques for Efficient Polynomial Equation Solving J. Complexity 2000;16(1):70-109 Heintz, J. Krick, T. Puddu, S. Sabia, J. Waissbein, A. Polynomial equation system; arithmetic circuit; shape (or primitive element) lemma; Newton-Hensel iteration Suppose we are given a parametric polynomial equation system encoded by an arithmetic circuit, which represents a generically flat and unramified family of zero-dimensional algebraic varieties. Let us also assume that there is given the complete description of the solution of a particular unramified parameter instance of our system. We show that it is possible to "move" the given particular solution along the parameter space in order to reconstruct - by means of an arithmetic circuit - the coordinates of the solutions of the system for an arbitrary parameter instance. The underlying algorithm is highly efficient, i.e., polynomial in the syntactic description of the input and the following geometric invariants: the number of solutions of a typical parameter instance and the degree of the polynomials occurring in the output. In fact, we prove a slightly more general result, which implies the previous statement by means of a well-known primitive element algorithm. We produce an efficient algorithmic description of the hypersurface obtained projecting polynomially the given generically flat family of varieties into a suitable affine space. © 2000 Academic Press. Fil:Krick, T. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Puddu, S. 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. 2000 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0885064X_v16_n1_p70_Heintz |
institution |
Universidad de Buenos Aires |
institution_str |
I-28 |
repository_str |
R-134 |
collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
language |
Inglés |
orig_language_str_mv |
eng |
topic |
Polynomial equation system; arithmetic circuit; shape (or primitive element) lemma; Newton-Hensel iteration |
spellingShingle |
Polynomial equation system; arithmetic circuit; shape (or primitive element) lemma; Newton-Hensel iteration Heintz, J. Krick, T. Puddu, S. Sabia, J. Waissbein, A. Deformation Techniques for Efficient Polynomial Equation Solving |
topic_facet |
Polynomial equation system; arithmetic circuit; shape (or primitive element) lemma; Newton-Hensel iteration |
description |
Suppose we are given a parametric polynomial equation system encoded by an arithmetic circuit, which represents a generically flat and unramified family of zero-dimensional algebraic varieties. Let us also assume that there is given the complete description of the solution of a particular unramified parameter instance of our system. We show that it is possible to "move" the given particular solution along the parameter space in order to reconstruct - by means of an arithmetic circuit - the coordinates of the solutions of the system for an arbitrary parameter instance. The underlying algorithm is highly efficient, i.e., polynomial in the syntactic description of the input and the following geometric invariants: the number of solutions of a typical parameter instance and the degree of the polynomials occurring in the output. In fact, we prove a slightly more general result, which implies the previous statement by means of a well-known primitive element algorithm. We produce an efficient algorithmic description of the hypersurface obtained projecting polynomially the given generically flat family of varieties into a suitable affine space. © 2000 Academic Press. |
format |
Artículo Artículo publishedVersion |
author |
Heintz, J. Krick, T. Puddu, S. Sabia, J. Waissbein, A. |
author_facet |
Heintz, J. Krick, T. Puddu, S. Sabia, J. Waissbein, A. |
author_sort |
Heintz, J. |
title |
Deformation Techniques for Efficient Polynomial Equation Solving |
title_short |
Deformation Techniques for Efficient Polynomial Equation Solving |
title_full |
Deformation Techniques for Efficient Polynomial Equation Solving |
title_fullStr |
Deformation Techniques for Efficient Polynomial Equation Solving |
title_full_unstemmed |
Deformation Techniques for Efficient Polynomial Equation Solving |
title_sort |
deformation techniques for efficient polynomial equation solving |
publishDate |
2000 |
url |
http://hdl.handle.net/20.500.12110/paper_0885064X_v16_n1_p70_Heintz |
work_keys_str_mv |
AT heintzj deformationtechniquesforefficientpolynomialequationsolving AT krickt deformationtechniquesforefficientpolynomialequationsolving AT puddus deformationtechniquesforefficientpolynomialequationsolving AT sabiaj deformationtechniquesforefficientpolynomialequationsolving AT waissbeina deformationtechniquesforefficientpolynomialequationsolving |
_version_ |
1769810033805099008 |