Computing Sparse GCD of Multivariate Polynomials via Polynomial Interpolation

The problem of computing the greatest common divisor (GCD) of multivariate polynomials, as one of the most important tasks of computer algebra and symbolic computation in more general scope, has been studied extensively since the beginning of the interdisciplinary of mathematics with computer science. For many real applications such as digital image restoration and enhancement, robust control theory of nonlinear systems, L₁-norm convex optimization in compressed sensing techniques, as well as algebraic decoding of Reed-Solomon and BCH codes, the concept of sparse GCD plays a core role where only the greatest common divisors with much fewer terms than the original polynomials are of interest due to the nature of problems or data structures. This paper presents two methods via multivariate polynomial interpolation which are based on the variation of Zippel’s method and Ben-Or/Tiwari algorithm, respectively. To reduce computational complexity, probabilistic techniques and randomization are employed to deal with univariate GCD computation and univariate polynomial interpolation. The authors demonstrate the practical performance of our algorithms on a significant body of examples. The implemented experiment illustrates that our algorithms are efficient for a quite wide range of input.     

Factorization for n-D Polynomial Matrices over Arbitrary Coefficient Field

Multivariate(n-D) polynomial matrix factorization is one of important research contents in multidimensional(n-D) systems, circuits, and signal processing. In this paper, several results on n-D polynomial matrices factorization over arbitrary coefficient fields are proved. Based on these results,generalizations of some results on general matrix factorization are obtained for given n-D polynomial matrices whose maximal order minors or lower order minors satisfy certain conditions. The proposed results fit for arbitrary coefficient field and have a wide range of application.     

On Minor Left Prime Factorization Problem for Multivariate Polynomial Matrices

A new necessary and sufficient condition for the existence of minor left prime factorizations of multivariate polynomial matrices without full row rank is presented. The key idea is to establish a relationship between a matrix and any of its full row rank submatrices. Based on the new result,the authors propose an algorithm for factorizing matrices and have implemented it on the computer algebra system Maple. Two examples are given to illustrate the effectiveness of the algorithm, and experiment...     

On Rank Factorizations and Factor Prime Factorizations for Multivariate Polynomial Matrices

In this paper, rank factorizations and factor left prime factorizations are studied. The authors prove that any polynomial matrix with full row rank has factor left prime factorizations. And for a class of polynomial matrices, the authors give an algorithm to decide whether they have rank factorizations or factor left prime factorizations and compute these factorizations if they exist.     

New Results on the Equivalence of Bivariate Polynomial Matrices

This paper investigates the equivalence problem of bivariate polynomial matrices. A necessary and sufficient condition for the equivalence of a square matrix with the determinant being some power of a univariate irreducible polynomial and its Smith form is proposed. Meanwhile, the authors present an algorithm that reduces this class of bivariate polynomial matrices to their Smith forms, and an example is given to illustrate the effectiveness of the algorithm. In addition, the authors generalize ...     

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.     

Computing the Determinant of a Matrix with Polynomial Entries by Approximation

Computing the determinant of a matrix with the univariate and multivariate polynomial entries arises frequently in the scientific computing and engineering fields. This paper proposes an effective algorithm to compute the determinant of a matrix with polynomial entries using hybrid symbolic and numerical computation. The algorithm relies on the Newton’s interpolation method with error control for solving Vandermonde systems. The authors also present the degree matrix to estimate the degree of variables in a matrix with polynomial entries, and the degree homomorphism method for dimension reduction. Furthermore, the parallelization of the method arises naturally.     

构造极小广播网络的新方法

广播是指从网络中某一成员开始 ,将消息传递给网络中其余成员的过程 .极小广播网络就是指能在最短时间内广播一条消息的通讯网络 .本文主要讨论一种构造极小广播网络的新方法 ,这种方法在大多数情况下改进了极小广播网络的最少边数的上界.     

求最小费用最大流的改进标号法

针对现有网络最小费用最大流算法存在的针对性差、步骤繁复、计算量大的问题,根据赋权有向图的最短路算法,提出并证明了一种寻找最小费用增广链的改进标号法.此方法可以直接在网络图上使用,避免了传统方法中需要反复将网络图转化为赋权有向图的操作.将此方法应用到求网络最小费用最大流的计算中,可以简化计算过程,提高运算效率.     

VerifyRealRoots:A Matlab Package for Computing Verified Real Solutions of Polynomials Systems of Equations and Inequalities

VerifyRealRoots is a Matlab package for computing and verifying real solutions of polynomial systems of equations and inequalities. It calls Bertini or MMCRSolver for finding approximate real solutions and then applies AINLSS to verify the existence of a regular solution of a polynomial system or applies AINLSS2(AIVISS) to verify the existence of a double solution(a singular solution of an arbitrary multiplicity) of a slightly perturbed polynomial system.     

网络O-D矩阵估计的两阶段交叉口回归分析方法

通过分析交通网络O-D矩阵估计与交叉口O-D矩阵估计问题的关系，获得从网络到交叉口O-D矩阵估计问题的转换条件，由此构建网络O-D矩阵估计的两阶段交叉口回归分析方法。该方法首先求解“叉点具有产生、消失流量的交叉口O-D矩阵估计问题”分离起讫点的通过流、产生流和消失流，然后根据网络构造交叉口，并求解“叉点无产生、消失流量的交叉口O-D矩阵估计问题”获得需要估计的网络O-D矩阵。该方法以路段观测交通流量为基础进行估计，无须进行交通分配等辅助手段。计算分析表明，该方法能获得较为满意的估计结果。     

Ritt-Wu Characteristic Set Method for Laurent Partial Differential Polynomial Systems

Journal of Systems Science and Complexity - In this paper, a Ritt-Wu characteristic set method for Laurent partial differential polynomial systems is presented. The concept of Laurent regular...     

New Implicit Enumeration Method for Polynomial 0-1 Programming

A new implicit enumeration method for polynomial zero-one programming is proposed in this article. By adopting the p-norm surrogate constraint method, a polynomial zero-one programming problem with multiple constraints can be converted into an equivalent polynomial zero-one programming problem with a single surrogate constraint. A new solution scheme is then devised to take the advantage of this prominent feature in carrying out the “fathoming” procedure and the “backtrack” procedure in a searching process of an implicit enumeration. We demonstrate the efficiency of this new algorithm by some promising computational results. Finally, we conclude by proposing certain topics for future research.     

模糊互补判断矩阵的排序方法研究

指出了模糊互补判断矩阵的一种常用排序方法的不足 ,提出了模糊互补判断矩阵排序的一种新方法 ,并研究了该法所具有的一些优良性质。该法不仅能充分利用模糊一致性判断矩阵的优良特性及其判断信息 ,而且可以直接由原模糊互补判断矩阵求出较为理想的排序向量 ,所需计算量较小。所得方案排序权重属于正常范围 ,因而更为合理、实用。最后进行了算例分析。     

层次分析法正互反矩阵灵敏度的Hadamard乘积分析法

定义了Ⅱ－标准形和Ⅲ－标准形，证明了任一正互反矩阵均可唯一分解为任一种标准形和一个一致性矩阵的Ｈａｄａｍａｒｄ乘积。利用这种分解进行了正互反矩阵的灵敏度分析。结果表明由被扰动矩阵和扰动矩阵的最小偏差法（ＬＤＭ）和对数最小二乘法（ＬＬＳＭ）排序向量可以得到扰动后矩阵在相应方法下的排序向量，而无需计算扰动后矩阵。     

一种计算复杂网络可靠性的新方法

修正了RBAP算法和RBAC算法中的错误,提出了一种分析网络可靠性的新方法。这种算法通过构造树的方法产生不交和。     

群组区间数互补判断矩阵偏好信息的一种集结方法

研究了群组区间数互补判断矩阵偏好信息的集结问题。根据误差传递理论,把不确定性的区间数偏好信息转换为确定性的偏好信息,即中值和和极限误差信息,然后利用OWA算子,得到备选方案排序,最后通过算例说明了该方法的可行性和有效性。     

一种基于SOA的自律计算模型与实现方法

通过引入面向服务架构技术,提出一种面向服务的自律计算模型,对自律计算环境的架构和自律单元的设计进行了详细论述,并对计算模型的关键问题——服务装载过程做出改进,解决了服务引用、行为不一致性的问题.实验结果表明,提出的模型使Web服务器节省了平均事务响应时间,提高了平均吞吐量,改进的服务装载过程能增加约10个百分点的服务通过率.服务质量得到有效提高.     

群组判断矩阵排序中的广义最小偏差方法

本文对群组判断矩阵排序提出一种新的广义最小偏差方法。鉴于不同专家所给判断矩阵质量上的差异, 广义最小偏差排序方法对群组判断矩阵进行不同程度的加权处理, 并进行群组一致性检验。     

多项式0-1规划中隐枚举算法的改进及应用

提出了一个求解多项式0-1规划问题的隐枚举算法.通过应用p次范数约束划归,多项式0-1规划问题的多个约束可以被一单一等价约束来替代.利用这一显著特性,新算法在搜寻最优解过程中,能改进探寻(fathoming)和折返(backtrack)策略以提高隐枚举法的计算效率.通过一个算例说明这个新算法的计算步骤并对随机产生的问题进行了测试,得到了较好的结果.