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.     

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.     

A New Method for the Construction of Multivariate Minimal Interpolation Polynomial

The extended Hermite interpolation problem on segment points set over n-dimensional Euclidean space is considered. Based on the algorithm to compute the Gröbner basis of Ideal given by dual basis a new method to construct minimal multivariate polynomial which satisfies the interpolation conditions is given.     

Effective computation of singularities of parametric affine curves

Let k be a field of characteristic zero and f(t),g(t) be polynomials in k[t]. For a plane curve parameterized by x=f(t),y=g(t), Abhyankar developed the notion of Taylor resultant (Mathematical Surveys and Monographs, Vol. 35, American Mathematical Society, Providence, RI, 1990) which enables one to find its singularities without knowing its defining polynomial. This concept was generalized as D-resultant by Yu and Van den Essen (Proc. Amer. Math. Soc. 125(3) (1997) 689), which works over an arbitrary field. In this paper, we extend this to a curve in affine n-space parameterized by x₁=f₁(t),…,x_n=f_n(t) over an arbitrary ground field k, where f₁,…,f_n∈k[t]. This approach compares to the usual approach of computing the ideal of the curve first. It provides an efficient algorithm of computing the singularities of such parametric curves using Gröbner bases. Computational examples worked out by symbolic computation packages are included.     

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.     

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 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.     

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.     

Positivity of quiver coefficients through Thom polynomials

We use the Thom Polynomial theory developed by Fehér and Rimányi to prove the component formula for quiver varieties conjectured by Knutson, Miller, and Shimozono. This formula expresses the cohomology class of a quiver variety as a sum of products of Schubert polynomials indexed by minimal lace diagrams, and implies that the quiver coefficients of Buch and Fulton are non-negative. We also apply our methods to give a new proof of the component formula from the Gröbner degeneration of quiver varieties, and to give generating moves for the KMS-factorizations that form the index set in K-theoretic versions of the component formula.     

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.     

An explicit construction of ruled surfaces

The main goal of this paper is to give a general algorithm to compute, via computer-algebra systems, an explicit set of generators of the ideals of the projective embeddings of ruled surfaces, i.e. projectivizations of rank two vector bundles over curves, such that the fibers are embedded as smooth rational curves.There are two different applications of our algorithm. Firstly, given a very ample linear system on an abstract ruled surface, our algorithm allows computing the ideal of the embedded surface, all the syzygies, and all the algebraic invariants which are computable from its ideal as, for instance, the k-regularity. Secondly, it is possible to prove the existence of new embeddings of ruled surfaces.The method can be implemented over any computer-algebra system able to deal with commutative algebra and Gröbner-basis computations. An implementation of our algorithms for the computer-algebra system Macaulay2 (cf. [Daniel R. Grayson, Michael E. Stillman, Macaulay 2, a software system for research in algebraic geometry, 1993. Available at http://www.math.uiuc.edu/Macaulay2/]) and explicit examples are enclosed.     

Degree bounds for Gröbner bases in algebras of solvable type

We establish doubly-exponential degree bounds for Gröbner bases in certain algebras of solvable type over a field (as introduced by Kandri-Rody and Weispfenning). The class of algebras considered here includes commutative polynomial rings, Weyl algebras, and universal enveloping algebras of finite-dimensional Lie algebras. For the computation of these bounds, we adapt a method due to Dubé based on a generalization of Stanley decompositions. Our bounds yield doubly-exponential degree bounds for ideal membership and syzygies, generalizing the classical results of Hermann and Seidenberg (in the commutative case) and Grigoriev (in the case of Weyl algebras).     

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.     

Maximal rank and minimal generation of some parametric varieties

In this paper, continuing work of the second author (J. Pure Appl. Algebra 155 (2001) 77) for rational curves, we address the problem of computing the generators of the ideal of an irreducible parametric variety V to the computation of the generators of the ideal of a suitable finite set of points on V. In particular, we consider the case of general parametric surfaces and threefolds and of general parametric surfaces represented by polynomials with base points.     

The symmetric group given by a Gröbner basis

We present a Gröbner basis associated with the symmetric group of degree n, which is determined by a strong generating set of the symmetric group and is defined by means of a term ordering with the elimination property.     

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.     

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     

On the critical ideals of graphs

We introduce some determinantal ideals of the generalized Laplacian matrix associated to a digraph G, that we call critical ideals of G. Critical ideals generalize the critical group and the characteristic polynomials of the adjacency and Laplacian matrices of a digraph. The main results of this article are the determination of some minimal generator sets and the reduced Gröbner basis for the critical ideals of the complete graphs, the cycles and the paths. Also, we establish a bound between the number of trivial critical ideals and the stability and clique numbers of a graph.     

Decomposition of algebraic sets and applications to weak centers of cubic systems

There are many methods such as Gröbner basis, characteristic set and resultant, in computing an algebraic set of a system of multivariate polynomials. The common difficulties come from the complexity of computation, singularity of the corresponding matrices and some unnecessary factors in successive computation. In this paper, we decompose algebraic sets, stratum by stratum, into a union of constructible sets with Sylvester resultants, so as to simplify the procedure of elimination. Applying this decomposition to systems of multivariate polynomials resulted from period constants of reversible cubic differential systems which possess a quadratic isochronous center, we determine the order of weak centers and discuss the bifurcation of critical periods.     

On the coinvariants of modular representations of cyclic groups of prime order

We consider the ring of coinvariants for modular representations of cyclic groups of prime order. For all cases for which explicit generators for the ring of invariants are known, we give a reduced Gröbner basis for the Hilbert ideal and the corresponding monomial basis for the coinvariants. We also describe the decomposition of the coinvariants as a module over the group ring. For one family of representations, we are able to describe the coinvariants despite the fact that an explicit generating set for the invariants is not known. In all cases our results confirm the conjecture of Harm Derksen and Gregor Kemper on degree bounds for generators of the Hilbert ideal. As an incidental result, we identify the coefficients of the monomials appearing in the orbit product of a terminal variable for the three-dimensional indecomposable representation.