Parallelization of modular algorithms. (English) Zbl 1229.13002

The title is a bit of an understatement, the results are also interesting without parallelisation. First, a modular algorithm for the computation of Gröbner bases is given. Its correctness was shown in [E. A. Arnold, “Modular algorithms for computing Gröbner bases”, J. Symb. Comput. 35, No. 4, 403-419 (2003; Zbl 1046.13018)] for the homegeneous case and in [G.-M. Greuel, G. Pfister, A Singular Introduction to Commutative Algebra. Berlin: Springer. (2007; Zbl 1133.13001)] for local orderings; here the case of global orderings is treated. Also, the paper contains a modular algorithm for the computation of associated primes of zero-dimensional ideals.


13-04 Software, source code, etc. for problems pertaining to commutative algebra
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
65Y05 Parallel numerical computation
65Y04 Numerical algorithms for computer arithmetic, etc.
68W10 Parallel algorithms in computer science
68W30 Symbolic computation and algebraic computation
Full Text: DOI arXiv


[1] Arnold, E.A., Modular algorithms for computing Gröbner bases, Journal of symbolic computation, 35, 403-419, (2003) · Zbl 1046.13018
[2] Björck, G.; Fröberg, G., A faster way to count the solution of inhomogeneous systems of algebraic equations, with applications to cyclic \(n\)-roots, Journal of symbolic computation, 12, 329-336, (1991) · Zbl 0751.12001
[3] Bini, D., Mourrain, B., Polynomial test suite. Frisco project (LTR 21.024). http://www-sop.inria.fr/saga/POL/ (2010).
[4] Becker, E.; Wörmann, T., Radical computations of zero-dimensional ideals and real root counting, Mathematics and computers in simulation, 42, 561-569, (1996) · Zbl 1037.68540
[5] Dickenstein, A.; Emiris, I.Z., ()
[6] Decker, W.; Greuel, G.-M.; Pfister, G., (), 187-220
[7] Decker, W., Greuel, G.-M., Pfister, G., Schönemann, H., Singular 3-1-1 — A computer algebra system for polynomial computations. http://www.singular.uni-kl.de (2010).
[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.; Huneke, C.; Vasconcelos, W., Direct methods for primary decomposition, Inventiones mathematicae, 110, 207-235, (1992) · Zbl 0770.13018
[10] Faugère, J.C.; Gianni, P.; Lazard, D.; Mora, T., Efficient computation of zero-dimensional Gröbner bases by change of ordering, Journal of symbolic computation, 16, 329-344, (1993) · Zbl 0805.13007
[11] Gräbe, H.-G., On lucky primes, Journal of symbolic computation, 15, 199-209, (1993) · Zbl 0787.13016
[12] Gräbe, H.-G., The SymbolicData Project — Tools and Data for Testing Computer Algebra Software. http://www.symbolicdata.org (2010).
[13] Greuel, G.-M.; Pfister, G., A {\scsingular} introduction to commutative algebra, (2007), Springer
[14] Gianni, P.; Trager, B.; Zacharias, G., Gröbner bases and primary decomposition of polynomial ideals, Journal of symbolic computation, 6, 149-167, (1988) · Zbl 0667.13008
[15] Kornerup, P.; Gregory, R.T., Mapping integers and hensel codes onto Farey fractions, BIT numerical mathematics, 23, 1, 9-20, (1983) · Zbl 0521.10007
[16] Kotsireas, I.; Lazard, D., Central configurations of the 5-body problem with equal masses in three-dimensional space representation theory, dynamical systems, combinatorial and algorithmic methods. part IV, (), 292-317
[17] Krick, T., Logar, A., 1991. An algorithm for the computation of the radical of an ideal in the ring of polynomials. In: Applied Algebra, Algebraic Algorithms and Error Correcting Codes, 9th International Symposium AAECC-9, Springer. Lecture Notes in Computer Science, vol. 539, pp. 195-205. · Zbl 0823.13018
[18] Monico, C., Computing the primary decomposition of zero-dimensional ideals, Journal of symbolic computation, 34, 451-459, (2002) · Zbl 1010.13017
[19] Pauer, F., On lucky ideals for Gröbner bases computations, Journal of symbolic computation, 14, 471-482, (1992) · Zbl 0776.13014
[20] Pfister, G., On modular computation of standard basis, Analele stiintifice ale universitatii ovidius, mathematical series XV (1), 129-137, (2007) · Zbl 1199.13032
[21] Sasaki, T.; Takeshima, T., A modular method for Gröbner-basis construction over \(\mathbb{Q}\) and solving system of algebraic equations, Journal of information processing, 12, 371-379, (1989) · Zbl 0757.13012
[22] Shimoyama, T.; Yokoyama, K., Localization and primary decomposition of polynomial ideals, Journal of symbolic computation, 22, 247-277, (1996) · Zbl 0874.13022
[23] Traverso, C., 1989. Gröbner trace algorithms. In: Symbolic and Algebraic Computation, International Symposium ISSAC’88, Springer Lecture Notes in Computer Science, vol. 358, pp. 125-138.
[24] Wang, P.S.; Guy, M.J.T.; Davenport, J.H., \(P\)-adic reconstruction of rational numbers, ACM SIGSAM bulletin, 16, 2-3, (1982) · Zbl 0489.68032
[25] 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.