On the complexity of the F5 Gröbner basis algorithm. (September 2015)

• Record Type: Journal Article
• Authors: Bardet, Magali; Faugère, Jean-Charles; Salvy, Bruno
• Is Part Of: Journal of symbolic computation. Volume 70(2015)
• Page Start: 49
• Page End: 70
• Publication Date: 2015-09
• Subjects: Gröbner bases -- F5 algorithm -- Complexity -- Regular sequences -- Noether position; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2014.09.025
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We study the complexity of Gröbner bases computation, in particular in the generic situation where the variables are in simultaneous Noether position with respect to the system. We give a bound on the number of polynomials of degree d in a Gröbner basis computed by Faugère's F 5 algorithm (2002) in this generic case for the grevlex ordering (which is also a bound on the number of polynomials for a reduced Gröbner basis, independently of the algorithm used). Next, we analyse more precisely the structure of the polynomials in the Gröbner bases with signatures that F 5 computes and use it to bound the complexity of the algorithm. Our estimates show that the version of F 5 we analyse, which uses only standard Gaussian elimination techniques, outperforms row reduction of the Macaulay matrix with the best known algorithms for moderate degrees, and even for degrees up to the thousands if Strassen's multiplication is used. The degree being fixed, the factor of improvement grows exponentially with the number of variables.