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 D3 to 12n D2for the systems with n variables and at most Dsolutions, Dbeing either Bezout or Bernstein bound. We view this improvement of a long standing complexity record as theoretical, due to the factor 12n, 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.)