An improvement over the GVW algorithm for inhomogeneous polynomial systems

The GVW algorithm provides a new framework for computing Gröbner bases efficiently. If the input system is not homogeneous, some J-pairs with larger signatures but lower degrees may be rejected by GVW's criteria, and instead, GVW has to compute some J-pairs with smaller signatures but higher degrees. Consequently, degrees of polynomials appearing during the computations may unnecessarily grow up higher, and hence, the total computations become more expensive. This phenomenon happens more frequently when the coefficient field is a finite field and the field polynomials are involved in the computations. In this paper, a variant of the GVW algorithm, called M-GVW, is proposed. The concept of mutant pairs is introduced to overcome the inconveniences brought by inhomogeneous inputs. In aspects of implementations, to obtain efficient implementations of GVW/M-GVW over boolean polynomial rings, we take advantages of the famous library M4RI. We propose a new rotating swap method of adapting efficient routines in M4RI to deal with the one-direction reductions in GVW/M-GVW. Our implementations are tested with many examples from Boolean polynomial rings, and the timings show M-GVW usually performs much better than the original GVW algorithm if mutant pairs are found.     

Amortized multi-point evaluation of multivariate polynomials

The evaluation of a polynomial at several points is called the problem of multi-point evaluation. Sometimes, the set of evaluation points is fixed and several polynomials need to be evaluated at this set of points. Several efficient algorithms for this kind of “amortized” multi-point evaluation have been developed recently for the special cases of bivariate polynomials or when the set of evaluation points is generic. In this paper, we extend these results to the evaluation of polynomials in an arbitrary number of variables at an arbitrary set of points. We prove a softly linear complexity bound when the number of variables is fixed. Our method relies on a novel quasi-reduction algorithm for multivariate polynomials, that operates simultaneously with respect to several orderings on the monomials.     

Symbolic Differential Elimination for Symmetry Analysis

Differential problems are ubiquitous in mathematical modeling of physical and scientific problems. Algebraic analysis of differential systems can help in determining qualitative and quantitative properties of solutions of such systems. In this tutorial paper we describe several algebraic methods for investigating differential systems.     

Gröbner Bases for the Polynomial Ring with Infinite Variables and Their Applications

We develop the theory of Gröbner bases for ideals in a polynomial ring with countably infinite variables over a field. As an application we reconstruct some of the one-to-one correspondences among various sets of partitions by using the division algorithm.     

Very ampleness of multiple of tetragonal linear systems

In this paper we continue the study of sandwich near‐rings. We introduce the sandwich near‐ring of homogeneous functions,N: = M _F(D,W,ψ) where Fis a fieldDis an F-setWa vector space over Fand ψW→D, a homogeneous map. We investigate the internal structure of Nin terms of the components D, W,and ψ     

NON-COMMUTATIVE GRÖBNER BASES UNDER COMPOSITION

Polynomial composition is the operation of replacing the variables in a polynomial with other polynomials. In this paper we give sufficient and necessary conditions on a set Θ of non-commutative polynomials to assure that the set G ○ Θ of composed polynomials is a Gröbner basis in the free associative algebra whenever G is. The subject was initiated by Hong, treating the commutative analogue in (1998, J. Symb. Comput. 25, 643–663).     

Universal Associative Envelopes of Nonassociative Triple Systems

We construct universal associative envelopes for the nonassociative triple systems arising from the trilinear operations of Bremner and Peresi applied to the 2-dimensional simple associative triple system. We use noncommutative Gröbner bases to determine monomial bases, structure constants, and centers of the universal envelopes. We show that the infinite dimensional envelopes are closely related to the down-up algebras of Benkart and Roby. For the finite dimensional envelopes, we determine the Wedderburn decompositions and classify the irreducible representations.     

Gröbner Bases for Ideals of σ-PBW Extensions

In this article, we introduce the σ-PWB extensions and construct the theory of Gröbner bases for the left ideals of them. We prove the Hilbert's basis theorem and the division algorithm for this more general class of Poincaré–Birkhoff–Witt extensions. For the particular case of bijective and quasi-commutative σ-PWB extensions, we implement the Buchberger's algorithm for computing Gröbner bases of left ideals.     

Ideals Generated by Diagonal 2-Minors

With a simple graph G on [n], we associate a binomial ideal P_G generated by diagonal minors of an n × n matrix X = (x_ij) of variables. We show that for any graph G, P_G is a prime complete intersection ideal and determine the divisor class group of K[X]/P_G. By using these ideals, one may find a normal domain with free divisor class group of any given rank.     

Gröbner–Shirshov Bases for Schreier Extensions of Groups

In this article, by using the Gröbner–Shirshov bases, we give characterizations of the Schreier extensions of groups when the group is presented by generators and relations. An algorithm to find the conditions of a group to be a Schreier extension is obtained. By introducing a special total order, we obtain the structure of the Schreier extension by an HNN group.     

H-bases for polynomial interpolation and system solving

The H-basis concept allows, similarly to the Gröbner basis concept, a reformulation of nonlinear problems in terms of linear algebra. We exhibit parallels of the two concepts, show properties of H-bases, discuss their construction and uniqueness questions, and prove that n polynomials in n variables are, under mild conditions, already H-bases. We apply H-bases to the solution of polynomial systems by the eigenmethod and to multivariate interpolation.     

On generator and parity-check polynomial matrices of generalized quasi-cyclic codes

Generalized quasi-cyclic (GQC) codes have been investigated as well as quasi-cyclic (QC) codes, e.g., on the construction of efficient low-density parity-check codes. While QC codes have the same length of cyclic intervals, GQC codes have different lengths of cyclic intervals. Similarly to QC codes, each GQC code can be described by an upper triangular generator polynomial matrix, from which the systematic encoder is constructed. In this paper, a complete theory of generator polynomial matrices of GQC codes, including a relation formula between generator polynomial matrices and parity-check polynomial matrices through their equations, is provided. This relation generalizes those of cyclic codes and QC codes. While the previous researches on GQC codes are mainly concerned with 1-generator case or linear algebraic approach, our argument covers the general case and shows the complete analogy of QC case. We do not use Gröbner basis theory explicitly in order that all arguments of this paper are self-contained. Numerical examples are attached to the dual procedure that extracts one from each other. Finally, we provide an efficient algorithm which calculates all generator polynomial matrices with given cyclic intervals.     

Full Graphs and Koszul Algebras I

The main result of this article is the establishment of a new connection between combinatorics and noncommutative algebra. This is done by linking a certain class of directed graphs, called full graphs, to quotients of path algebras that are Koszul algebras.     

On the peirce decompositions for freudenthal—kantor triple systems

It is the object of this paper to investigate the Peirce decomposition for Freudenthal-Kantor triple systems, by making use of the concept of anti-derivation of the triple systems.