The membrane inclusions curvature equations

We examine a system of equations arising in biophysics whose solutions are believed to represent the stable positions of N conical proteins embedded in a cell membrane. Symmetry considerations motivate two equivalent refomulations of the system which allow the complete classification of solutions for small N<13. The occurrence of regular geometric patterns in these solutions suggests considering a simpler system, which leads to the detection of solutions for larger N up to 280. We use the most recent techniques of Gröbner bases computation for solving polynomial systems of equations.     

Computing Gröbner fans

This paper presents algorithms for computing the Gröbner fan of an arbitrary polynomial ideal. The computation involves enumeration of all reduced Gröbner bases of the ideal. Our algorithms are based on a uniform definition of the Gröbner fan that applies to both homogeneous and non-homogeneous ideals and a proof that this object is a polyhedral complex. We show that the cells of a Gröbner fan can easily be oriented acyclically and with a unique sink, allowing their enumeration by the memory-less reverse search procedure. The significance of this follows from the fact that Gröbner fans are not always normal fans of polyhedra, in which case reverse search applies automatically. Computational results using our implementation of these algorithms in the software package Gfan are included.

     

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.     

Minimal Gröbner bases and the predictable leading monomial property

We focus on Gröbner bases for modules of univariate polynomial vectors over a ring. We identify a useful property, the “predictable leading monomial (PLM) property” that is shared by minimal Gröbner bases of modules in F[x]^q, no matter what positional term order is used. The PLM property is useful in a range of applications and can be seen as a strengthening of the wellknown predictable degree property (= row reducedness), a terminology introduced by Forney in the 70’s. Because of the presence of zero divisors, minimal Gröbner bases over a finite ring of the type Z_p^r (where p is a prime integer and r is an integer >1) do not necessarily have the PLM property. In this paper we show how to derive, from an ordered minimal Gröbner basis, a so-called “minimal Gröbner p-basis” that does have a PLM property. We demonstrate that minimal Gröbner p-bases lend themselves particularly well to derive minimal realization parametrizations over Z_p^r. Applications are in coding and sequences over Z_p^r.     

Algorithms for computing multiplier ideals

We give algorithms for computing multiplier ideals using Gröbner bases in Weyl algebras. To this end, we define a modification of Budur-Musta?aˇ-Saito’s generalized Bernstein-Sato polynomial. We present several examples computed by our algorithm.     

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.     

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.     

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.

     

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.     

Homological Computations in PBW Modules

In this paper the Poincaré–Birkhoff–Witt (PBW) rings are characterized. Gröbner bases techniques are also developed for these rings. An explicit presentation of Ext ⁱ (M,N) is provided when N is a centralizing bimodule.     

Generalized binomial edge ideals

This paper studies a class of binomial ideals associated to graphs with finite vertex sets. They generalize the binomial edge ideals, and they arise in the study of conditional independence ideals. A Gröbner basis can be computed by studying paths in the graph. Since these Gröbner bases are square-free, generalized binomial edge ideals are radical. To find the primary decomposition a combinatorial problem involving the connected components of subgraphs has to be solved. The irreducible components of the solution variety are all rational.     

Toric ideals of lattice path matroids and polymatroids

White has conjectured that the toric ideal of a matroid is generated by quadric binomials corresponding to symmetric basis exchanges. We prove a stronger version of this conjecture for lattice path polymatroids by constructing a monomial order under which these sets of quadrics form Gröbner bases. We then introduce a larger class of polymatroids for which an analogous theorem holds. Finally, we obtain the same result for lattice path matroids as a corollary.     

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.     

Supernormal Vector Configurations

A configuration of lattice vectors is supernormal if it contains a Hilbert basis for every pointed cone spanned by a subset. We study such configurations from various perspectives, including triangulations, integer programming and Gröbner bases. Our main result is a bijection between virtual chambers of the configuration and virtual initial ideals of the associated binomial ideal.     

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.     

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.

     

Computing global minima to polynomial optimization problems using Gröbner bases

The local optimality conditions to polynomial optimization problems are a set of polynomial equations (plus some inequality conditions). With the recent techniques of Gröbner bases one can find all solutions to such systems, and hence also find global optima. We give a short survey of these methods. We also apply them to a set of problems termed with exact solutions unknown in the problem sets of Hock and Schittkowski. To these problems we give exact solutions.     

Symbolic Computation for Moments and Filter Coefficients of Scaling Functions

Algebraic relations between discrete and continuous moments of scaling functions are investigated based on the construction of Bell polynomials. We introduce families of scaling functions which are parametrized by moments. Filter coefficients of scaling functions and wavelets are computed with computer algebra methods (in particular Gröbner bases) using relations between moments. Moreover, we propose a novel concept for data compression based on parametrized wavelets.Received December 15, 2003     

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.