The intrinsic complexity of parametric elimination methods

This paper is devoted to the complexity analysis of a particular property, called geometric robustness owned by all known symbolic methods of parametric polynomial equation solving (geometric elimination). It is shown that any parametric elimination procedure which owns this property must necessaril...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Heintz, J., Matera, G., Pardo, L. M., Wachenchauzer, R.
Formato:	Articulo
Lenguaje:	Inglés
Publicado:	1998
Materias:	Ciencias Informáticas Polynomial system solving elimination complexity
Acceso en línea:	http://sedici.unlp.edu.ar/handle/10915/135547 https://publicaciones.sadio.org.ar/index.php/EJS/article/view/134
Aporte de:	SEDICI (UNLP) de Universidad Nacional de La Plata

id	I19-R120-10915-135547
record_format	dspace
institution	Universidad Nacional de La Plata
institution_str	I-19
repository_str	R-120
collection	SEDICI (UNLP)
language	Inglés
topic	Ciencias Informáticas Polynomial system solving elimination complexity
spellingShingle	Ciencias Informáticas Polynomial system solving elimination complexity Heintz, J. Matera, G. Pardo, L. M. Wachenchauzer, R. The intrinsic complexity of parametric elimination methods
topic_facet	Ciencias Informáticas Polynomial system solving elimination complexity
description	This paper is devoted to the complexity analysis of a particular property, called geometric robustness owned by all known symbolic methods of parametric polynomial equation solving (geometric elimination). It is shown that any parametric elimination procedure which owns this property must necessarily have an exponential sequential time complexity even if highly performant data structures (as e.g. the straight--line program encoding of polynomials) are used. The paper finishes with the motivated introduction of a new non-uniform complexity measure for zero-dimensional polynomial equation systems, called elimination complexity.
format	Articulo Articulo
author	Heintz, J. Matera, G. Pardo, L. M. Wachenchauzer, R.
author_facet	Heintz, J. Matera, G. Pardo, L. M. Wachenchauzer, R.
author_sort	Heintz, J.
title	The intrinsic complexity of parametric elimination methods
title_short	The intrinsic complexity of parametric elimination methods
title_full	The intrinsic complexity of parametric elimination methods
title_fullStr	The intrinsic complexity of parametric elimination methods
title_full_unstemmed	The intrinsic complexity of parametric elimination methods
title_sort	intrinsic complexity of parametric elimination methods
publishDate	1998
url	http://sedici.unlp.edu.ar/handle/10915/135547 https://publicaciones.sadio.org.ar/index.php/EJS/article/view/134
work_keys_str_mv	AT heintzj theintrinsiccomplexityofparametriceliminationmethods AT materag theintrinsiccomplexityofparametriceliminationmethods AT pardolm theintrinsiccomplexityofparametriceliminationmethods AT wachenchauzerr theintrinsiccomplexityofparametriceliminationmethods AT heintzj intrinsiccomplexityofparametriceliminationmethods AT materag intrinsiccomplexityofparametriceliminationmethods AT pardolm intrinsiccomplexityofparametriceliminationmethods AT wachenchauzerr intrinsiccomplexityofparametriceliminationmethods
bdutipo_str	Repositorios
_version_	1764820455459389440

The intrinsic complexity of parametric elimination methods

Ejemplares similares