×

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

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.

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Adams, W.W.; Loustaunau, P., An introduction to Gröbner bases, (1994), American Mathematical Society Providence, RI · Zbl 0811.13020
[2] Arnold, E.A., 2000. Computing Gröbner Bases with Hilbert Lucky Primes, Ph.D. Dissertation, University of Maryland, College Park, MD
[3] Borosh, I., Exact solutions of linear equations with rational coefficients by congruence techniques, Mathematics of computation, 20, 107-112, (1966) · Zbl 0137.11002
[4] Buchberger, B., 1979. A criterion for detecting unnecessary reductions in the construction of Gröbner-bases, Lecture Notes in Computer Science, vol. 72, pp. 23-21
[5] Buchberger, B., 1985. Gröbner-bases: an algorithmic method in polynomial ideal theory, In: Multidimensional Systems Theory, pp. 184-232
[6] Capani, A., Niesi, G., Robbiano, L., 2001. CoCoA, a system for doing Computations in Commutatative Algebra. Available via anonymous ftp from cocoa.dima.unige.it, ed. 4.1
[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
[13] Grayson, D., Stillman, M., 2000. Macaulay 2, Available via anonymous ftp from ftp.math.uiuc.edu, ed. 0.8.60
[14] Möller, H.M., Mora, F., 1984. Upper and lower bounds for the degree of Groebner bases, Eurosam ’84, Lecture Notes in Computer Science, vol. 174, pp. 172-183
[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
[17] Traverso, C., 1988. Gröbner Trace Algorithms, Proceedings ISSAC ‘88, Lecture Notes in Computer Science, vol. 358, pp. 125-138
[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.