×

zbMATH — the first resource for mathematics

A new efficient algorithm for computing Gröbner bases \((F_4)\). (English) Zbl 0930.68174
The first part of the paper contains the description and theoretical foundations of a new, implementation oriented algorithmic method for the computation of Gröbner bases of polynomial ideals.
Degree-truncated Gröbner basis computations, sparse linear algebra routines and parallel computing are used in order to speed up the classical Buchberger algorithm (in the past these tools were only applied to the theoretical worst case complexity analysis of this algorithm).
The new procedure combines term rewriting with linear algebra. Its main feature consists in the simultaneous reduction of several polynomials modulo a precomputed list of them. This is done in a parallel way, using sparse linear algebra routines. This aspect of massive parallel computation distinguishes the new procedure from the classical Buchberger algorithm.
The paper ends with a comparison of the implemented version of the new algorithm (the program FGb) with its forerunner Gb and some of its competitors. The author claims that the program FGb behaves almost optimally with respect to time complexity. Time seems to be almost proportional to the (objective) output size.

MSC:
68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
Software:
Maple; IML++; Magma; FGb; Gb; symrcm
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] F.L. Alvarado, The Sparse Matrix Manipulation System User and Reference Manual, University of Wisconsin, Wisconsin, May 1993.
[2] F.L. Alvarado, A. Pothen, R. Schreiber, Highly parallel sparse triangular solution, Preprint. · Zbl 0794.65019
[3] G. Attardi, C. Traverso, Homogeneous parallel algorithm, J. Symbolic Comput. (1996). · Zbl 0865.68059
[4] T. Becker, V. Weispfenning, Groebner Bases, a Computationnal Approach to Commutative Algebra, Graduate Texts in Mathematics, Springer, Berlin, 1993. · Zbl 0772.13010
[5] D. Bini, V. Pan, Polynomial and Matrix Computations, Progress in Theoretical Computer Science, vol. 1, Fundamental Algorithms, Birkäuser, Basel, 1994.
[6] B. Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, PhD thesis, Innsbruck, 1965. · Zbl 1245.13020
[7] B. Buchberger, An algorithmical criterion for the solvability of algebraic systems, Aequationes Mathematicae 4 (3) (1970) 374-383 (in German).
[8] B.A. Buchberger, Criterion for detecting unnecessary reductions in the construction of Gröbner basis, in: Proc. EUROSAM 79, Lecture Notes in Computer Science, vol. 72, Springer, Berlin, 1979, pp. 3-21.
[9] B. Buchberger, Gröbner bases: an algorithmic method in polynomial ideal theory, in: Reidel (Ed.), Recent Trends in Multidimensional System Theory, Bose, 1985.
[10] J. Cannon, The Magma Computational Algebra System 2.20-7, February 1998.
[11] B. Char, K. Geddes, G. Gonnet, B. Leong, M. Monagan, S. Watt, Maple V Library Reference Manual, Springer, Berlin, 1991, Third Printing, 1993.
[12] T. Davis, Users’ Guide for the Unsymmetric-pattern MultiFrontal Package, Computer and Information Sciences Department, University of Florida, January 1995. Technical Report TR-95-004.
[13] Dixon, J.D., Exact solution of linear equations using p-adic expansions, Numer. math., 40, 137-141, (1982) · Zbl 0492.65016
[14] J. Dongarra, A. Lumsdaine, X. Niu, R. Pozo, K. Remington, A sparse matrix library in C++ for high performance architectures, Preprint.
[15] Duff, I.S.; Reid, J.K., The multifrontal solution of unsymmetric sets of linear equations, SIAM J. sci. statist. comput., 5, 3, 633-641, (1984) · Zbl 0557.65017
[16] J.C. Faugère, Benchmarks for polynomial solvers, Available on the WEB
[17] J.C. Faugère, On line documentation of Gb, Available on the WEB http://posso.lip6.fr/^{∼}jcf.
[18] J.C. Faugère, Computing Gröbner Basis without reduction to zero (F5), Technical report, LIP6 report, 1998, in preparation.
[19] J.C. Faugère, F. Moreau de Saint-Martin, F. Rouillier, Design of nonseparable bidimensional wavelets and filter banks using Gröbner bases techniques, IEEE SP Trans. Signal Processing 46 (4) 1998. Special Issue on Theory and Applications of Filter Banks and Wavelets.
[20] A. Fronville, Singularité résiduelle et Problème du centre, PhD thesis, Université Paris 6, Décember 1996.
[21] R. Gebauer, H.M. Möller, On an installation of Buchberger’s algorithm, J. Symbolic Comput. 6 (2,3) (1988) 275-286. · Zbl 0675.13013
[22] A. George, J.W.H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, Englewood Cliffs, NJ, 1981. · Zbl 0516.65010
[23] A. George, J.R. Gilbert, J.W.H. Liu, Graph Theory and Sparse Matrix Computation, Springer, New York, 1993.
[24] V.P. Gerdt, Involutive Polynomial Bases, in: PoSSo on Software Paris, F, 1995.
[25] A. Giovini, T. Mora, G. Niesi, L. Robbiano, C. Traverso, One sugar cube, please, or Selection strategies in the Buchberger Algorithm, in: S.M. Watt (Ed.), Proc. 1991 Internat. Symp. on Symbolic and Algebraic Computation, ISSAC’ 91, ACM, New York, 1991. · Zbl 0933.68161
[26] D. Grayson, M. Stillman, Macaulay 2 User Manual, 1997.
[27] G.-M. Greuel, G. Pfister, H. Schoenemann, SINGULAR 1.0.2, July 1997.
[28] M.T. Heath, P. Raghavan, Distributed solution of sparse linear systems, Preprint. · Zbl 1067.68789
[29] E. Kaltofen, On Wiedemann’s method of solving sparse linear systems, Lecture Notes in Computer Science, vol. 539, Springer, Berlin, 1991, pp. 29-38, AAECC-9. · Zbl 0778.65034
[30] D.E. Knuth, The Art of Computer Programming, vol. 2, 2 ed., Addison-Wesley, Reading, MA, 1981. · Zbl 0477.65002
[31] B.A. LaMacchia, A.M. Odlyzko, Solving large sparse linear systems over finite fields, Lecture Notes in Computer Science, vol. 537, Springer, Berlin, 1991. Advances in Cryptology, CRYPTO’90. · Zbl 0786.65028
[32] D. Lazard, Systems of algebraic equations, in: EUROSAM 79, 1979, 88-94.
[33] D. Lazard, Resolution des systemes d’equations algebriques, Theoret. Comput. Sci. 15 (1981) 77-110. · Zbl 0459.68013
[34] D. Lazard, Gaussian elimination and resolution of systems of algebraic equations, in: Proc. EUROCAL 83, Lecture Notes in Computer Science, vol. 162, Springer, Berlin, 1983, pp. 146-157.
[35] H. Lombardi, Un nouvel algorithme de calcul d’une Base de Gröbner, Technical report, Equipe de Mathématiques de Besançon, Janvier 1998.
[36] A.M. Mandache, The Gröbner basis algorithm and subresultant theory, in: Proc. ISSAC’94, Oxford, UK, ACM, New York, 1994, pp. 123-128. · Zbl 0917.13009
[37] A.M. Mandache, A note on the relationship between involutive bases and Gröbner bases, Mega 96, 1996.
[38] J.L. Massey, Shift-register synthesis and bch decoding, IEEE Trans. Inform. Theory 15 (1) (1969) 122-127. · Zbl 0167.18101
[39] P. Montgomery, A block Lanczos algorithm for finding dependencies over GF(2), Lecture Notes in Computer Science, Springer, Berlin, 1995, pp. 106-120. · Zbl 0973.11520
[40] S.R. Petrick (Ed.), Proc. 2nd Symp. Symbolic and Algebraic Manipulation, ACM Press, New York, 1971.
[41] B.W. Peyton, A. Pothen, X. Yuan, Partitioning a choral graph into transitive subgraphs for parallel sparse triangular solution, Preprint. · Zbl 0786.05081
[42] J.K. Reid, Large Sparse Sets of Linear Equations, Academic Press, London, 1971.
[43] D. Rose, R.A. Willoughby, Sparse Matrices and their Applications, Plenum Press, New York, 1972.
[44] M. Stillman, D. Bayer, Macaulay User Manual, 1989, Available via anonymous ftp on
[45] T. Takeshima, Risa/Asir. Fujitsu Laboratories Limited, 1996, Version 950831, Available from ftp://endeavor.fujitsu.co.jp/pub/isis/asir.
[46] C. Traverso, Groebner Engine. Rel. 2.0, 1997,
[47] A.F. Van der Stappen, R.H. Bisseling, J.G.G. Van de Vorst, Parallel sparse LU decomposition on a mesh network of transputers, SIAM J. Matrix Anal. Appl. 14 (3) (1993) 853-879. · Zbl 0783.65022
[48] D. Wiedemann, Solving sparse linear equation over finite fields, IEEE Trans. Inform. Theory IT-32 (1) (1986) 54-62. · Zbl 0607.65015
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.