On the time-space complexity of geometric elimination procedures. (English) Zbl 0977.68101

Summary: In [M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern and L. M. Pardo, J. Pure Appl. Algebra 124, No. 1-3, 101-146 (1998; Zbl 0944.12004)] and [M. Giusti, J. Heintz, K. Hägele, J. E. Morais, L. M. Pardo and J. L. Montaña, ibid. 117-118, 277-317 (1997; Zbl 0871.68101)] a new algorithmic concept was introduced for the symbolic solution of a zero dimensional complete intersection polynomial equation system satisfying a certain generic smoothness condition. The main innovative point of this algorithmic concept consists in the introduction of a new geometric invariant, called the degree of the input system, and the proof that the most common elimination problems have time complexity, which is polynomial in this degree and the length of the input. In this paper we apply this algorithmic concept in order to exhibit an elimination procedure whose space complexity is only quadratic and its time complexity is only cubic in the degree of the input system.


68W30 Symbolic computation and algebraic computation
68Q25 Analysis of algorithms and problem complexity
14Q99 Computational aspects in algebraic geometry


Full Text: DOI