2021-06-24T16:15:59Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmh
oai:ipsj.ixsq.nii.ac.jp:000597672017-03-31T05:36:57Z05471:05490:05491
A Modular Method for Grobner-basis Construction over Q and Solving System of Algebraic EquationsA Modular Method for Grobner-basis Construction over Q and Solving System of Algebraic Equationsenghttp://id.nii.ac.jp/1001/00059767/Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=59767&item_no=1&attribute_id=1&file_no=1Copyright (c) 1990 by the Information Processing Society of JapanThe Institute of Physical and Chemical ResearchFujitsu LimitedTateaki, SasakiTaku, TakeshimaA 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.AA00700121Journal of Information Processing 1243713791990-03-151882-66522009-06-30