O-GVW Algorithm Based On Signature Related Gr(?)bner Basis Algorithms

Grobner basis theory is a fundamental theory in computational algebraic geometry,and the efficient algorithm of Grobner basis is one of the core research goals of Grobner basis theory.GVW algorithm is an efficient algorithm based on Grobner base that has been widely concerned since its proposal in the past decade.The key two steps in the GVW algorithm are the generation of elements in H and the generation of J-pairs,which require a large number of computational steps.Based on the GVW algorithm,this paper introduces and applies the concept of O-pairs,proposes a new algorithm for elements in H and J-pairs,establishes the O-GVW algorithm,and discusses the improvement of the GVW algorithm in terms of computational efficiency.This article introduces the concept of O-pairs.Let R=K[x1,x2,…,xn]is a polynomial ring on the domain K with respect to variables x1,x2,…,xn.For defining a fixed term order on R,we want to calculate the Grobner basis of the ideal I=<g1,g2,…,gm>={u1g1+u2g2+…+umgm:u1,u2,…,um∈R}?R.We call H=｛(u1,u2,…,um)Rm:u1g1+u2g2+…+umgm=0} is a syzygy of g=(g1,g2,…,gm)Then the Rm × Rsubmodule of M=｛(u,v)∈ Rm × R:ugt=v}.The concept of O-pair is to sort the(u1,v1),(u2,v2)leading term according to the specified term order,and define different O-pairs according to different sorting results,which is essentially to store the sorting results in O-pairs.Moreover,O-pair is used to propose theorem 3.4,and a new algorithm is proposed for calculating the elements in H,which makes the calculation process simpler.In addition,the GCD algorithm is introduced in the J-pair calculation,and theorem 3.5 is proposed,which divides two cases according to whether gcd(u1,v1),(u2,v2)is zero when(u1,v1),(u2,v2)produces J-pair elements,and gives two J-pair calculation methods for different situations,and theoretically introduces the required calculation steps and times.In the fourth chapter of this paper,GVW method and O-GVW method are used for the same example problem,and the operation steps and the number of calculations required by the O-GVW algorithm and the GVW algorithm can be clearly seen through numerical experiments,which are consistent with the theoretical results.From the data,it can be seen that the O-GVW algorithm improves the computational efficiency compared with the GVW algorithm,and the correctness of the O-GVW algorithm is verified from both theory and examples.