GVW algorithm over principal ideal domains

GVW algorithm was given by Gao, Wang, and Volny in computing a Gröbner bases for ideal in a polynomial ring, which is much faster and more simple than F5. In this paper, the authors generalize GVW algorithm and present an algorithm to compute a Gröbner bases for ideal when the coefficient ring is a principal ideal domain.     

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.     

An Improvement for GVW

Journal of Systems Science and Complexity - 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...     

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.     

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...     

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.     

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.     

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.     

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.     

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.     

A Survey on Algorithms for Computing Comprehensive Gr?bner Systems and Comprehensive Gr?bner Bases

Journal of Systems Science and Complexity - Weispfenning in 1992 introduced the concepts of comprehensive Gröbner system/basis of a parametric polynomial system, and he also presented an...     

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.     

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.     

大规模过程系统优化的简约空间SQP算法

提出了一种适用于大规模过程系统优化的简约空间ＳＱＰ方法．简约空间ＳＱＰ算法用变量分解的方法消去非独立变量和等式约束，以降低ＱＰ子问题的维数，使每次迭代的ＱＰ子问题求解只在零空间中进行．正交基分解与标准正交基分解相比，具有同样的收敛性能，但由于避免了ＱＲ分解，故进一步减少了计算量，是大规模过程系统优化中很有前途的算法．优化算例说明了这一方法的有效性．     

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

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

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.     

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

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

基于燃气轮机转速直接型自适应模糊控制器的设计

针对发电用单轴微型燃气轮机这样大型复杂且具有极强非线性的热能动力系统，提出了适用的燃机转子转速自适应模糊控制方法，将加速度限制包含在规则中。从而构建了新的控制结构。理论证明，利用在线调整算法改变模糊规则基使控制系统达到了全局稳定。数据仿真表明，控制方案对燃气轮机的转速控制取得了很好的效果，具有实际应用价值。方法适用于提出一类具有单输入单输出的非线性系统。     

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

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

用于基因预测的自适应滤波器的仿真研究

根据蛋白质编码区周期3行为,设计了两种用于基因外显子预测的窄带自适应滤波器,对基因序列进行滤波处理,获得了外显子的预测曲线;在此基础上,分析了最小均方误差（LMS）算法和递推最小二乘（RLS）算法用于基因预测的异同,通过比较滤波器参数和仿真曲线,表明递推最小二乘算法用于基因外显子预测优于最小均方误差算法。