×
Winkler, Franz

A p-adic approach to the computation of Gröbner bases. (English) Zbl 0669.13009

J. Symb. Comput. 6, No. 2-3, 287-304 (1988).
To deal with the problem of coefficient growth in the computation of Gröbner bases of polynomial ideals over the rational number field \({\mathbb{Q}}\) the paper presents a lifting algorithm that computes a p-adic approximation to the normalized reduced Gröbner basis for the ideal generated by a finite set of polynomials F in \({\mathbb{Q}}[x_ 1,...,x_ v]\). For the lucky prime p for F (it is shown that almost all primes are lucky) a normalized reduced Gröbner basis for F modulo p is computed and then lifted to the desired result.
Reviewer: E.Ederle

Cited in 1 Review
Cited in 16 Documents

MSC:

13F20 Polynomial rings and ideals; rings of integer-valued polynomials
68W30 Symbolic computation and algebraic computation
13-04 Software, source code, etc. for problems pertaining to commutative algebra

Keywords:

coefficient growth; computation of Gröbner bases of polynomial ideals; p-adic approximation

Software:

Algorithm 628
PDF BibTeX XML Cite
\textit{F. Winkler}, J. Symb. Comput. 6, No. 2--3, 287--304 (1988; Zbl 0669.13009)
Full Text: DOI

References:

[1] Brown, W. S., On Euclid’s algorithm and the computation of polynomial greatest common divisors, JACM, 18, 4, 478-504 (1971) · Zbl 0226.65040
[2] Buchberger, B., Some properties of Gröbner bases for polynomial ideals, ACM SIGSAM Bull., 10, 4, 19-24 (1976)
[3] Buchberger, B., A criterion for detecting unnecessary reductions in the construction of Gröbner-Bases, (Ng, E. W., Proc. EUROSAM 79. Proc. EUROSAM 79, Marseille, 1979. Proc. EUROSAM 79. Proc. EUROSAM 79, Marseille, 1979, LNCS, 72 (1979), Springer-Verlag: Springer-Verlag Heidelberg), 3-21 · Zbl 0417.68029
[4] Buchberger, B., Gröbner bases: An algorithmic method in polynomial ideal theory, (Bose, N. K., Multidimensional Systems Theory (1985), D. Reidel Publ. Comp.), 184-232 · Zbl 0587.13009
[5] Ebert, G. L., Some comments on the modular approach to Gröbner-bases, ACM SIGSAM Bull, 17, 2, 28-32 (1983) · Zbl 0527.13001
[6] Furukawa, A.; Sasaki, T.; Kobayashi, H., Gröbner basis of a module over \(K[x_1\), …, \(x_n]\) and polynomial solutions of a system of linear equations, (Char, B. W., Proc. SYMSAC’86. ACM 1986 (1986)), 222-224
[7] Galligo, A., Théorème de division et stabilité en géométrie analytique locale, Ann. Inst. Fourier, 29, 107-184 (1979) · Zbl 0412.32011
[8] Hilbert, D., Über die Theorie der algebraischen Formen, Math. Annalen, 36, 473-534 (1890) · JFM 22.0133.01
[9] Kornerup, P.; Gregory, R. T., Mapping integers and Hensel codes onto Farey fractions, BIT, 23, 9-20 (1983) · Zbl 0521.10007
[10] Lauer, M., Computing by homomorphic images, (Buchberger, B.; etal., Computer Algebra—Symbolic and Algebraic Computation (1983), Springer-Verlag: Springer-Verlag Heidelberg) · Zbl 0513.68035
[11] Malle, G.; Trinks, W., (Zur Behandlung algebraischer Gleichungssysteme mit dem Computer (1984), Mathematisches Institut, Universität Karlsruhe), unpublished manuscript
[12] Matzat, B. H.; Zeh-Marschke, A., Realisierung der Mathieugruppen \(M_{11}\) und \(M_{12}\) als Galoisgruppen über Q, J. Number Theory, 23, 195-202 (1986) · Zbl 0598.12007
[13] Miola, A.; Yun, D. Y.Y., The computational aspects of Hensel-type univariate greatest common divisor algorithms, (Jenks, R. D., Proc. EUROSAM’74. SIGSAM Bulletin, 8 (1974)), 46-54, 3
[14] Möller, H. M.; Mora, F., New constructive methods in classical ideal theory, J. of Algebra, 100, 138-178 (1986) · Zbl 0621.13007
[15] Moses, J.; Yun, D. Y.Y., The EZGCD algorithm, (Proc. ACM Annual Conference. Proc. ACM Annual Conference, Atlanta (1973)), 159-166
[16] Musser, D. R., Multivariate polynomial factorization, JACM, 22, 291-308 (1975) · Zbl 0301.65029
[17] Trinks, W., On improving approximate results of Buchberger’s algorithm by Newton’s method, SIGSAM Bull., 18, 3, 7-11 (1984) · Zbl 0563.12024
[18] van der Waerden, B. L., (Algebra II (1967), Springer-Verlag: Springer-Verlag Heidelberg) · Zbl 0192.33002
[19] Wang, P. S.H., An improved multivariate polynomial factorization algorithm, Math. Comp., 32, 1215-1231 (1978) · Zbl 0388.10035
[20] Wang, P. S.H.; Rothschild, L. P., Factoring multivariate polynomials over the integers, Math. Comp., 29, 935-950 (1975) · Zbl 0311.10052
[21] Winkler, F., The Church-Rosser Property in Computer Algebra and Special Theorem Proving: An Investigation of Critical-Pair/Completion Algorithms, (Dissertation (1984), Institut für Mathematik, J. Kepler Universität: Institut für Mathematik, J. Kepler Universität Linz) · Zbl 0562.68023
[22] Winkler, F., Solution of Equations I: Polynomial Ideals and Gröbner Bases. Lecture notes, Short Course “Symbolic and Algebraic Computation”, (Jenks, R. D., Conf. on “Computers & Mathematics”. Conf. on “Computers & Mathematics”, Stanford University, 1986. Conf. on “Computers & Mathematics”. Conf. on “Computers & Mathematics”, Stanford University, 1986, Series in Computational Mathematics (1986), Springer-Verlag)
[23] Winkler, F., \(p\)-adic methods for the computation of Gröbner bases, extended abstract, (EUROCAL’87. EUROCAL’87, Leipzig, GDR (1987))
[24] Winkler, F., A recursive method for computing a Gröbner basis of a module in \(K[x_1\), …, \(x_v]^r\), A.A.E.C.C.-5, Menorca, Spain (1987)
[25] Winkler, F.; Buchberger, B.; Lichtenberger, F.; Rolletschek, H., Algorithm 628—An algorithm for constructing canonical bases of polynomial ideals, ACM Trans. on Math. Software, 11, 66-78 (1985) · Zbl 0575.68047
[26] Zassenhaus, H., On Hensel factorization, I, J. Number Theory, 1, 291-311 (1969) · Zbl 0188.33703
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.