Generalization of the F5 algorithm for calculating Gröbner bases for polynomial ideals

This survey paper presents general approach to the well-known F5 algorithm for calculating Gröbner bases, which was created by Faugère in 2002.     

On the homogeneous Gröbner basis for tensors

Algorithmic methods of commutative algebra based on the involutive and Gröbner bases technique are efficient means for completion of equations governing dynamical systems to involution. At the same time, when working with high-dimensional tensor quantities, direct use of standard functions for calculating Gröbner bases, which are built in computer algebra systems Maple and Mathematica, requires much memory. However, being multilinear forms, tensors admit special grading that makes it possible to classify polynomials in terms of their degree of homogeneity. With regard to this feature, we propose to use a special homogeneous Gröbner basis, which allows us to avoid difficulties associated with large amount of computation. Such a basis is constructed step by step, as the degree of the polynomial grows. As an example, an algorithm for constructing the homogeneous basis in a finite-dimensional Hamiltonian system with many polynomial constraints (the so-called Yang-Mills mechanics) is presented.     

Efficiency estimate for distributed computation of Gröbner bases and involutive bases

Several years ago, we presented a program complex for parallel computation of Gröbner bases that works on computers with shared-memory architecture. Unfortunately, the number of the processors that we can use is small (from 2 to 16) because of hardware constraints. This paper presents a program for distributed computation of bases that relies on the same principles but works in a network consisting of heterogeneous machines. The effectiveness of such an approach is estimated from the standpoint of the processor capacity usage and the required network bandwidth, and methods optimizing usage of these resources are specified.     

On the Stability of Gröbner Bases Under Specializations

LetRbe a Noetherian commutative ring with identity,Ka field and π a ring homomorphism fromRtoK. We investigate for which ideals inR[x₁,…,x_n] and admissible orders the formation of leading monomial ideals commutes with the homomorphism π.     

Lower bounds for the polynomial calculus and the Gröbner basis algorithm

Razborov (1996) recently proved that polynomial calculus proofs of the pigeonhole principle must have degree at least ⌈n/2⌉ + 1 over any field. We present a simplified proof of the same result.?Furthermore, we show a matching upper bound on polynomial calculus proofs of the pigeonhole principle for any field of suficiently large characteristic, and an ⌈n/2⌉ + 1 lower bound for any subset sum problem over the field of reals.?We show that these degree lower bounds also translate into lower bounds on the number of monomials in any polynomial calculus proof, and hence on the running time of most implementations of the Gr?bner basis algorithm. Received: October 14, 1997.     

On the Gröbner basis triangularization of constraint equations in natural coordinates

Efficient dynamic simulation code is essential in many situations (including hardware-in-the-loop and model-predictive control applications), and highly beneficial in others (such as design optimization, sensitivity analysis, parameter identification, and controller tuning tasks). When the number of modeling coordinates n exceeds the degrees-of-freedom of the system f, as is often the case when closed kinematic chains are present, the governing dynamic equations consist of n second-order ordinary differential equations (ODEs) coupled with m=n?f algebraic constraint equations. This set of n+m index-3 differential-algebraic equations can be difficult to solve in an efficient yet accurate manner. Embedding (or generalized coordinate partitioning) can be used to obtain f ODEs (one for each independent acceleration), which are generally more amenable to numerical integration; however, the dependent positions are typically computed from the independent positions at each time step. Newton–Raphson iteration is often used for solving the position-level kinematics, but only provides solutions to within a specified tolerance, and can require several iterations to converge. In this work, Gröbner bases are used to obtain recursively solvable symbolic solutions for the dependent positions, which can then be evaluated to within machine precision using a fixed number of arithmetic operations. Natural coordinates are particularly attractive in this context, since the resulting constraint equations are maximally quadratic polynomials and are, therefore, easily triangularized. The proposed approach is suitable for use in an automated formulation procedure and, as demonstrated by three examples, is capable of generating highly efficient simulation code with minimal additional effort required at the formulation stage.     

Parallel modular computation of Gröbner and involutive bases

An overview of an algorithm and an efficient implementation of parallel computing of involutive and Gröbner bases with the help of modular operations is presented. Difficulties arising in modulo calculations and in the reconstruction of a basis with coefficients in ? by its modular images are considered; Some ways to overcome these difficulties are indicated.     

Enumeration of finite monomial orderings and combinatorics of universal Gröbner bases

The goal of this work is to analyze various classes of finite and total monomial orderings. The concept of monomial ordering plays the key role in the theory of Gröbner bases: every basis is determined by a certain ordering. At the same time, in order to define a Gröbner basis, it is not necessary to know ordering of all monomials. Instead, it is sufficient to know only a finite interval of the given ordering. We consider combinatorics of finite monomial orderings and its relationship with cells of a universal Gröbner basis. For every considered class of orderings (weakly admissible, convex, and admissible), an algorithm for enumerating finite orderings is discussed and combinatorial integer sequences are obtained. An algorithm for computing all minimal finite orderings for an arbitrary Gröbner basis that completely determine this basis is presented. The paper presents also an algorithm for computing an extended universal Gröbner basis for an arbitrary zero-dimensional ideal.     

Triangularizing kinematic constraint equations using Gröbner bases for real-time dynamic simulation

Real-time simulation is an essential component of hardware- and operator-in-the-loop applications, such as driving simulators, and can greatly facilitate the design, implementation, and testing of dynamic controllers. Such applications may involve multibody systems containing closed kinematic chains, which are most readily modeled using a set of redundant generalized coordinates. The governing dynamic equations for such systems are differential-algebraic in nature—that is, they consist of a set of ordinary differential equations coupled with a set of nonlinear algebraic constraint equations—and can be difficult to solve in real time. In this work, the equations of motion are formulated symbolically using linear graph theory. The embedding technique is applied to eliminate the Lagrange multipliers from the dynamic equations and obtain one ordinary differential equation for each independent acceleration. The theory of Gröbner bases is then used to triangularize the kinematic constraint equations, thereby producing a recursively solvable system for calculating the dependent generalized coordinates given values of the independent coordinates. The proposed approach can be used to generate computationally efficient simulation code that avoids the use of iteration, which makes it particularly suitable for real-time applications.     

Involutive method for computing Gröbner bases over $$ \mathbb{F}_2 $$

In this paper, an involutive algorithm for computation of Gröbner bases for polynomial ideals in a ring of polynomials in many variables over the finite field \(\mathbb{F}_2 \) with the values of variables belonging of \(\mathbb{F}_2 \) is considered. The algorithm uses Janet division and is specialized for a graded reverse lexicographical order of monomials. We compare efficiency of this algorithm and its implementation in C++ with that of the Buchberger algorithm, as well as with the algorithms of computation of Gröbner bases that are built in the computer algebra systems Singular and CoCoA and in the FGb library for Maple. For the sake of comparison, we took widely used examples of computation of Gröbner bases over ? and adapted them for \(\mathbb{F}_2 \). Polynomial systems over \(\mathbb{F}_2 \) with the values of variables in \(\mathbb{F}_2 \) are of interest, in particular, for modeling quantum computation and a number of cryptanalysis problems.     

An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals

In this paper, we present an optimal, exponential space algorithm for generating the reduced Gröbner basis of binomial ideals. We make use of the close relationship between commutative semigroups and pure difference binomial ideals. Based on an optimal algorithm for the uniform word problem in commutative semigroups, we first derive an exponential space algorithm for constructing the reduced Gröbner basis of pure difference binomial ideals. In addition to some applications to finitely presented commutative semigroups, this algorithm is then extended to an exponential space algorithm for generating the reduced Gröbner basis of binomial ideals over Q in general.     

Analogs of Gröbner Bases in Polynomial Rings over a Ring

In this paper we will define analogs of Gröbner bases forR-subalgebras and their ideals in a polynomial ringR[x₁,...,x_n] whereRis a noetherian integral domain with multiplicative identity and in which we can determine ideal membership and compute syzygies.The main goal is to present and verify algorithms for constructing these Gröbner basis counterparts.As an application, we will produce a method for computing generators for the first syzygy module of a subset of anR[x₁,...,x_n] where each coordinate of each syzygy must be an element of the subalgebra.     

BIBasis,a package for reduce and Macaulay2 computer algebra systems to compute Boolean involutive and Gröbner bases

In this paper, we describe the BIBasis package designed for REDUCE and Macaulay2 computer algebra systems, which allows one to compute Boolean involutive bases and Gröbner bases. The implementations and user interfaces of the package for both systems are described in the respective sections of the paper. Also, we present results of comparisons of BIBasis with other packages and algorithms for constructing Boolean Gröbner bases available in the computer algebra systems.