On the Complexity of Zero-dimensional Algebraic Systems

A probabilistic algorithm is given which, a zero-dimensional system of polynomials being given, computes Gröbner base for any ordering of its radical and/or all of its irreducible components in time dO(n) where d is the maximal degree of the polynomials and n the number of variables. With probability nearly 1, no component is lost.This algorithm can decide zero-dimensionality with the same complexity and the same probability of success.These complexities remain valid even if the system is not zero-dimensional at infinity.This algorithm is a pratical one; it is probably slower than the computation of the Gröbner base for a degree ordering but faster than the same computation with a variable more.