Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleModular algorithms for computing Gröbner bases
Author(s) Elizabeth A. Arnold
TypeArticle in Journal
AbstractIntermediate coefficient swell is a well-known difficulty with Buchberger‘s algorithm for computing Gröbner bases over the rational numbers. p-Adic and modular methods have been successful in limiting intermediate coefficient growth in other computations, and in particular in the Euclidian algorithm for computing the greatest common divisor (GCD) of polynomials in one variable. In this paper we present two modular algorithms for computing a Gröbner basis for an ideal in Q[x1, ... ,xy] which extend the modular GCD algorithms. These algorithms improve upon previously proposed modular techniques for computing Gröbner bases in that we test primes before lifting, and also provide an algorithm for checking the result for correctness. A complete characterization of unlucky primes is also given. Finally, we give some preliminary timings which indicate that these modular algorithms can provide considerable time improvements in examples where intermediate coefficient growth is a problem.
Length17
ISSN0747-7171
File
LanguageEnglish
JournalJournal of Symbolic Computation
Volume35
Number4
Pages403-419
PublisherAcademic Press, Inc.
AddressDuluth, MN, USA
Year2003
MonthApril
Edition0
Translation No
Refereed No
Organization Texas A&M University
Webmaster