We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A single exponential time algorithm for homogeneous regular sequence tests.
- Authors
Hashemi, Amir; Alizadeh, Benyamin M.; Parnian, Hossein; Seiler, Werner M.
- Abstract
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.
- Subjects
HOMOGENEOUS polynomials; ARITHMETIC; POLYNOMIALS; ALGORITHMS
- Publication
Journal of Algebra & Its Applications, 2024, Vol 23, Issue 9, p1
- ISSN
0219-4988
- Publication type
Article
- DOI
10.1142/S0219498824501457