On the Complexity of Zero-dimensional Algebraic Systems
Y. N. Lakshman, Daniel Lazard · Progress in mathematics · 1991
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 d O ( 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. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.