In this paper, we obtain （non-commutative） GrSbner-Shirshov bases for rect- angular bands, small extensions of semigroups and Bruck-Reilly extensions of monoids in terms of the general product.
Groebner basis theory for parametric polynomial ideals is explored with the main objec- tive of nfinicking the Groebner basis theory for ideals. Given a parametric polynomial ideal, its basis is a comprehensive GrSbne...Groebner basis theory for parametric polynomial ideals is explored with the main objec- tive of nfinicking the Groebner basis theory for ideals. Given a parametric polynomial ideal, its basis is a comprehensive GrSbner basis if and only if for every specialization of its parameters in a given field, the specialization of the basis is a GrSbnerbasis of the associated specialized polynomial ideal. For various specializations of parameters, structure of specialized ideals becomes qualitatively different even though there are significant relationships as well because of finiteness properties. Key concepts foundational to GrSbner basis theory are reexamined and/or further developed for the parametric case： （i） Definition of a comprehensive Groebner basis, （ii） test for a comprehensive GrSbner basis, （iii） parameterized rewriting, （iv） S-polynomials among parametric polynomials, （v） completion algorithm for directly computing a comprehensive Groebner basis from a given basis of a parametric ideal. Elegant properties of Groebner bases in the classical ideal theory, such as for a fixed admissible term ordering, a unique GrSbner basis can be associated with every polynomial ideal as well as that such a basis can be computed from any Groebner basis of an ideal, turn out to be a major challenge to generalize for parametric ideals; issues related to these investigations are explored. A prototype implementation of the algorithm has been successfully tried on many examples from the literature.展开更多
A complete solution classification of the perspective-three-point(P3P) problem is given by using the Gr?bner basis method. The structure of the solution space of the polynomial system deduced by the P3P problem can be...A complete solution classification of the perspective-three-point(P3P) problem is given by using the Gr?bner basis method. The structure of the solution space of the polynomial system deduced by the P3P problem can be obtained by computing a comprehensive Gr?bner system. Combining with properties of the generalized discriminant sequences, the authors give the explicit conditions to determine the number of distinct real positive solutions of the P3P problem. Several examples are provided to illustrate the effectiveness of the proposed conditions.展开更多
Some techniques using linear algebra was introduced by Faugore in F4 to speed up the reduction process during Grobner basis computations. These techniques can also be used in fast implementations of F5 and some other ...Some techniques using linear algebra was introduced by Faugore in F4 to speed up the reduction process during Grobner basis computations. These techniques can also be used in fast implementations of F5 and some other signature-based Grobner basis algorithms. When these techniques are applied, a very important step is constructing matrices from critical pairs and existing polynomials by the Symbolic Preprocessing function （given in F4）. Since multiplications of monomials and polynomials are involved in the Symbolic Preprocessing function, this step can be very costly when the number of involved polynomials/monomials is huge. In this paper, multiplications of monomials and polynomials for a Boolean polynomial ring are investigated and a specific method of implementing the Symbolic Preprocessing function over Boolean polynomial rings is reported. Many examples have been tested by using this method, and the experimental data shows that the new method is very efficient.展开更多
In 2002, Faugere presented the famous F5 algorithm for computing GrSbner basis where two cri- teria, syzygy criterion and rewritten criterion, were proposed to avoid redundant computations. He proved the correctness o...In 2002, Faugere presented the famous F5 algorithm for computing GrSbner basis where two cri- teria, syzygy criterion and rewritten criterion, were proposed to avoid redundant computations. He proved the correctness of the syzygy criterion, but the proof for the correctness of the rewritten criterion was left. Since then, F5 has been studied extensively. Some proofs for the correctness of F5 were proposed, but these proofs are valid only under some extra assumptions. In this paper, we give a proof for the correctness of F5B, an equivalent version of F5 in Buchberger＇s style. The proof is valid for both homogeneous and non-homogeneous polynomial systems. Since this proof does not depend on the computing order of the S-pairs, any strategy of selecting S-pairs could be used in F5B or F5. Furthermore, we propose a natural and non-incremental variant of F5 where two revised criteria can be used to remove almost all redundant S-pairs.展开更多
Bokut, Chen and Liu in 2010 gave a Composition-Diamond lemma for dialge- bras. In this paper, by introducing an arbitrary monomial-center ordering, we give a new Composition-Diamond lemma for dialgebras which makes th...Bokut, Chen and Liu in 2010 gave a Composition-Diamond lemma for dialge- bras. In this paper, by introducing an arbitrary monomial-center ordering, we give a new Composition-Diamond lemma for dialgebras which makes the two conditions in Bokut, Chen and Liu＇s result equivalent. The new lemma is more useful and convenient than the one Bokut, Chen and Liu got. We show that every ideal of the free dialgebra generated by a set X has a unique reduced GrSbner-Shirshov basis. As applications, we give a method to find normal forms of elements of an arbitrary disemigroup, in particular, two Zhuchoks＇ normal forms of the free commutative disemigroups and the free abelian disemigroups, and normal forms of the free left （right） commutative disemigroups.展开更多
A finite GrSbner-Shirshov basis is constructed for the plactic algebra of rank 3 over a field K. It is also shown that plactic algebras of rank exceeding 3 do not have finite GrSbner-Shirshov bases associated to the n...A finite GrSbner-Shirshov basis is constructed for the plactic algebra of rank 3 over a field K. It is also shown that plactic algebras of rank exceeding 3 do not have finite GrSbner-Shirshov bases associated to the natural degree-lexicographic ordering on the corresponding free algebra. The latter is in contrast with the case of a strongly related class of algebras, called Chinese algebras.展开更多
In this paper, we construct the GrSbner-Shirshov bases for degenerate Ringel- Hall algebras of types A and G2 from the multiplication formulas of the corresponding generic extension monoid algebras.
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 impro...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.展开更多
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 produc...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 GrSbner bases will terminate. Also the relative Gr6bner bases exist under the condition. Finally, we prove the algorithm for computation of the bivariate dimension polynomials in difference-differential modules terminates.展开更多
In this paper,the authors first apply the Fitzpatrick algorithm to multivariate vectorvalued osculatory rational interpolation.Then based on the Fitzpatrick algorithm and the properties of an Hermite interpolation bas...In this paper,the authors first apply the Fitzpatrick algorithm to multivariate vectorvalued osculatory rational interpolation.Then based on the Fitzpatrick algorithm and the properties of an Hermite interpolation basis,the authors present a Fitzpatrick-Neville-type algorithm for multivariate vector-valued osculatory rational interpolation.It may be used to compute the values of multivariate vector-valued osculatory rational interpolants at some points directly without computing the interpolation function explicitly.展开更多
Pan and Wang presented a method for computing uniform GrSbner bases for certain ide- als generated by polynomials with parametric exponents in 2006, and two criteria were proposed to determine if a uniform GrSbner bas...Pan and Wang presented a method for computing uniform GrSbner bases for certain ide- als generated by polynomials with parametric exponents in 2006, and two criteria were proposed to determine if a uniform GrSbner basis can be obtained. This paper gives a new algorithmic approach for computing tile uniform GrSbner basis such that Pan and Wang＇s method could be concluded as a special case. The authors use the method of reduced term order under ring homomorphisnl to get the reduced uniform GrSbner basis. Also the authors point and correct a mistake in Pan and Wang＇s method. The result is a generalization of approach of Pan and Wang and one could compute the uniform GrSbner basis more efficiently by the new approach.展开更多
In this paper, we find Hall-Shirshov type bases for free pre-Lie algebras. We show that Segal＇s basis of a free pre-Lie algebra is a type of these bases. We give a nonassociative GrSbner-Shirshov basis S for a free p...In this paper, we find Hall-Shirshov type bases for free pre-Lie algebras. We show that Segal＇s basis of a free pre-Lie algebra is a type of these bases. We give a nonassociative GrSbner-Shirshov basis S for a free pre-Lie algebra such that Irr（S） is a monomial basis （called normal words） of a free pre-Lie algebra, where Irr（S） is the set of all nonassociative words, not containing maximal nonassociative words of polynomials from S. We establish the Composition-Diamond lemma for free pre-Lie algebras over the basis of normal words and the degree breadth lexicographic ordering.展开更多
文摘In this paper, we obtain （non-commutative） GrSbner-Shirshov bases for rect- angular bands, small extensions of semigroups and Bruck-Reilly extensions of monoids in terms of the general product.
基金supported by the National Science Foundation under Grant No.DMS-1217054
文摘Groebner basis theory for parametric polynomial ideals is explored with the main objec- tive of nfinicking the Groebner basis theory for ideals. Given a parametric polynomial ideal, its basis is a comprehensive GrSbner basis if and only if for every specialization of its parameters in a given field, the specialization of the basis is a GrSbnerbasis of the associated specialized polynomial ideal. For various specializations of parameters, structure of specialized ideals becomes qualitatively different even though there are significant relationships as well because of finiteness properties. Key concepts foundational to GrSbner basis theory are reexamined and/or further developed for the parametric case： （i） Definition of a comprehensive Groebner basis, （ii） test for a comprehensive GrSbner basis, （iii） parameterized rewriting, （iv） S-polynomials among parametric polynomials, （v） completion algorithm for directly computing a comprehensive Groebner basis from a given basis of a parametric ideal. Elegant properties of Groebner bases in the classical ideal theory, such as for a fixed admissible term ordering, a unique GrSbner basis can be associated with every polynomial ideal as well as that such a basis can be computed from any Groebner basis of an ideal, turn out to be a major challenge to generalize for parametric ideals; issues related to these investigations are explored. A prototype implementation of the algorithm has been successfully tried on many examples from the literature.
基金supported by the National Nature Science Foundation of China under Grant Nos.11371356 and 61121062
文摘A complete solution classification of the perspective-three-point(P3P) problem is given by using the Gr?bner basis method. The structure of the solution space of the polynomial system deduced by the P3P problem can be obtained by computing a comprehensive Gr?bner system. Combining with properties of the generalized discriminant sequences, the authors give the explicit conditions to determine the number of distinct real positive solutions of the P3P problem. Several examples are provided to illustrate the effectiveness of the proposed conditions.
基金supported by the National Key Basic Research Program of China under Grant Nos.2013CB834203 and 2011CB302400the National Nature Science Foundation of China under Grant Nos.11301523,11371356,61121062+1 种基金the Strategic Priority Research Program of the Chinese Academy of Sciences under Grant No.XDA06010701IEE’s Research Project on Cryptography under Grant Nos.Y3Z0013102,Y3Z0018102,and Y4Z0061A02
文摘Some techniques using linear algebra was introduced by Faugore in F4 to speed up the reduction process during Grobner basis computations. These techniques can also be used in fast implementations of F5 and some other signature-based Grobner basis algorithms. When these techniques are applied, a very important step is constructing matrices from critical pairs and existing polynomials by the Symbolic Preprocessing function （given in F4）. Since multiplications of monomials and polynomials are involved in the Symbolic Preprocessing function, this step can be very costly when the number of involved polynomials/monomials is huge. In this paper, multiplications of monomials and polynomials for a Boolean polynomial ring are investigated and a specific method of implementing the Symbolic Preprocessing function over Boolean polynomial rings is reported. Many examples have been tested by using this method, and the experimental data shows that the new method is very efficient.
基金supported by National Key Basic Research Project of China (Grant No.2011CB302400)National Natural Science Foundation of China (Grant Nos. 10971217 and 61121062)
文摘In 2002, Faugere presented the famous F5 algorithm for computing GrSbner basis where two cri- teria, syzygy criterion and rewritten criterion, were proposed to avoid redundant computations. He proved the correctness of the syzygy criterion, but the proof for the correctness of the rewritten criterion was left. Since then, F5 has been studied extensively. Some proofs for the correctness of F5 were proposed, but these proofs are valid only under some extra assumptions. In this paper, we give a proof for the correctness of F5B, an equivalent version of F5 in Buchberger＇s style. The proof is valid for both homogeneous and non-homogeneous polynomial systems. Since this proof does not depend on the computing order of the S-pairs, any strategy of selecting S-pairs could be used in F5B or F5. Furthermore, we propose a natural and non-incremental variant of F5 where two revised criteria can be used to remove almost all redundant S-pairs.
文摘Bokut, Chen and Liu in 2010 gave a Composition-Diamond lemma for dialge- bras. In this paper, by introducing an arbitrary monomial-center ordering, we give a new Composition-Diamond lemma for dialgebras which makes the two conditions in Bokut, Chen and Liu＇s result equivalent. The new lemma is more useful and convenient than the one Bokut, Chen and Liu got. We show that every ideal of the free dialgebra generated by a set X has a unique reduced GrSbner-Shirshov basis. As applications, we give a method to find normal forms of elements of an arbitrary disemigroup, in particular, two Zhuchoks＇ normal forms of the free commutative disemigroups and the free abelian disemigroups, and normal forms of the free left （right） commutative disemigroups.
文摘A finite GrSbner-Shirshov basis is constructed for the plactic algebra of rank 3 over a field K. It is also shown that plactic algebras of rank exceeding 3 do not have finite GrSbner-Shirshov bases associated to the natural degree-lexicographic ordering on the corresponding free algebra. The latter is in contrast with the case of a strongly related class of algebras, called Chinese algebras.
文摘In this paper, we construct the GrSbner-Shirshov bases for degenerate Ringel- Hall algebras of types A and G2 from the multiplication formulas of the corresponding generic extension monoid algebras.
基金supported by the National Natural Science Foundation of China under Grant Nos.11101185 and 11171133
文摘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.
基金Acknowledgements The authors thank the anonymous referees for their constructive comments and suggestions. This work was supported in part by the National Natural Science Foundation of China （Grant No. 11271040）.
文摘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 GrSbner bases will terminate. Also the relative Gr6bner bases exist under the condition. Finally, we prove the algorithm for computation of the bivariate dimension polynomials in difference-differential modules terminates.
基金supported by the National Science Foundation of China under Grant No.11171133the Open Fund of Automated Reasoning and Cognition Key Laboratory of Chongqing under Grant No.CARC2014001
文摘In this paper,the authors first apply the Fitzpatrick algorithm to multivariate vectorvalued osculatory rational interpolation.Then based on the Fitzpatrick algorithm and the properties of an Hermite interpolation basis,the authors present a Fitzpatrick-Neville-type algorithm for multivariate vector-valued osculatory rational interpolation.It may be used to compute the values of multivariate vector-valued osculatory rational interpolants at some points directly without computing the interpolation function explicitly.
基金supported by the National Natural Science Foundation of China under Grant No.11271040Science and Technology Foundation of Gui Zhou Province LKM[2013]16
文摘Pan and Wang presented a method for computing uniform GrSbner bases for certain ide- als generated by polynomials with parametric exponents in 2006, and two criteria were proposed to determine if a uniform GrSbner basis can be obtained. This paper gives a new algorithmic approach for computing tile uniform GrSbner basis such that Pan and Wang＇s method could be concluded as a special case. The authors use the method of reduced term order under ring homomorphisnl to get the reduced uniform GrSbner basis. Also the authors point and correct a mistake in Pan and Wang＇s method. The result is a generalization of approach of Pan and Wang and one could compute the uniform GrSbner basis more efficiently by the new approach.
文摘In this paper, we find Hall-Shirshov type bases for free pre-Lie algebras. We show that Segal＇s basis of a free pre-Lie algebra is a type of these bases. We give a nonassociative GrSbner-Shirshov basis S for a free pre-Lie algebra such that Irr（S） is a monomial basis （called normal words） of a free pre-Lie algebra, where Irr（S） is the set of all nonassociative words, not containing maximal nonassociative words of polynomials from S. We establish the Composition-Diamond lemma for free pre-Lie algebras over the basis of normal words and the degree breadth lexicographic ordering.
