http://swrc.ontoware.org/ontology#Article
A Modular Method for Grobner-basis Construction over Q and Solving System of Algebraic Equations
en
The Institute of Physical and Chemical Research
Fujitsu Limited
Tateaki Sasaki
Taku Takeshima
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) ￥deal(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.
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) ￥deal(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.
AA00700121
Journal of Information Processing
12
4
371-379
1990-03-15
1882-6652