An Improvement for GVW

Gao, et al.(2015) gave a simple algorithm to compute Gr?bner bases named GVW. It can be used to compute Gr?bner bases for both ideals and syzygies at the same time, and the latter plays an important role in free resolutions in homological algebra. In GVW algorithms the authors need to compute all the J-pairs firstly and then use GVW criterion(which refers the criterions used in GVW) to determine which one is useless or which one the authors should do top-reduction. In this paper, based on the st...     

Speeding Up the GVW Algorithm via a Substituting Method

Journal of Systems Science and Complexity - The GVW algorithm is an efficient signature-based algorithm for computing Gröbner bases. In this paper, the authors consider the implementation of...     

Comprehensive Gröbner basis theory for a parametric polynomial ideal and the associated completion algorithm

Gröbner basis theory for parametric polynomial ideals is explored with the main objective of mimicking the Gröbner basis theory for ideals. Given a parametric polynomial ideal, its basis is a comprehensive Gröbner basis if and only if for every specialization of its parameters in a given field, the specialization of the basis is a Gröbner basis 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 Gröbner basis theory are reexamined and/or further developed for the parametric case: (i) Definition of a comprehensive Gröbner basis, (ii) test for a comprehensive Gröbner basis, (iii) parameterized rewriting, (iv) S-polynomials among parametric polynomials, (v) completion algorithm for directly computing a comprehensive Gröbner basis from a given basis of a parametric ideal. Elegant properties of Gröbner bases in the classical ideal theory, such as for a fixed admissible term ordering, a unique Gröbner basis can be associated with every polynomial ideal as well as that such a basis can be computed from any Gröbner 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.     

On computing uniform Gröbner bases for ideals generated by polynimials with parametric exponents

Pan and Wang presented a method for computing uniform Gr?bner bases for certain ideals generated by polynomials with parametric exponents in 2006,and two criteria were proposed to determine if a uniform Gr?bner basis can be obtained.This paper gives a new algorithmic approach for computing the uniform Gr?bner 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 homomorphism to get the reduced uniform Gr?bner 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 Gr?bner basis more efficiently by the new approach.     

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.     

Normalization in Riemann Tensor Polynomial Ring

It is one of the oldest research topics in computer algebra to determine the equivalence of Riemann tensor indexed polynomials. However, it remains to be a challenging problem since Grbner basis theory is not yet powerful enough to deal with ideals that cannot be finitely generated. This paper solves the problem by extending Grbner basis theory. First, the polynomials are described via an infinitely generated free commutative monoid ring. The authors then provide a decomposed form of the Grbner basis of the defining syzygy set in each restricted ring. The canonical form proves to be the normal form with respect to the Grbner basis in the fundamental restricted ring, which allows one to determine the equivalence of polynomials. Finally, in order to simplify the computation of canonical form, the authors find the minimal restricted ring.     

THE λ-GROBNER BASES UNDER POLYNOMIAL COMPOSITION

Polynomial composition is the operation of replacing variables in a polynomial with other polynomials. λ-Grgbner basis is an especial Grobner basis. The main problem in the paper is： when does composition commute with λ-Grobner basis computation？ We shall answer better the above question. This has a natural application in the computation of λ-Grobner bases.     

On implementing the symbolic preprocessing function over Boolean polynomial rings in Gröbner basis algorithms using linear algebra

Some techniques using linear algebra was introduced by Faugère in F4 to speed up the reduction process during Gr?bner basis computations.These techniques can also be used in fast implementations of F5 and some other signature-based Gr?bner 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.     

Solving the perspective-three-point problem using comprehensive Gröbner systems

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.     

Comprehensive G?bner Basis Theory for a Parametric Polynomial Ideal and the Associated Completion Algorithm

Gr?bner basis theory for parametric polynomial ideals is explored with the main objective of mimicking the Gr?bner basis theory for ideals. Given a parametric polynomial ideal, its basis is a comprehensive Gr?bner basis if and only if for every specialization of its parameters in a given field, the specialization of the basis is a Gr?bner basis 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 Gr?bner basis theory are reexamined and/or further developed for the parametric case:(i) Definition of a comprehensive Gr?bner basis,(ii) test for a comprehensive Gr?bner basis,(iii) parameterized rewriting,(iv) S-polynomials among parametric polynomials,(v) completion algorithm for directly computing a comprehensive Gr?bner basis from a given basis of a parametric ideal. Elegant properties of Gr?bner bases in the classical ideal theory, such as for a fixed admissible term ordering,a unique Gr?bner basis can be associated with every polynomial ideal as well as that such a basis can be computed from any Gr?bner 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.     

The F5 algorithm in Buchberger’s style

The famous F5 algorithm for computing Gröbner basis was presented by Faugère in 2002. The original version of F5 is given in programming codes, so it is a bit difficult to understand. In this paper, the F5 algorithm is simplified as F5B in a Buchberger’s style such that it is easy to understand and implement. In order to describe F5B, we introduce F5-reduction, which keeps the signature of labeled polynomials unchanged after reduction. The equivalence between F5 and F5B is also shown. At last, some versions of the F5 algorithm are illustrated.     

A New Signature-Based Algorithms for Computing Gr?bner Bases

Gao,Volny and Wang(2010) gave a simple criterion for signature-based algorithms to compute Grobner bases.It gives a unified frame work for computing Grobner bases for both ideals and syzygies,the latter is very important in free resolutions in homological algebra.Sun and Wang(2011) later generalized the GVW criterion to a more general situation(to include the F5 Algorithm).Signature-based algorithms have become increasingly popular for computing Grobner bases.The current paper introduces a concept of factor pairs that can be used to detect more useless J-pairs than the generalized GVW criterion,thus improving signature-based algorithms.     

A New Algorithm for Computing the Extended Hensel Construction of Multivariate Polynomials

This paper presents a new algorithm for computing the extended Hensel construction(EHC) of multivariate polynomials in main variable x and sub-variables u_1, u_2, ···, u_m over a number field K. This algorithm first constructs a set by using the resultant of two initial coprime factors w.r.t. x, and then obtains the Hensel factors by comparing the coefficients of x~i on both sides of an equation. Since the Hensel factors are polynomials of the main variable with coefficients in fraction field K(u_1, u_2, ···, u_m), the computation cost of handling rational functions can be high. Therefore,the authors use a method which multiplies resultant and removes the denominators of the rational functions. Unlike previously-developed algorithms that use interpolation functions or Gr?bner basis, the algorithm relies little on polynomial division, and avoids multiplying by different factors when removing the denominators of Hensel factors. All algorithms are implemented using Magma, a computational algebra system and experiments indicate that our algorithm is more efficient.     

一种语言模型的精确学习方法

语言模型具有很好的可解释性，但面对复杂问题时，其精确性不能满足要求。为此结合微粒群算法和遗传算法各自的演化特点，采用两阶段学习策略。对语言模型进行分层演化，首先利用微粒群算法优化各输入变量的语言值数目及对应的模糊集参数。形成候选规则集，再应用遗传算法选择规则，得到精确的语言模型．该方法几乎无需先验知识，可直接从样本数据获取语言模型，应用函数近似为例说明其有效性。     

DENOISING AND HARMONIC DETECTION USING NONORTHOGONAL WAVELET PACKETS IN INDUSTRIAL APPLICATIONS

New industrial applications call for new methods and new ideas in signal analysis. Wavelet packets are new tools in industrial applications and they have just recently appeared in projects and patents. In training neural networks, for the sake of dimensionality and of ratio of time, compact information is needed. This paper deals with simultaneous noise suppression and signal compression of quasi-harmonic signals. A quasi-harmonic signal is a signal with one dominant harmonic and some more sub harmonics in superposition. Such signals often occur in rail vehicle systems, in which noisy signals are present. Typically, they are signals which come from rail overhead power lines and are generated by intermodulation phenomena and radio interferences. An important task is to monitor and recognize them. This paper proposes an algorithm to differentiate discrete signals from their noisy observations using a library of nonorthonormal bases. The algorithm combines the shrinkage technique and techniques in regression analysis using Shannon Entropy function and Cross Entropy function to select the best discernable bases. Cosine and sine wavelet bases in wavelet packets are used. The algorithm is totally general and can be used in many industrial applications. The effectiveness of the proposed method consists of using as few as possible samples of the measured signal and in the meantime highlighting the difference between the noise and the desired signal. The problem is a difficult one, but well posed. In fact, compression reduces the level of the measured noise and undesired signals but introduces the well known compression noise. The goal is to extract a coherent signal from the measured signal which will be “well represented” by suitable waveforms and a noisy signal or incoherent signal which cannot be “compressed well” by the waveforms. Recursive residual iterations with cosine and sine bases allow the extraction of elements of the required signal and the noise. The algorithm that has been developed is utilized as a filter to extract features for training neural networks. It is currently integrated in the inferential modelling platform of the unit for Advanced Control and Simulation Solutions within ABB’s industry division. An application using real measured data from an electrical railway line is presented to illustrate and analyze the effectiveness of the proposed method. Another industrial application in fault detection, in which coherent and incoherent signals are univocally visible, is also shown.     

城市环境质量综合评价的多目标决策理想区间法

为了科学地评价城市环境质量,并使评价方法更符合实际,对多目标决策理想点法进行改进,把评价标准处理成理想区间的形式,并用遗传投影寻踪方法来确定权重,提出了一种新的评价方法———多目标决策理想区间法(MODMIIM).介绍了MODMIIM的原理,给出了它的构成方法和具体评价公式,并用MODMIIM对宣州市环境质量进行了综合评价.结果表明,该方法较好地反映了实际环境质量分级的区间界限,解决了不相容指标权重分配问题,使评价结果更合理,是一种有效的城市环境质量综合评价方法.     

An algorithm for the discretization of an ideal projector

Ideal interpolation is a generalization of the univariate Hermite interpolation. It is well known that every univariate Hermite interpolant is a pointwise limit of some Lagrange interpolants. However, a counterexample provided by Shekhtman Boris shows that, for more than two variables, there exist ideal interpolants that are not the limit of any Lagrange interpolants. So it is natural to consider: Given an ideal interpolant, how to find a sequence of Lagrange interpolants (if any) that converge to it. The authors call this problem the discretization for ideal interpolation. This paper presents an algorithm to solve the discretization problem. If the algorithm returns “True”, the authors get a set of pairwise distinct points such that the corresponding Lagrange interpolants converge to the given ideal interpolant.     

M/G/1排队系统的性能灵敏度估计与仿真

对具有一般分布的排队系统-M／G／l排队系统给出了一种通过其嵌入Markov链来计算系统势能及性能导数的仿真算法。由于该算法基于分析系统的一条单一样本轨道，故可直接用于系统的控制与优化。最后提供一个数值例子来表明该算法的应用。     

基于两点外推法的跟踪滤波器启始方法研究

对于多目标跟踪系统，滤波器的起始波门的设计是一个关键问题，首先给出了利用量测标准差与采样周期比值的相对大小来确定滤波器启始的方法，然后利用目标速度极限的先验信息构造环状波门，并考虑量测量噪声对环状波门的影响，利用矩阵范数特性，导出一种更精细的基于两点外推的滤波器启始法，仿真结果表明利用本文方法的构造出的波门的置信区间比其他两种方法所构作出的更为合理。     

协同过滤推荐算法研究: 考虑在线评论情感倾向

协同过滤推荐算法通常是基于兴趣相似的用户行为来实现个性化推荐, 其核心义用户之间的兴趣相似度. 本文在传统的协同过滤推荐算法基础上, 考虑在线评论对用似度识别的影响. 在混合商品推荐中, 粗粒度识别评论情感极性; 而在同类商品推荐中, 细粒别每个商品特征的情感极性. 如果用户对产品的某个特征评价次数大于平均次数, 表明用户对征较关注; 如果对产品的某个特征评价低于平均评价, 表明用户对该特征较挑剔. 进而根据用户评论来建立用户偏好模型, 用户在评论中反映出来的相似度越高, 表明用户之间的偏好越. 实验表明, 同传统的协同过滤算法相比, 基于在线评论情感分析的用户协同过滤算法在率和召回率指标上有显著提升.