×
Arnold, Elizabeth A.

Modular algorithms for computing Gröbner bases. (English) Zbl 1046.13018

J. Symb. Comput. 35, No. 4, 403-419 (2003).
Summary: Intermediate 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 the author presents two modular algorithms for computing a Gröbner basis for an ideal in \(\mathbb{Q}[x_1, \dots,x_\nu]\) which extend the modular GCD algorithms. These algorithms improve upon previously proposed modular techniques for computing Gröbner bases in that the author tests primes before lifting, and also provides an algorithm for checking the result for correctness. A complete characterization of unlucky primes is also given. Finally, the author gives some preliminary timings which indicate that these modular algorithms can provide considerable time improvements in examples where intermediate coefficient growth is a problem.

Cited in 5 Reviews
Cited in 42 Documents

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation

Keywords:

modular algorithms; unlucky primes; time improvements

Software:

modstd.lib; modwalk; Macaulay2; CoCoA; ffmodstd
PDF BibTeX XML Cite
\textit{E. A. Arnold}, J. Symb. Comput. 35, No. 4, 403--419 (2003; Zbl 1046.13018)
Full Text: DOI

References:

[1] Adams, W. W.; Loustaunau, P., An Introduction to Gröbner Bases (1994), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0811.13020
[3] Borosh, I., Exact solutions of linear equations with rational coefficients by congruence techniques, Mathematics of Computation, 20, 107-112 (1966) · Zbl 0137.11002
[7] Davenport, J. H.; Siret, Y.; Tournier, E., Computer Algebra: Systems and algorithms for algebraic computation (1988), Academic Press · Zbl 0679.68058
[8] Ebert, G. L., Some comments on the modular approach to Gröbner-bases, ACM SIGSAM Bulletin, 17, 28-32 (1983) · Zbl 0527.13001
[9] Eisenbud, D., Commutative Algebra with a view toward Algebraic Geometry (1995), Springer-Verlag · Zbl 0819.13001
[10] Gebauer, R.; Möller, H. M., On an installation of Buchberger’s algorithm, Journal of Symbolic Computation, 6, 275-286 (1988) · Zbl 0675.13013
[11] Gräbe, H., On lucky primes, Journal of Symbolic Computation, 15, 199-209 (1994) · Zbl 0787.13016
[12] Kornerup, P.; Gregory, R., Mapping integers and Hensel codes onto Farey fractions, Bit, 23, 9-20 (1983) · Zbl 0521.10007
[15] Pauer, F., On lucky ideals for Gröbner basis computations, Journal of Symbolic Computation, 14, 471-482 (1992) · Zbl 0776.13014
[16] Sasaki, T.; Takeshima, T., A modular method for Gröbner-basis construction over \(Q\) and solving system of algebraic equations, Journal of Information Processing, 12, 371-379 (1989) · Zbl 0757.13012
[18] Traverso, C., Hilbert functions and the Buchberger’s algorithm, Journal of Symbolic Computation, 22, 355-376 (1997)
[19] Winkler, F., A \(p\)-adic approach to the computation of Gröbner bases, Journal of Symbolic Computation, 6, 287-304 (1987) · Zbl 0669.13009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.