×

Straight-line programs in polynomial equation solving. (English) Zbl 1097.65063

Cucker, Felipe (ed.) et al., Foundations of computational mathematics: Minneapolis 2002 (FoCM 2002). Selected papers based on the plenary talks presented at FoCM 2002, Minneapolis, MN, USA, August 5–14, 2002. Cambridge: Cambridge University Press (ISBN 0-521-54253-7/pbk). London Mathematical Society Lecture Note Series 312, 96-136 (2004).
Summary: Solving symbolically polynomial equation systems when intermediate and final polynomials are represented in the usual dense encoding turns out to be very inefficient: the sizes of the systems one can deal with do not respond to realistic needs. Evaluation representations appeared in this frame a decade ago as a decade ago as a new possibility to treat new families of problems. We present a survey of the most recent complexity results for different polynomial problems when polynomials are encoded by evaluation (straight-line) programs. We also show surprising mathematical by-products, such as new mathematical invariants and results, that appeared as a consequence of the search of good algorithms.
For the entire collection see [Zbl 1084.65004].

MSC:

65H05 Numerical computation of solutions to single equations
12Y05 Computational aspects of field theory and polynomials (MSC2010)
26C10 Real polynomials: location of zeros
65Y20 Complexity and performance of numerical algorithms
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)

Software:

Kronecker
PDFBibTeX XMLCite