Gröbner bases and generalized Padé approximation

It is shown how to find general multivariate Padé approximation using the Gröbner basis technique. This method is more flexible than previous approaches, and several examples are given to illustrate this advantage. When the number of variables is small compared to the degree of approximation, the Gröbner basis technique is more efficient than the linear algebra methods in the literature.

     

Structure of Gröbner bases with respect to block orders

In this paper we study the structure of Gröbner bases with respect to block orders. We extend Lazard's theorem and the Gianni-Kalkbrenner theorem to the case of a zero-dimensional ideal whose trace in the ring generated by the first block of variables is radical. We then show that they do not hold for general zero-dimensional ideals.

     

Estimating the Volumes of the Cones in a Gröbner Fan

We present a stochastic method for estimating the relative volumes of the Gröbner cones of a Gröbner fan without computing the actual fan. The method is particularly useful when the dimension of the Gröbner fan is large and/or the volumes of several or all cones need to be estimated. A Macaulay 2 implementation for uniform sampling from the Gröbner fan is provided by the author.     

Regularity of lex-segment ideals: Some closed formulas and applications

A closed formula for computing the regularity of the lex-segment ideal in terms of the Hilbert function is given. This regularity bounds the one of any ideal with the same Hilbert function. As a consequence, we give explicit expressions to bound the regularity of a projective scheme in terms of the coefficients of the Hilbert polynomial.

We also characterize, in terms of their coefficients, which polynomials are Hilbert polynomials of some projective scheme.

Finally, we provide some applications to estimates for the maximal degree of generators of Gröbner bases in terms of the degrees of defining equations.

     

On the universal Gröbner bases of toric ideals of graphs

The universal Gröbner basis of an ideal is a Gröbner basis with respect to all term orders simultaneously. We characterize in graph theoretical terms the elements of the universal Gröbner basis of the toric ideal of a graph. We also provide a new degree bound. Finally, we give examples of graphs for which the true degrees of their circuits are less than the degrees of some elements of the Graver basis.     

Generic tropical varieties

We show that in the constant coefficient case the generic tropical variety of a graded ideal exists. This can be seen as an analogue to the existence of the generic initial ideal in Gröbner basis theory. We determine the generic tropical variety as a set in general and as a fan for principal ideals and linear ideals.     

Gröbner bases, local cohomology and reduction number

D. Bayer and M. Stillman showed that Gröbner bases can be used to compute the Castelnuovo-Mumford regularity which is a measure for the vanishing of graded local cohomology modules. The aim of this paper is to show that the same method can be applied to study other cohomological invariants as well as the reduction number.

     

Gröbner bases for solving ΔQ-equations in water distribution networks

The analysis of water distribution network is of great interest to hydraulic engineers. Although the water distribution network has been extensively studied for the last decades, there are still many unsolved problems awaiting clarification. In this paper, an algorithm is presented that describes a computationally efficient technique for water distribution networks based on Gröbner basis method. Gröbner basis algorithm provides the exact algorithmic solutions for solving the system of equations. However, Gröbner algorithm works only for polynomials and moreover for a large scale network, it takes a long CPU time. Hence, we present two other algorithms that work for non-polynomials and large scale problems. Three examples are presented to show the effectiveness of Gröbner basis method compared with Hardy Cross method, linear theory and Gradient method.     

The arithmetic of Jacobian groups of superelliptic cubics

We present two algorithms for the arithmetic of cubic curves with a totally ramified prime at infinity. The first algorithm, inspired by Cantor's reduction for hyperelliptic curves, is easily implemented with a few lines of code, making use of a polynomial arithmetic package. We prove explicit reducedness criteria for superelliptic curves of genus 3 and 4, which show the correctness of the algorithm. The second approach, quite general in nature and applicable to further classes of curves, uses the FGLM algorithm for switching between Gröbner bases for different orderings. Carrying out the computations symbolically, we obtain explicit reduction formulae in terms of the input data.

     

Computing border bases

This paper presents several algorithms that compute border bases of a zero-dimensional ideal. The first relates to the FGLM algorithm as it uses a linear basis transformation. In particular, it is able to compute border bases that do not contain a reduced Gröbner basis. The second algorithm is based on a generic algorithm by Bernard Mourrain originally designed for computing an ideal basis that need not be a border basis. Our fully detailed algorithm computes a border basis of a zero-dimensional ideal from a given set of generators. To obtain concrete instructions we appeal to a degree-compatible term ordering σ and hence compute a border basis that contains the reduced σ-Gröbner basis. We show an example in which this computation actually has advantages over Buchberger's algorithm. Moreover, we formulate and prove two optimizations of the Border Basis Algorithm which reduce the dimensions of the linear algebra subproblems.     

The vanishing ideal of a finite set of closed points in affine space

Given a finite set of closed rational points of affine space over a field, we give a Gröbner basis for the lexicographic ordering of the ideal of polynomials which vanish at all given points. Our method is an alternative to the Buchberger-Möller algorithm, but in contrast to that, we determine the set of leading terms of the ideal without solving any linear equation but by induction over the dimension of affine space. The elements of the Gröbner basis are also computed by induction over the dimension, using one-dimensional interpolation of coefficients of certain polynomials.     

Computations in differential and difference modules

Constructive methods based on the Gröbner bases theory have been used many times in commutative algebra over the past 20 years, in particular, they allow the computation of such important invariants of manifolds given by systems of algebraic equations as their Hilbert polynomials. In differential and difference algebra, the analogous roles play characteristic sets.In this paper, algorithms for computations in differential and difference modules, which allow for the computation of characteristic sets (Gröbner bases) in differential, difference, and polynomial modules and differential (difference) dimension polynomials, are described. The algorithms are implemented in the algorithmic language REFAL.     

Gröbner Flags and Gorenstein Algebras

The goal of this paper is to study the Koszul property and the property of having a Gröbner basis of quadrics for classical varieties and algebras as canonical curves, finite sets of points and Artinian Gorenstein algebras with socle in low degree. Our approach is based on the notion of Gröbner flags and Koszul filtrations. The main results are the existence of a Gröbner basis of quadrics for the ideal of the canonical curve whenever it is defined by quadrics, the existence of a Gröbner basis of quadrics for the defining ideal of s 2n points in general linear position in P ⁿ , and the Koszul property of the generic Artinian Gorenstein algebra of socle degree 3.     

When Does a Submodule of (ℝ[x 1 ⋯, x k]) n Contain a Positive Element?

We characterize for modules consisting of tuples of Laurent polynomials with real coefficients whether such a module contains a positive element. The two conditions needed are numerical and directional positivity. The proof applies universal Gröbner bases.     

Ring graphs and complete intersection toric ideals

We study the family of graphs whose number of primitive cycles equals its cycle rank. It is shown that this family is precisely the family of ring graphs. Then we study the complete intersection property of toric ideals of bipartite graphs and oriented graphs. An interesting application is that complete intersection toric ideals of bipartite graphs correspond to ring graphs and that these ideals are minimally generated by Gröbner bases. We prove that any graph can be oriented such that its toric ideal is a complete intersection with a universal Gröbner basis determined by the cycles. It turns out that bipartite ring graphs are exactly the bipartite graphs that have complete intersection toric ideals for any orientation.     

Parallel algorithms for Gröbner-basis construction

The problem of the Gröbner-basis construction is important both from the theoretical and applied points of view. As examples of applications of Gröbner bases, one can mention the consistency problem for systems of nonlinear algebraic equations and the determination of the number of solutions to a system of nonlinear algebraic equations. The Gröbner bases are actively used in the constructive theory of polynomial ideals and at the preliminary stage of numerical solution of systems of nonlinear algebraic equations. Unfortunately, many real examples cannot be processed due to the high computational complexity of known algorithms for computing the Gröbner bases. However, the efficiency of the standard basis construction can be significantly increased in practice. In this paper, we analyze the known algorithms for constructing the standard bases and consider some methods for increasing their efficiency. We describe a technique for estimating the efficiency of paralleling the algorithms and present some estimates.     

Minimised Geometric Buchberger Algorithm for Integer Programming

Recently, various algebraic integer programming (IP) solvers have been proposed based on the theory of Gröbner bases. The main difficulty of these solvers is the size of the Gröbner bases generated. In algorithms proposed so far, large Gröbner bases are generated by either introducing additional variables or by considering the generic IP problem IP _A,C . Some improvements have been proposed such as Hosten and Sturmfels' method (GRIN) designed to avoid additional variables and Thomas' truncated Gröbner basis method which computes the reduced Gröbner basis for a specific IP problem IP _A,C (b) (rather than its generalisation IP _A,C ). In this paper we propose a new algebraic algorithm for solving IP problems. The new algorithm, called Minimised Geometric Buchberger Algorithm, combines Hosten and Sturmfels' GRIN and Thomas' truncated Gröbner basis method to compute the fundamental segments of an IP problem IP _A,C directly in its original space and also the truncated Gröbner basis for a specific IP problem IP _A,C (b). We have carried out experiments to compare this algorithm with others such as the geometric Buchberger algorithm, the truncated geometric Buchberger algorithm and the algorithm in GRIN. These experiments show that the new algorithm offers significant performance improvement.     

Involutive Division Techniques: Some Generalizations and Optimizations

A new class of involutive divisions induced by certain orderings of monomials is considered. It is proved that these divisions are Noetherian and constructive. Therefore, each of them allows one to compute an involutive Gröbner basis of a polynomial ideal by sequentially examining multiplicative reductions of nonmultiplicative prolongations. The dependence of involutive algorithms on the completion ordering is studied. Based on the properties of particular involutive divisions, two computational optimizations are suggested. One of them consists of a special choice of the completion ordering. The other optimization is related to recomputing multiplicative and nonmultiplicative variables in the course of the algorithm. Bibliography: 17 titles.     

Algorithms for finding the minimal polynomials and inverses of resultant matrices

In this paper, algorithms for computing the minimal polynomial and the common minimal polynomial of resultant matrices over any field are presented by means of the approach for the Gröbner basis of the ideal in the polynomial ring, respectively, and two algorithms for finding the inverses of such matrices are also presented. Finally, an algorithm for the inverse of partitioned matrix with resultant blocks over any field is given, which can be realized by CoCoA 4.0, an algebraic system over the field of rational numbers or the field of residue classes of modulo prime number. We get examples showing the effectiveness of the algorithms.     

Normal toric ideals of low codimension

Every normal toric ideal of codimension two is minimally generated by a Gröbner basis with squarefree initial monomials. A polynomial time algorithm is presented for checking whether a toric ideal of fixed codimension is normal.