Probabilistic algorithms for geometric elimination. (English) Zbl 0934.68122

Matera, Guillermo

Appl. Algebra Eng. Commun. Comput. 9, No. 6, 463-520 (1999).

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.

MSC:

68W05	Nonnumerical algorithms
68W30	Symbolic computation and algebraic computation

Keywords:

probabilistic algorithms; elimination theory; Boolean circuit