Normalization of Indexed Differentials by Extending Grobner Basis Theory

It is a fundamental problem to determine the equivalence of indexed differential polynomials in both computer algebra and differential geometry.However,in the literature,there are no general computational theories for this problem.The main reasons are that the ideal generated by the basic syzygies cannot be finitely generated,and it involves eliminations of dummy indices and functions.This paper solves the problem by extending Grobner basis theory.The authors first present a division of the set of elementary indexed differential monomials E■ into disjoint subsets,by defining an equivalence relation on E■ based on Leibniz expansions of monomials.The equivalence relation on E■also induces a division of a Grobner basis of basic syzygies into disjoint subsets.Furthermore,the authors prove that the dummy index numbers of the sim-monomials of the elements in each equivalence class of E■ have upper bounds,and use the upper bounds to construct fundamental restricted rings.Finally,the canonical form of an indexed differential polynomial proves to be the normal form with respect to a subset of the Grobner basis in the fundamental restricted ring.

A Grobner Basis Algorithm for Ideals over Zero-Dimensional Valuation Rings

Zero-dimensional valuation rings are one kind of non-Noetherian rings.This paper investigates properties of zero-dimensional valuation rings and prove that a finitely generated ideal over such a ring has a Grobner basis.The authors present an algorithm for computing a Gr?bner basis of a finitely generated ideal over it.Furthermore,an interesting example is also provided to explain the algorithm.

An Extension of Grobner Basis Theory to Indexed Polynomials Without Eliminations

In computer algebra,it remains to be challenging to establish general computational theories for determining the equivalence of indexed polynomials.In previous work,the author solved the equivalence determination problem for Riemann tensor polynomials by extending Grobner basis theory.This paper extends the previous work to more general indexed polynomials that involve no eliminations of indices and functions,by the method of ST-restricted rings.A decomposed form of the Grobner basis of the defining syzygy set in each ST-restricted ring is provided,and then the canonical form of an indexed polynomial proves to be the normal form with respect to the Grobner basis in the ST-fundamental restricted ring.

A Note on Determine the Greatest Common Subfamily of Two NFSRs by Grbner Basis

For nonlinear feedback shift registers （NFSRs）, their greatest common subfamily may be not unique. Given two NFSRs, the authors only consider the case that their greatest common subfamily exists and is unique. If the greatest common subfamily is exactly the set of all sequences which can be generated by both of them, the authors can determine it by Grobner basis theory. Otherwise, the authors can determine it under some conditions and partly solve the problem.

Fast computation of Grbner basis of homogenous ideals of F[x,y]

This paper provides a fast algorithm for Grobnerbases of homogenous ideals of F[x, y] over a finite field F. We show that only the 8-polynomials of neighbor pairs of a strictly ordered finite homogenours generating set are needed in the computing of a Grobner base of the homogenous ideal. It reduces dramatically the number of unnecessary 5-polynomials that are processed. We also show that the computational complexity of our new algorithm is O（N^2）, where N is the maximum degree of the input generating polynomials. The new algorithm can be used to solve a problem of blind recognition of convolutional codes. This problem is a new generalization of the important problem of synthesis of a linear recurring sequence.

Recognizing the Semiprimitivity of N-graded Algebras via Grobner Bases

Let K〈X〉 = K（X1,..., Xn） be the free K-algebra on X = {X1,..., Xn} over a field K, which is equipped with a weight N-gradation （i.e., each Xi is assigned a positive degree）, and let G be a finite homogeneous GrSbner basis for the ideal I = （G） of K（X） with respect to some monomial ordering 〈 on K（X）. It is shown that if the monomial algebra K（X）/（LM（6）） is semiprime, where LM（6） is the set of leading monomials of 6 with respect to 〈, then the N-graded algebra A ： K（X）/I is semiprimitive in the sense of Jacobson. In the case that G is a finite nonhomogeneous Gr6bner basis with respect to a graded monomial ordering 〈gr, and the N-filtration FA of the algebra A = K（X）/I induced by the N-grading filtration FK（X） of K（X） is considered, if the monomial algebra K（X）/（LM（6）） is semiprime, then it is shown that the associated N-graded algebra G（A） and the Rees algebra A of A determined by FA are all semiprimitive.

Algebraic-Differential Attacks on a Family of Arithmetization-Oriented Symmetric Ciphers

Motivated by applications in advanced cryptographic protocols,research on arithmetizationoriented symmetric primitives has been rising in the field of symmetric cryptography in recent years.In this paper,the authors focus on on the collision attacks for a family of arithmetization-oriented symmetric ciphers GMiMCHash.The authors firstly enhance the algebraically controlled differential attacks proposed by introducing more variables.Then,combining algebraic attacks and differential attacks,the authors propose algebraic-differential attacks on GMi MCHash.This attack method is shown to be effective by experiments on toy versions of GMi MCHash.The authors further introduce some tricks to reduce the complexities of algebraic-differential attacks and improve the success probability of finding collisions.

Graph Representation of Projective Resolutions

We generalize the concept -- dimension tree and the related results for monomial algebras to a more general case -- relations algebras A by bringing GrSbner basis into play. More precisely, we will describe the minimal projective resolution of a left A-module M as a rooted ＇weighted＇ diagraph to be called the minimal resolution graph for M. Algorithms for computing such diagraphs and applications as well will be presented.

Conditions for polynomial Liénard centers

In 1999, Christopher gave a necessary and sufficient condition for polynomial Li′enard centers, which requires coupled functional equations, where the primitive functions of the damping function and the restoring function are involved, to have polynomial solutions. In order to judge whether the coupled functional equations are solvable, in this paper we give an algorithm to compute a Gr¨obner basis for irreducible decomposition of algebraic varieties so as to find algebraic relations among coefficients of the damping function and the restoring function. We demonstrate the algorithm for polynomial Li′enard systems of degree 5, which are divided into 25 cases. We find all conditions of those coefficients for the polynomial Li′enard center in 13 cases and prove that the origin is not a center in the other 12 cases.

A Two-Dimensional Improvement for Farr-Gao Algorithm

Farr-Gao algorithm is a state-of-the-art algorithm for reduced Gr?bner bases of vanishing ideals of finite points, which has been implemented in Maple as a build-in command. This paper presents a two-dimensional improvement for it that employs a preprocessing strategy for computing reduced Gr?bner bases associated with tower subsets of given point sets. Experimental results show that the preprocessed Farr-Gao algorithm is more efficient than the classical one.

A Strongly-Consistent Difference Scheme for 3D Nonlinear Navier-Stokes Equations

This paper constructs a strongly-consistent explicit finite difference scheme for 3D constant viscosity incompressible Navier-Stokes equations by using of symbolic algebraic computation.The difference scheme is space second order accurate and temporal first order accurate. It is proved that difference Grobner basis algorithm is correct. By using of difference Grobner basis computation method, an element in Gr?bner basis of difference scheme for momentum equations is a difference scheme for pressure Poisson equation. The authors find that the truncation errors expressions of difference scheme is consistent with continuous errors functions about modified version of above difference equation. The authors prove that, for strongly consistent difference scheme, each element in the difference Grobner basis of such difference scheme always approximates a differential equation which vanishes on the analytic solutions of Navier-Stokes equations. To prove the strongly-consistency of this difference scheme, the differential Thomas decomposition theorem for nonlinear differential equations and difference Grobner basis theorems for difference equations are applied. Numerical test certifies that strongly-consistent difference scheme is effective.

Computing PUR of Zero-Dimensional Ideals of Breadth at Most One

In this paper,for a zero-dimensional polynomial ideal I,the authors prove that k[x_(1),x_(2),…,x_(n)]/I is cyclic if and only if the breadth of I is 0 or 1.Furthermore,the authors present a new algorithm to compute polynomial univariate representation(PUR)of such an ideal.

An efficient and globally optimal solution to perspective-n-line problem

This research develops an accurate and efficient method for the Perspective-n-Line(Pn L)problem. The developed method addresses and solves Pn L via exploiting the problem’s geometry in a non-linear least squares fashion. Specifically, by representing the rotation matrix with a novel quaternion parameterization, the Pn L problem is first decomposed into four independent subproblems. Then, each subproblem is reformulated as an unconstrained minimization problem, in which the Kronecker product is adopted to write the cost function in a more compact form. Finally, the Groobner basis technique is used to solve the polynomial system derived from the first-order optimality conditions of the cost function. Moreover, a novel strategy is presented to improve the efficiency of the algorithm. It is improved by exploiting structure information embedded in the rotation parameterization to accelerate the computing of coefficient matrix of a cost function. Experiments on synthetic data and real images show that the developed method is comparable to or better than state-of-the-art methods in accuracy, but with reduced computational requirements.

The Decision of Prime and Primary Ideal

We give more efficient criteria to characterise prime ideal or primary ideal. Further, we obtain the necessary and sufficient conditions that an ideal is prime or primary in real field from the Grobner bases directly.

Algorithmic criteria for permutation orthogonal systems over finite fields

Two criteria for orthogonal systems over finite fields are presented. The first one is an algorithm by use of Gr*ibner bases. The second one is a formula of the numbers of adjoint morphisms.