Probabilistic algorithms for geometric elimination. (English) Zbl 0934.68122

Summary: We develop probabilistic algorithms that solve problems of geometric elimination theory using small memory resources. These algorithms are obtained by means of the adaptation of a general transformation due to A. Borodin which converts uniform Boolean circuit depth into sequential (Turing machine) space. The Boolean circuits themselves are developed using techniques based on the computation of a primitive element of a suitable zero-dimensional algebra and diophantine considerations.
Our algorithms improve considerably the space requirements of the elimination algorithms based on rewriting techniques (Gröbner solving), having simultaneously a time performance of the same kind of them.


68W05 Nonnumerical algorithms
68W30 Symbolic computation and algebraic computation
Full Text: DOI