Gröbner–Shirshov bases for brace algebras

Let A be a brace algebra. This structure implies that A is also a pre-Lie algebra. In this paper, we establish Composition-Diamond lemma for brace algebras. For each pre-Lie algebra L, we find a Gröbner–Shirshov basis for its universal brace algebra U_b(L). As applications, we determine an explicit linear basis for U_b(L) and prove that L is a pre-Lie subalgebra of U_b(L).     

Gröbner–Shirshov bases for pre-associative algebras

We develop Gröbner–Shirshov bases technique for pre-associative (dendriform) algebras and prove a version of composition-diamond lemma.     

Gröbner–Shirshov bases for some Lie algebras

Siberian Mathematical Journal - We give Gröbner–Shirshov bases for the Drinfeld–Kohno Lie algebra L n in [1] and the Kukin Lie algebra A P in [2], where P is a semigroup. By way of...     

Invariant G2V algorithm for computing SAGBI-Gröbner bases

Faugère and Rahmany have presented the invariant F5 algorithm to compute SAGBI-Grbner bases of ideals of invariant rings. This algorithm has an incremental structure, and it is based on the matrix version of F5 algorithm to use F5 criterion to remove a part of useless reductions. Although this algorithm is more efficient than the Buchberger-like algorithm, however it does not use all the existing criteria (for an incremental structure) to detect superfluous reductions. In this paper, we consider a new algorithm, namely, invariant G2V algorithm, to compute SAGBI-Grbner bases of ideals of invariant rings using more criteria. This algorithm has a new structure and it is based on the G2V algorithm; a variant of the F5 algorithm to compute Grbner bases. We have implemented our new algorithm in Maple , and we give experimental comparison, via some examples, of performance of this algorithm with the invariant F5 algorithm.     

Grbner bases in difference-differential modules and difference-differential dimension polynomials

In this paper we extend the theory of Grbner bases to difference-differential modules and present a new algorithmic approach for computing the Hilbert function of a finitely generated difference-differential module equipped with the natural filtration. We present and verify algorithms for construct-ing these Grbner bases counterparts. To this aim we introduce the concept of "generalized term order" on Nm ×Zn and on difference-differential modules. Using Grbner bases on difference-differential mod-ules we present a direct and algorithmic approach to computing the difference-differential dimension polynomials of a difference-differential module and of a system of linear partial difference-differential equations.     

On computing Grbner bases in rings of differential operators

Insa and Pauer presented a basic theory of Grbner basis for differential operators with coeffcients in a commutative ring in 1998,and a criterion was proposed to determine if a set of differential operators is a Gro¨bner basis.In this paper,we will give a new criterion such that Insa and Pauer's criterion could be concluded as a special case and one could compute the Grbner basis more effciently by this new criterion.     

Gröbner bases in Asymptotic Analysis of Perturbed Polynomial Programs

We consider a perturbed mathematical programming problem where both the objective and the constraint functions are polynomial in all underlying decision variables and in the perturbation parameter $\varepsilon.We consider a perturbed mathematical programming problem where both the objective and the constraint functions are polynomial in all underlying decision variables and in the perturbation parameter We study the behaviour of the solutions of such a perturbed problem as Though the solutions of the programming problems are real, we consider the Karush–Kuhn–Tucker optimality system as a one-dimensional complex algebraic variety in a multi-dimensional complex space. We use the Buchberger’s elimination algorithm of the Gr?bner bases theory to replace the defining equations of the variety by its Gr?bner basis, that has the property that one of its elements is bivariate, that is, a polynomial in and one of the decision variables only. Changing the elimination order in the Buchberger’s algorithm, we obtain such a bivariate polynomial for each of the decision variables. Thus, the solutions of the original system reduces to a number of algebraic functions in that can be represented as a Puiseux series in a neighbourhood of . A detailed analysis of the branching order and the order of the pole is also provided. The latter is estimated via characteristics of these bivariate polynomials of Gr?bner bases.This research was supported by a grant from the Australian Research Council no. DP0343028. We are indebted to K. Avrachenkov, P. Howlett, and V. Gaitsgory for many helpful discussions.     

Quadratic Gröbner bases for smooth 3×3 transportation polytopes

The toric ideals of 3×3 transportation polytopes T_rc\mathsf{T}_{\mathbf{rc}} are quadratically generated. The only exception is the Birkhoff polytope B ₃. If T_rc\mathsf{T}_{\mathbf{rc}} is not a multiple of B ₃, these ideals even have square-free quadratic initial ideals. This class contains all smooth 3×3 transportation polytopes.     

Simple signature based iterative algorithm for calculation of Gröbner bases

The paper presents an algorithm for calculation of Gröbner bases with the use of labeled polynomials from the F5 algorithm. The distinct feature of this algorithm is the simplicity both of the algorithm and the proof of its correctness achieved without loss of efficiency. This leads to a simple implementation whose performance is in par with more complex analogues.     

Differential Gröbner bases in one variable and in the partial case

Differential Gröbner bases of differential ideals in one differential variable and in the partial are characterized, when a canonical term ordering compatible with the derivations is used.     

差分-微分模上的Gröbner基及差分-微分维数多项式

通过引入广义单项式序把Gröbner基理论拓展到差分\!-\!微分模上, 构造和证明了差分\!-\!微分模上Gröbner基算法. 然后利用差分-微分模上的Gröbner基构造了线性差分-微分方程系的维数多项式算法.     

Gröbner–Shirshov bases for Vinberg–Koszul–Gerstenhaber right-symmetric algebras

In this paper, we establish the composition-diamond lemma for right-symmetric algebras. As an application, we give a Gröbner–Shirshov basis for the universal enveloping right-symmetric algebra of a Lie algebra.     

Termination of algorithm for computing relative Gr?bner bases and difference differential dimension polynomials

We introduce the concept of difference-differential degree compatibility on generalized term orders. Then we prove that in the process of the algorithm the polynomials with higher and higher degree would not be produced, if the term orders ‘?’ and ‘?′’ are difference-differential degree compatibility. So we present a condition on the generalized orders and prove that under the condition the algorithm for computing relative Gr?bner bases will terminate. Also the relative Gr?bner bases exist under the condition. Finally, we prove the algorithm for computation of the bivariate dimension polynomials in difference-differential modules terminates.     

Approximation Representations for Δ<Subscript>2</Subscript> Reals

We study ₂ reals x in terms of how they can be approximated symmetrically by a computable sequence of rationals. We deal with a natural notion of approximation representation and study how these are related computationally for a fixed x. This is a continuation of earlier work; it aims at a classification of ₂ reals based on approximation and it turns out to be quite different than the existing ones (based on information content etc.)Mathematics Subject Classification (2000): 03F60, 03D30     

A three‐phase procedure for designing an irrigation system's water distribution network

This paper focuses on the design of an irrigation network included in a public project to build a distributing water system for agricultural purposes. We begin by outlining the issue. We then present a procedure composed of three sequential modules to tackle this complex problem. The first module provides the design of the network links by heuristically constructing a short length Steiner forest. In the second module, the flows for every arc of this network are calculated. The last one determines the size of the pipes and pumps by solving a mixed binary linear programming problem. A real experiment is reported. Although further improvements are required, the results confirm the adaptability of the overall procedure to assist agricultural engineers in preparing their projects.     

Pivoting in Extended Rings for Computing Approximate Gr?bner Bases

It is well known that in the computation of Gr?bner bases arbitrarily small perturbations in the coefficients of polynomials may lead to a completely different staircase, even if the solutions of the polynomial system change continuously. This phenomenon is called artificial discontinuity in Kondratyev’s Ph.D. thesis. We show how such phenomenon may be detected and even “repaired” by using a new variable to rename the leading term each time we detect a “problem”. We call such strategy the TSV (Term Substitutions with Variables) strategy. For a zero-dimensional polynomial ideal, any monomial basis (containing 1) of the quotient ring can be found with the TSV strategy. Hence we can use TSV strategy to relax term order while keeping the framework of Gr?bner basis method so that we can use existing efficient algorithms (for instance the F ₅ algorithm) to compute an approximate Gr?bner basis. Our main algorithms, named TSVn and TSVh, can be used to repair artificial e{\epsilon}-discontinuities. Experiments show that these algorithms are effective for some nontrivial problems.     

Fractional-step <Emphasis Type="Italic">θ</Emphasis>-method for solving singularly perturbed problem in ecology

We consider a predator-prey model arising in ecology that describes a slow-fast dynamical system. The dynamics of the model is expressed by a system of nonlinear differential equations having different time scales. Designing numerical methods for solving problems exhibiting multiple time scales within a system, such as those considered in this paper, has always been a challenging task. To solve such complicated systems, we therefore use an efficient time-stepping algorithm based on fractional-step methods. To develop our algorithm, we first decouple the original system into fast and slow sub-systems, and then apply suitable sub-algorithms based on a class of θ-methods, to discretize each sub-system independently using different time-steps. Then the algorithm for the full problem is obtained by utilizing a higher-order product method by merging the sub-algorithms at each time-step. The nonlinear system resulting from the use of implicit schemes is solved by two different nonlinear solvers, namely, the Jacobian-free Newton-Krylov method and the well-known Anderson’s acceleration technique. The fractional-step θ-methods give us flexibility to use a variety of methods for each sub-system and they are able to preserve qualitative properties of the solution. We analyze these methods for stability and convergence. Several numerical results indicating the efficiency of the proposed method are presented. We also provide numerical results that confirm our theoretical investigations.