**Victor Y. Pan
Department of Mathematics and Computer Science
Lehman College, City University of New York
Bronx, NY 10468
VPAN@ALPHA.LEHMAN.CUNY.EDU
**

Several effective techniques
are known
for solving a polynomial equation and
for some fundamental operations with dense structured matrices;
in particular, the arithmetic cost of these computations
has been
decreased
to a nearly optimal level (that
is, linear in the input size, up to polylogarithmic factors). We recall
and extend
some of
these techniques and results and combine them with other old and new algebraic techniques to
accelerate asymptotically the known algorithms for
polynomial systems of equations.
In this way, we
decreased the solution time from *D*^{3} to 12^{n} *D*^{2}for
the systems with
*n* variables and at most *D*solutions, *D*being either Bezout or Bernstein bound.
We view this improvement of a long standing complexity record as theoretical, due to the factor
12^{n}, but various techniques
that we
used
also
served
for us
as the basis of some promising practical heuristic
algorithms for polynomial system solving. (This work is joint
with Bernard Mourrain.)

IMACS ACA'98 Electronic Proceedings