A Modular Method for Grobner-basis Construction over Q and Solving System of Algebraic Equations

概要

論文の詳細を見る
A modular method for constructing Grobner-basis of polynomial ideal over Q is described. Given a finite set of polynomials in Z[x_1, . . . , x_n], the method calculates Grobner-bases over Z/(p_i), i= 1, . . . , k, where p_1, . . . ,p_k are distinct primes, then it constructs a Grobner-basis over Q by using Chinese remainder algorithm and con-version of integers to rationals. By this method, we can calculate Grobner-basis with large-sized coefficients efficiently by avoiding intermediate coefficient growth. We propose two algorithms, one is simple but probabilistic in that it may give a wrong basis such that ideal(wrong basis) ⊃ideal(true basis) with an extremely small possibility, and the other is less simple but gives the correct basis. we also discuss solving system of algebraic equations by using the modular Grobner-basis method.
一般社団法人情報処理学会の論文
1990-03-15