剰余列とGCDによる辞書式グレブナー基底計算に対する種々の技法

Abstract

For as ystem of m+l polynomials in main variables (x) =(x 1, ... , xm≥2) and sub-variables (u) = (u1, ... , un≥1), we have two famous methods of eliminating x and obtain polynomials in u usually: the resultant method and the Gröbner basis method w.r.t. the term-order xi, ... , xm≻u1, ... , un , The latter method gives us the lowest order element of the ideal but the method is mostly very slow. The former method is quite fast but the resultant is a multiple of the lowest order element, and the multiplier which we call the extraneous factor, is often quite large. In recent several years, the author studied to generate polynomials which are small multiples of corresponding elements of the Gröbner basis. As for the system of two polynomials {G, H} ⊂Q[x, u], where G and H are relatively prime, he found that the lowest order element of elimination ideal〈G, H〉⋂Q[u] can be computed by the PRS (Polynomial Remainder Sequence) and the GCD (⇒ Theorem 1 [6]). As for systems of m≥2, the situation is complicated, so he made the situation simple by defining healthy system and confining himself to treat only healthy systems; most of actual systems are healthy. Let F :={Fi, ... , Fm +1} be a healthy system and GB(F) be the Gröbner basis of F w.r.t. the lexicographic order. Then, we have GB(F)⋂Q[u] = {S} (⇒ Theorem 2 [7]). On the basis of Theorems 1 and 2 mostly, he proposed a method to enhance Buchberger's algorithm in [5]. The proposed method is rather complicated and contains many problems, computational as well as theoretical. In this paper, after reviewing the new method as well as Theorems 1 and 2 in Sect. 2, we explain computational techniques in details which are necessary for making the new method efficient. We will show by experiments that, among various computational problems, computation of cofactors by the extended Euclid's method is the most serious problem, and we will propose a sophisticated algorithm for solving this problem.