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
[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., (Solving Polynomial Equations. Solving Polynomial Equations, Algorithms and Computation in Mathematics, vol. 14 (2005), Springer) · Zbl 1061.12001
[6] Decker, W.; Greuel, G.-M.; Pfister, G., (Primary Decomposition: Algorithms and Comparisons. Primary Decomposition: Algorithms and Comparisons, Algorithmic Algebra and Number Theory (1998), Springer), 187-220 · Zbl 0932.13019
[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
[13] Greuel, G.-M.; Pfister, G., A Singular 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, (Zap. Nauchn. Sem. POMI, vol. 258 (1999), POMI: POMI St. Petersburg), 292-317
[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 \(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
[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.