Software Engineering and complexity in effective Algebraic Geometry

One may represent polynomials not only by their coefficients but also by arithmetic circuits which evaluate them. This idea allowed in the past fifteen years considerable complexity progress in effective polynomial equation solving. We present a circuit based computation model which captures all kno...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Heintz, J., Kuijpers, B., Rojas Paredes, A.
Formato: JOUR
Materias:
Branching parsimonious algorithm
Flat family of zero dimensional elimination problems
Isoparametric routine
Robust parameterized arithmetic circuit
Logic circuits
Polynomials
Software engineering
Algebraic geometry
Arithmetic circuit
Computation model
Elimination problem
Iso-parametric
Polynomial equation solving
Geometry
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0885064X_v29_n1_p92_Heintz
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_0885064X_v29_n1_p92_Heintz
record_format dspace
spelling todo:paper_0885064X_v29_n1_p92_Heintz2023-10-03T15:40:40Z Software Engineering and complexity in effective Algebraic Geometry Heintz, J. Kuijpers, B. Rojas Paredes, A. Branching parsimonious algorithm Flat family of zero dimensional elimination problems Isoparametric routine Robust parameterized arithmetic circuit Logic circuits Polynomials Software engineering Algebraic geometry Arithmetic circuit Computation model Elimination problem Iso-parametric Polynomial equation solving Geometry One may represent polynomials not only by their coefficients but also by arithmetic circuits which evaluate them. This idea allowed in the past fifteen years considerable complexity progress in effective polynomial equation solving. We present a circuit based computation model which captures all known symbolic elimination algorithms in effective Algebraic Geometry and exhibit a class of simple elimination problems which require exponential size circuits to be solved in this model. This implies that the known, circuit based elimination algorithms are already optimal. © 2012 Elsevier Inc. All rights reserved. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0885064X_v29_n1_p92_Heintz
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Branching parsimonious algorithm
Flat family of zero dimensional elimination problems
Isoparametric routine
Robust parameterized arithmetic circuit
Logic circuits
Polynomials
Software engineering
Algebraic geometry
Arithmetic circuit
Computation model
Elimination problem
Iso-parametric
Polynomial equation solving
Geometry
spellingShingle Branching parsimonious algorithm
Flat family of zero dimensional elimination problems
Isoparametric routine
Robust parameterized arithmetic circuit
Logic circuits
Polynomials
Software engineering
Algebraic geometry
Arithmetic circuit
Computation model
Elimination problem
Iso-parametric
Polynomial equation solving
Geometry
Heintz, J.
Kuijpers, B.
Rojas Paredes, A.
Software Engineering and complexity in effective Algebraic Geometry
topic_facet Branching parsimonious algorithm
Flat family of zero dimensional elimination problems
Isoparametric routine
Robust parameterized arithmetic circuit
Logic circuits
Polynomials
Software engineering
Algebraic geometry
Arithmetic circuit
Computation model
Elimination problem
Iso-parametric
Polynomial equation solving
Geometry
description One may represent polynomials not only by their coefficients but also by arithmetic circuits which evaluate them. This idea allowed in the past fifteen years considerable complexity progress in effective polynomial equation solving. We present a circuit based computation model which captures all known symbolic elimination algorithms in effective Algebraic Geometry and exhibit a class of simple elimination problems which require exponential size circuits to be solved in this model. This implies that the known, circuit based elimination algorithms are already optimal. © 2012 Elsevier Inc. All rights reserved.
format JOUR
author Heintz, J.
Kuijpers, B.
Rojas Paredes, A.
author_facet Heintz, J.
Kuijpers, B.
Rojas Paredes, A.
author_sort Heintz, J.
title Software Engineering and complexity in effective Algebraic Geometry
title_short Software Engineering and complexity in effective Algebraic Geometry
title_full Software Engineering and complexity in effective Algebraic Geometry
title_fullStr Software Engineering and complexity in effective Algebraic Geometry
title_full_unstemmed Software Engineering and complexity in effective Algebraic Geometry
title_sort software engineering and complexity in effective algebraic geometry
url http://hdl.handle.net/20.500.12110/paper_0885064X_v29_n1_p92_Heintz
work_keys_str_mv AT heintzj softwareengineeringandcomplexityineffectivealgebraicgeometry
AT kuijpersb softwareengineeringandcomplexityineffectivealgebraicgeometry
AT rojasparedesa softwareengineeringandcomplexityineffectivealgebraicgeometry
_version_ 1782029591342219264

Ejemplares similares