zbMATH — the first resource for mathematics

Efficient Gröbner bases computation over principal ideal rings. (English) Zbl 1451.13078
In the paper under review, the authors present new techniques for improving the computation of strong Gröbner bases over a principal ideal ring. Let \(R\) be a principal ideal ring; i.e. a unital commutative ring such that every ideal of \(R\) is principal. Let \(P=R[x_1,\ldots ,x_n]\) be the polynomial ring in \(n\) variables over \(R\). Let us fix a monomial ordering \(\prec\) on \(P\). For any polynomial \(f\in P\), we can define the leading term of \(f\), denoted by \(lt(f)\), as the greatest term (including the coefficient) appearing in \(f\). For a given ideal \(I\subset R\), a finite set \(G\subset I\) is called a strong Gröbner basis of \(I\) if for any polynomial \(0\ne f\in I\), there exists \(g\in G\) such that \(lt(f)\mid lt(g)\). In order to compute strong Gröbner bases, in addition to S-polynomials proposed by Buchberger, on needs to consider GCD-polynomials and A-polynomials. Based on this discussion, we can describe a variant of Buchberger’s algorithm to construct strong Gröbner bases.
To compute a strong Gröbner basis for an ideal of \(I\subset P\), the authors apply a kind of modular method by passing to quotient rings. More precisely, they choose an element \(n\in R\), construct a Gröbner basis of the ideal \(\bar{I}\subset (R/nR)[x]\) and from this basis a Gröbner basis for the ideal \(I\) is reconstructed.
This algorithm has been implemented in the Julia package for the special case of \(R=\mathbb{Z}\). Running standard benchmarks shows the efficiency of the algorithm.
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation
PDF BibTeX Cite
Full Text: DOI
[1] Adams, W. W.; Loustaunau, P., An Introduction to Gröbner Bases, Graduate Studies in Mathematics (1994), AMS · Zbl 0803.13015
[2] Arnold, E. A., Modular algorithms for computing Gröbner bases, J. Symb. Comput., 35, 4, 403-419 (2003) · Zbl 1046.13018
[3] Bach, E.; Driscoll, J.; Shallit, J., Factor refinement, J. Algorithms, 15, 2, 199-222 (1993) · Zbl 0784.11058
[4] Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system. I. The user language, J. Symb. Comput., 24, 3-4, 235-265 (1997) · Zbl 0898.68039
[5] Buchberger, B., Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal (1965), University of Innsbruck, Ph.D. thesis · Zbl 1245.13020
[6] Buchberger, B., Gröbner-Bases: An Algorithmic Method in Polynomial Ideal Theory (1985), Reidel Publishing Company: Reidel Publishing Company Dordrecht - Boston - Lancaster · Zbl 0587.13009
[7] Buchberger, B., An algorithm for finding the basis elements of the residue class ring of zero dimensional polynomial ideal, J. Symb. Comput., 41, 3-4, 475-511 (2006) · Zbl 1158.01307
[8] Decker, W.; Greuel, G.-M.; Pfister, G.; Schönemann, H., Singular 4-1-2 — a computer algebra system for polynomial computations (2019)
[9] Eder, C. (2019), gb
[10] Eder, C.; Hofmann, T. (2019), gb
[11] Eder, C.; Pfister, G.; Popescu, A., On signature-based Gröbner bases over Euclidean rings, (ISSAC 2017: Proceedings of the 2011 International Symposium on Symbolic and Algebraic Computation (2017)), 141-148 · Zbl 1458.13032
[12] Eder, C.; Pfister, G.; Popescu, A., Standard bases over Euclidean domains (2018)
[13] Faugère, J.-C., A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra, 139, 1-3, 61-88 (June 1999)
[14] Fieker, C.; Hart, W.; Hofmann, T.; Johansson, F., Nemo/Hecke: computer algebra and number theory packages for the Julia programming language, (ISSAC’17—Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation (2017), ACM: ACM New York), 157-164 · Zbl 1457.68325
[15] Fieker, C.; Hofmann, T., Computing in quotients of rings of integers, LMS J. Comput. Math., 17, suppl. A, 349-365 (2014) · Zbl 1369.11104
[16] Francis, M.; Verron, T., Signature-based Möller’s algorithm for strong Gröbner bases over PIDs (2019), CoRR
[17] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2003), Cambridge University Press: Cambridge University Press Cambridge, England · Zbl 1055.68168
[18] Grauert, H., Über die Deformation isolierter Singularitäten analytischer Mengen, Invent. Math., 15, 3, 171-198 (1972) · Zbl 0237.32011
[19] Hashemi, A.; Alvandi, P., Applying Buchberger’s criteria for computing Gröbner bases over finite-chain rings, J. Algebra Appl., 12, 7, Article 1350034 pp. (2013) · Zbl 1281.13017
[20] Hironaka, H., Resolution of singularities of an algebraic variety over a field of characteristic zero: I, Ann. Math., 79, 1, 109-203 (1964) · Zbl 0122.38603
[21] Hironaka, H., Resolution of singularities of an algebraic variety over a field of characteristic zero: II, Ann. Math., 79, 2, 205-326 (1964) · Zbl 1420.14031
[22] Kandri-Rody, A.; Kapur, D., Algorithms for computing Gröbner bases of polynomial ideals over various Euclidean rings, (Fitch, J., EUROSAM 84 (1984), Springer: Springer Berlin, Heidelberg), 195-206 · Zbl 0564.13001
[23] Kandri-Rody, A.; Kapur, D., Computing a Gröbner basis of a polynomial ideal over a Euclidean domain, J. Symb. Comput., 6, 1, 37-57 (1988) · Zbl 0658.13016
[24] Kapur, D.; Cai, Y., An algorithm for computing a Gröbner basis of a polynomial ideal over a ring with zero divisors, Math. Comput. Sci., 2, 601-634 (2009) · Zbl 1205.13032
[25] Lichtblau, D., Effective computation of strong Gröbner bases over Euclidean domains, Ill. J. Math., 56, 1, 177-194 (2012) · Zbl 1275.13021
[26] Möller, H. M., On the construction of Gröbner bases using syzygies, J. Symb. Comput., 6, 2, 345-359 (1988) · Zbl 0695.13003
[27] Norton, G. H.; Sălăgean, A., Strong Gröbner bases and cyclic codes over a finite-chain ring, (International Workshop on Coding and Cryptography. International Workshop on Coding and Cryptography, Paris, 2001. International Workshop on Coding and Cryptography. International Workshop on Coding and Cryptography, Paris, 2001, Electron. Notes Discrete Math., vol. 6 (2001), Elsevier Sci. B. V.: Elsevier Sci. B. V. Amsterdam), 11
[28] Norton, G. H.; Sǎlǎgean, A., Strong Gröbner bases for polynomials over a principal ideal ring, Bull. Aust. Math. Soc., 64, 3, 505-528 (2001) · Zbl 1046.13019
[29] Pauer, F., On lucky ideals for Gröbner basis computations, J. Symb. Comput., 14, 5, 471-482 (1992) · Zbl 0776.13014
[30] Pauer, F., Gröbner bases with coefficients in rings, J. Symb. Comput., 42, 11, 1003-1011 (2007) · Zbl 1127.13024
[31] Pauer, F.; Pfeifhofer, M., The theory of Gröbner bases, Enseign. Math. (2), 34, 3-4, 215-232 (1988) · Zbl 0702.13019
[32] Popescu, A., Signature Standard Bases over Principal Ideal Rings (2016), Technische Universität Kaiserslautern, Ph.D. thesis
[33] Storjohann, A.; Mulders, T., Fast algorithms for linear algebra modulo N, (Algorithms—ESA ’98. Algorithms—ESA ’98, Venice. Algorithms—ESA ’98. Algorithms—ESA ’98, Venice, Lecture Notes in Comput. Sci., vol. 1461 (1998), Springer: Springer Berlin), 139-150 · Zbl 0929.65019
[34] Trinks, W., Über B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu lösen, J. Number Theory, 10, 4, 475-488 (1978) · Zbl 0404.13004
[35] Wienand, O., Algorithms for Symbolic Computation and Their Applications - Standard Bases over Rings and Rank Tests in Statistics (2011), Technische Universität Kaiserslautern, Ph.D. thesis
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.