Deformation Techniques for Efficient Polynomial Equation Solving

Mostrar todas las versiones(3)

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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A.
Formato: Artículo publishedVersion
Publicado: 2000
Materias:
Polynomial equation system; arithmetic circuit; shape (or primitive element) lemma; Newton-Hensel iteration
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0885064X_v16_n1_p70_Heintz
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0885064X_v16_n1_p70_Heintz_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-paper_0885064X_v16_n1_p70_Heintz_oai
record_format dspace
spelling I28-R145-paper_0885064X_v16_n1_p70_Heintz_oai2024-08-16 Heintz, J. Krick, T. Puddu, S. Sabia, J. Waissbein, A. 2000 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. application/pdf http://hdl.handle.net/20.500.12110/paper_0885064X_v16_n1_p70_Heintz info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar J. Complexity 2000;16(1):70-109 Polynomial equation system; arithmetic circuit; shape (or primitive element) lemma; Newton-Hensel iteration Deformation Techniques for Efficient Polynomial Equation Solving 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_0885064X_v16_n1_p70_Heintz_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 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
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0885064X_v16_n1_p70_Heintz_oai
work_keys_str_mv AT heintzj deformationtechniquesforefficientpolynomialequationsolving
AT krickt deformationtechniquesforefficientpolynomialequationsolving
AT puddus deformationtechniquesforefficientpolynomialequationsolving
AT sabiaj deformationtechniquesforefficientpolynomialequationsolving
AT waissbeina deformationtechniquesforefficientpolynomialequationsolving
_version_ 1809356821983395840

Ejemplares similares