A Generalization of Gröbner Basis Algorithms to Polycyclic Group Rings

It is well-known that for the integral group ring of a polycyclic group several decision problems are decidable, in particular the ideal membership problem. In this paper we define an effective reduction relation for group rings over polycyclic groups. This reduction is based on left multiplication and hence corresponds to left ideals. Using this reduction we present a generalization of Buchberger's Gröbner basis method by giving an appropriate definition of “Gröbner bases” in this setting and by characterizing them using the concepts of saturation and s-polynomials. The approach is extended to two-sided ideals and a discussion on a Gröbner bases approach for right ideals is included.     

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.     

A Fast Algorithm for Gröbner Basis Conversion and its Applications

The Gröbner walk method converts a Gröbner basis by partitioning the computation of the basis into several smaller computations following a path in the Gröbner fan of the ideal generated by the system of equations. The method works with ideals of zero-dimension as well as positive dimension. Typically, the target point of the walking path lies on the intersection of very many cones, which ends up with initial forms of a considerable number of terms. Therefore, it is crucial to the performance of the conversion to change the target point since we have to compute a Gröbner basis with respect to the elimination term order of such large initial forms. In contrast to heuristic methods found in the literature, in this paper the author presents a deterministic method to vary the target point in order to ensure the generality of the position, i.e. we always have just a few terms in the initial forms. It turns out that this theoretical result brings a dramatic speed-up in practice. We have implemented the Gröbner walk method together with the deterministic method for varying the target point in the kernel of Mathematica. Our experiments show the superlative performance of our improved Gröbner walk method in comparison with other known methods. Our best performance is 3  ×  10⁴times faster than the direct computation of the reduced Gröbner basis with respect to pure lexicographic term order (using the Buchberger algorithm and the sugar cube strategy). We also discuss the complexity of the conversion algorithm and prove a degree bound for polynomials in the target Gröbner basis. In the second part of the paper, we present some applications of the conversion method for implicitization and geometric reasoning. We compare the efficiency of the improved Gröbner walk method with other methods for elimination such as multivariate resultant methods.     

Automated Reducible Geometric Theorem Proving and Discovery by Gröbner Basis Method

In this paper, we investigate the problem that the conclusion is true on some components of the hypotheses for a geometric statement. In that case, the affine variety associated with the hypotheses is reducible. A polynomial vanishes on some but not all the components of a variety if and only if it is a zero divisor in a quotient ring with respect to the radical ideal defined by the variety. Based on this fact, we present an algorithm to decide if a geometric statement is generally true or generally true on components by the Gröbner basis method. This method can also be used in geometric theorem discovery, which can give the complementary conditions such that the geometric statement becomes true or true on components. Some reducible geometric statements are given to illustrate our method.     

Reduced Gröbner Bases,Free Difference–Differential Modules and Difference–Differential Dimension Polynomials

We define a special type of reduction in a free left module over a ring of difference–differential operators and use the idea of the Gröbner basis method to develop a technique that allows us to determine the Hilbert function of a finitely generated difference–differential module equipped with the natural double filtration. The results obtained are applied to the study of difference–differential field extensions and systems of difference–differential equations. We prove a theorem on difference–differential dimension polynomial that generalizes both the classical Kolchin’s theorem on dimension polynomial of a differential field extension and the corresponding author’s result for difference fields. We also determine invariants of a difference–differential dimension polynomial and consider a method of computation of the dimension polynomial associated with a system of linear difference–differential equations.     

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.     

Gröbner Bases over Galois Rings with an Application to Decoding Alternant Codes

We develop a theory of Gröbner bases over Galois rings, following the usual formulation for Gröbner bases over finite fields. Our treatment includes a division algorithm, a characterization of Gröbner bases, and an extension of Buchberger’s algorithm. One application is towards the problem of decoding alternant codes over Galois rings. To this end we consider the module M =  {(a, b) :aS ≡ b  mod x^r} of all solutions to the so-called key equation for alternant codes, where S is a syndrome polynomial. In decoding, a particular solution (Σ, Ω)  ∈ M is sought satisfying certain conditions, and such a solution can be found in a Gröbner basis of M. Applying techniques introduced in the first part of this paper, we give an algorithm which returns the required solution.     

The Inverse Gröbner Basis Problem in Codimension Two

Generic linkage is used to compute a prime ideal such that the radical of the initial ideal of the prime ideal is equal to the radical of a given codimension two monomial ideal that has Cohen–Macaulay quotient ring.     

A New Algorithm for Discussing Gröbner Bases with Parameters

Let F be a set of polynomials in the variables __x = x₁, . . . , x_nwith coefficients in R [__ a ], where R is a UFD and __ a = a₁, . . . ,a_m a set of parameters. In this paper we present a new algorithm for discussing Gröbner bases with parameters. The algorithm obtains all the cases over the parameters leading to different reduced Gröbner basis, when the parameters in F are substituted in an extension field K of R. This new algorithm improves Weispfenning’s comprehensive Gröbner basis CGB algorithm, obtaining a reduced complete set of compatible and disjoint cases. A final improvement determines the minimal singular variety outside of which the Gröbner basis of the generic case specializes properly. These constructive methods provide a very satisfactory discussion and rich geometrical interpretation in the applications.     

A Gröbner bases-based shell for rule-based expert systems development

A Gröbner Basis of a polynomial ideal is a very special kind of basis. It characterises the ideal and can be calculated by an effective algorithm. It has been shown how it is possible to use Gröbner Bases to compute calculations in Boolean and multi-valued logics. We have extended this work to deal with consistency and knowledge extraction in Rule-Based Expert Systems. In this article, we briefly describe the applications already developed (Railway Interlockings, Medical Appropriateness Criteria), the ongoing development projects (Museums Management, Stock Investment Consulting) and research planned for the immediate future (a full Gröbner Bases-Based Shell for Rule-Based Expert System Development).     

A Gröbner Approach to Involutive Bases

Recently, Zharkov and Blinkov introduced the notion of involutive bases of polynomial ideals. This involutive approach has its origin in the theory of partial differential equations and is a translation of results of Janet and Pommaret. In this paper we present a pure algebraic foundation of involutive bases of Pommaret type. In fact, they turn out to be generalized left Gröbner bases of ideals in the commutative polynomial ring with respect to a non-commutative grading. The introduced theory will allow not only the verification of the results of Zharkov and Blinkov but it will also provide some new facts.     

Regular Gröbner Bases

In this paper we introduce the concept of bi-automaton algebras, generalizing the automaton algebras previously defined by Ufnarovski. A bi-automaton algebra is a quotient of the free algebra, defined by a binomial ideal admitting a Gröbner basis which can be encoded as a regular set; we call such a Gröbner basis regular. We give several examples of bi-automaton algebras, and show how automata connected to regular Gröbner bases can be used to perform reduction.     

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.     

Multiplicative Bases,Gröbner Bases,and Right Gröbner Bases

In this paper, we study conditions on algebras with multiplicative bases so that there is a Gröbner basis theory. We introduce right Gröbner bases for a class of modules. We give an elimination theory and intersection theory for right submodules of projective modules in path algebras. Solutions to homogeneous systems of linear equations with coefficients in a quotient of a path algebra are studied via right Gröbner basis theory.     

A Note on Gröbner Bases and Integration of Rational Functions

It will be shown that for rational functions the logarithmic part of the integral can be computed in a very simple manner by Buchberger's algorithm.     

An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals,and Applications to Commutative Semigroups

It is known that the reduced Gröbner basis of general polynomial ideals can be computed in exponential space. The algorithm, obtained by Kühnle and Mayr, is, however, based on rather complex parallel computations, and, above that, makes extensive use of the parallel computation thesis. In this paper, we exhibit an exponential space algorithm for generating the reduced Gröbner basis of binomial ideals which can be implemented without any complex parallel computations. This result is then applied to derive space optimal decision procedures for the finite enumeration and subword problems for commutative semigroups.     

Counting and Gröbner Bases

We show how the complexity of counting relates to the well known phenomenon that computing Gröbner bases under a lexicographic order is generally harder than total degree orders. We give simple examples of polynomials for which it is very easy to compute their Gröbner basis using a total degree order but for which exponential time is required for a lexicographic order. It follows that conversion algorithms do not help in such cases.