A single exponential time algorithm for homogeneous regular sequence tests.

Assume that we are given a sequence F of k homogeneous polynomials in n variables of degree at most d and the ideal ℐ generated by this sequence. The aim of this paper is to present a new and effective method to determine, within the arithmetic complexity d O (n) , whether F is regular. This algorithm has been implemented in Maple and its efficiency (compared to the classical approaches for regular sequence test) is evaluated via a set of benchmark polynomials. Furthermore, we show that if F is regular then we can transform ℐ into Nœther position and at the same time compute a reduced Gröbner basis for the transformed ideal within the arithmetic complexity d O (n 2) . Finally, under the same assumption, we establish the new upper bound 2 (d k / 2) 2 n − k − 1 for the maximum degree of the elements of any reduced Gröbner basis of ℐ in the case that n > k. [ABSTRACT FROM AUTHOR]