INVESTIGADORES
SABIA Juan Vicente Rafael
capítulos de libros
Título:
Algorithms and their complexities
Autor/es:
SABIA, JUAN
Libro:
Solving Polynomial Equations. Foundations, algorithms and applications. Alicia Dickenstein and Ioannis Emiris, eds.
Editorial:
Springer
Referencias:
Lugar: Berlin - Heidelberg - New York; Año: 2005; p. 241 - 268
Resumen:
This chapter is intended as a brief survey of the different notions and
results that arise when we try to compute the algebraic complexity of algorithms
solving polynomial equation systems. Although it is essentially self-contained, many
of the definitions, problems and results we deal with also appear in many other
chapters of this book. We start by considering algorithms which use the dense representation
of multivariate polynomials. Some results about the algebraic complexities
of the effective Nullstellensatz, of quantifier elimination processes over algebraically
closed fields and of the decomposition of algebraic varieties when considering this
model are stated. Then, it is shown that these complexities are essentially optimal
in the dense representation model. This is the reason why a change in the
encoding of polynomials is needed to get better upper bounds for the complexities
of new algorithms solving the already mentioned tasks. The straight-line program
representation for multivariate polynomials is defined and briefly discussed. Some
complexity results for algorithms in the straight-line program representation model
are mentioned (an effective Nullstellensatz and quantifier elimination procedures,
for instance). A description of the Newton-Hensel method to approximate roots of
a system of parametric polynomial equations is made. Finally, we mention some
new trends to avoid large complexities when trying to solve polynomial equation
systems.