On the Time-Space Complexity of Geometric Elimination Procedures

In [25] and [22] 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 ge...

Full description

Saved in:
Bibliographic Details
Published in:Applicable algebra in engineering, communication and computing communication and computing, 2001, Vol.11 (4), p.239-296
Main Authors: Heintz, Joos, Matera, Guillermo, Waissbein, Ariel
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In [25] and [22] 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.
ISSN:0938-1279
1432-0622
DOI:10.1007/s002000000046