On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal

Y. N. Lakshman

1990 · 35 citations · 19 references

DOIFull text

Open access

Concepts

Abstract

We show that if a system of polynomials fl,f2,... ,Jr in n variables with deg(fl) _< d over the rational numbers has only finitely many affine zeros, then, all the affine zeros can be determined in time polynomial in d n by a Las Vegas type randomized algorithm. We then describe single exponential time algorithms to compute reduced Gr5bner bases for the radical of the ideal generated by fi and for all the prime ideals containing the radical.

References

19