Probabilistic Algorithms for Geometric Elimination. - Matera, Guillermo
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.
Keywords: Probabilistic algorithms; Elimination theory; Boolean circuits; Arithmetic circuits