用于求解正则(3,4)-SAT实例集的修正警示传播算法

利用极小不可满足公式的临界特性,可以将任意的一个3-CNF公式多项式时间归约转换为一个正则(3,4)-CNF公式,从而得到一个保留NP完全性的正则(3,4)-SAT问题。警示传播算法(Warning Propagation,WP)在归约转换后的正则(3,4)-SAT实例集上高概率收敛,但在任意一个实例上都无法判断公式的可满足性,因此算法求解失效。对于一个归约转换后的正则(3,4)-CNF公式,每一变元出现的正负次数之差具有趋于稳定的结构特征,基于该特征,提出基于变元正负出现次数规则的WP算法来求解归约转换后的正则(3,4)-SAT实例。实验结果表明,修正的WP算法对正则公式的可满足性判定有效,从而可以利用公式的正则性特征进一步研究WP算法的收敛性特征条件。     

方程的求根公式和根的展开式及其算法

本文获得了方程的求根公式及其根的级数展开式，并得到了求根的算法，同时，建立了求根问题的一个新方法——函数零点和方程根公式表示法。     

命题公式真值表的生成算法

真值表是命题逻辑理论中的一个重要概念,利用它可以求命题公式的主范式、判定命题公式的类型以及进行命题逻辑的推理等。本文给出了任意命题公式真值表的生成算法,为利用计算机解决命题逻辑中的其它问题奠定了基础.     

图的树分解算法及其应用

一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。     

基于最佳位分配技术的图象编码

提出了一个新的位分配算法，它可以有效地分配一个给定的位的限额给任意不同的量化器集合.这种算法产生一个最佳或接近最佳位分配，它允许位分配集合值被限制成非负整数.该算法用在小波图象编码中，实验表明,这种算法是十分有效的.     

B样条曲线同时插入多个节点的快速算法

基于离散B样条的一个新的递推公式，提出B样条曲线同时插入多个节点的新算法。不同于Cohen等插入节点的Oslo算法，本算法用新的方法离算离散B样条，求每个离散B样条的值只需O(1)的运算量，从而使本算法高效，其时间复杂性为O(sk n)，其中k为B样条曲线的阶，n k 1为原节点数，s为新插入节点的个数,本算法的通用性强，适用于端点插值的和非端点插值的B样条曲线，可同时在曲线定义域内外的任意位置上插入任意个节点。     

用泛函网络求任意高阶多项式的近似根

本文提出了一种新的基于泛函网络的多项式求根模型及学习算法，而泛函网络的参数利用解线性不等式组，可得到所求任意高阶多项式近似根的一般参数表达式。文章还讨论了基于泛函网络的多项式求根学习算法实现的一些技术问题，相对传统方法，能够有效地获得任意多项式对应根的参数表达式。     

多边形填充的扫描线算法及其实现

多变形填充算法是图形学中一个比较复杂的算法。对多边形填充算法进行了介绍,用VC 实现了X-Y扫描线算法,该算法可以对任意形状的多边形(包括自相交的多边形)进行填充。     

基于Cayley图的三维六度环面网络研究

提出了一种三维六度环面Cayley图网络模型.针对该网络模型,给出了一种简单的三维节点编址方案,并利用该编址方案得到了任意两个节点间的最短距离公式;开发了一种简单的分布式最优路由算法,该算法可以运行于网络中的任意节点,可以建立任意两点之间的最短路由路径;基于陪集图(coset graph)理论,给出了一种新型的广播通信算法,并对该算法的效率进行了分析;给出了三维六度环绕网络模型直径的界限值.     

NURBS曲线和曲面的递推矩阵及其应用

本文运用Ｔｏｅｐｌｉｔｚ矩阵，导出了任意非均匀Ｂ样条的递推矩阵公式；提出了一个计算非均匀Ｂ样条基矩阵的新方法，该递推矩阵公式即可以用于ＮＵＲＢＳ曲线和曲面的分析计算，也可以用于Ｂｅｚｉｅｒ，均匀和非均匀Ｂ样条曲线及曲面的分析计算。     

Root isolation of zero-dimensional polynomial systems with linear univariate representation

In this paper, a linear univariate representation for the roots of a zero-dimensional polynomial equation system is presented, where the complex roots of the polynomial system are represented as linear combinations of the roots of several univariate polynomial equations. An algorithm is proposed to compute such a representation for a given zero-dimensional polynomial equation system based on Gröbner basis computation. The main advantage of this representation is that the precision of the roots of the system can be easily controlled. In fact, based on the linear univariate representation, we can give the exact precisions needed for isolating the roots of the univariate equations in order to obtain roots of the polynomial system with a given precision. As a consequence, a root isolating algorithm for a zero-dimensional polynomial equation system can be easily derived from its linear univariate representation.     

Discussion on polynomials having polynomial iterative roots

In this paper, we discuss polynomial mappings which have iterative roots of the polynomial form. We apply the computer algebra system Singular to decompose algebraic varieties and finally find a condition under which polynomial functions have quadratic iterative roots of quadratic polynomial form. This condition is equivalent to, but simpler than Schweizer and Sklar’s and more convenient than Strycharz–Szemberg and Szemberg’s. We further find all polynomial functions which have cubic iterative roots of the quadratic polynomial form and compute all those iterative roots. Moreover, we find all 2-dimensional homogeneous polynomial mappings of degree 2 which have iterative roots of the polynomial form and obtain expressions of some iterative roots.     

The fastest exact algorithms for the isolation of the real roots of a polynomial equation

This paper discusses a set of algorithms which, given a polynomial equation with integer coefficients and without any multiple roots, uses exact (infinite precision) integer arithmetic and the Vincent-Uspensky-Akritas theorem to compute intervals containing the real roots of the polynomial equation. Theoretical computing time bounds are developed for these algorithms which are proven to be the fastest existing; this fact is also verified by the empirical results which are included in this article.     

A computational algorithm for inners

A Gaussian elimination algorithm is proposed to compute the determinants of inners of certain types of matrices. This algorithm applies to the clustering of roots as well as to the roots distribution of a given polynomial. Several examples on stability, relative stability, and aperiodicity for both continuous and discrete systems are presented.     

一种基于泛函网络的多项式Euclidean算法

提出一种基于泛函网络的多项式Euclidean计算新模型,给出一种基于泛函网络的多项式Euclidean新算法。网络的泛函参数利用解线性方程组方法来完成。相对于传统方法,该方法不但能够快速地获得所求多项式问题的精确解,而且可获得所求多项式问题的近似解。计算机仿真结果表明,该算法十分有效、可行,可以看作是对传统的Euclidean算法的一种推广。该算法将在计算机数学、代数密码学等方面有着广泛的应用。     

基于多项式根最大模求解的二分搜索算法

传统多项式根最大模求解算法的求解效率低、计算复杂.针对该问题,提出一种基于多项式根的最大模求解的二分搜索算法.该算法通过选取模的上下界确定初始搜索区间,利用判定定理判断多项式的根与单位圆的关系,从而求得多项式任意精度的最大模.仿真结果表明,该算法收敛速度快、求解精度高.     

一类求解方程全部根的改进差分进化算法

求解高次实复系数代数方程的根,提出了一种改进的差分进化算法,计算种群中每个个体的适应度并排序,利用二分之一规则选取个体,并引入自适应差分变异算子和进化策略重组算子.对5个高次代数方程求根问题进行了数值计算,结果表明,该算法能求解任意次数的实复系数代数方程的全部根,而且求解精度高,收敛速度快,是求解代数方程根的一种有效算法.     

Serre’s reduction of linear partial differential systems with holonomic adjoints

Given a linear functional system (e.g., an ordinary/partial differential system, a differential time-delay system, a difference system), Serre’s reduction aims at finding an equivalent linear functional system which contains fewer equations and fewer unknowns. The purpose of this paper is to study Serre’s reduction of underdetermined linear systems of partial differential equations with either polynomial, formal power series or locally convergent power series coefficients, and with holonomic adjoints in the sense of algebraic analysis. We prove that these linear partial differential systems can be defined by means of only one linear partial differential equation. In the case of polynomial coefficients, we give an algorithm to compute the corresponding equation.     

Coupling of optimal variation of parameters method with Adomian’s polynomials for nonlinear equations representing fluid flow in different geometries

In this study, we describe a modified analytical algorithm for the resolution of nonlinear differential equations by the variation of parameters method (VPM). Our approach, including auxiliary parameter and auxiliary linear differential operator, provides a computational advantage for the convergence of approximate solutions for nonlinear boundary value problems. We consume all of the boundary conditions to establish an integral equation before constructing an iterative algorithm to compute the solution components for an approximate solution. Thus, we establish a modified iterative algorithm for computing successive solution components that does not contain undetermined coefficients, whereas most previous iterative algorithm does incorporate undetermined coefficients. The present algorithm also avoid to compute the multiple roots of nonlinear algebraic equations for undetermined coefficients, whereas VPM required to complete calculation of solution by computing roots of undetermined coefficients. Furthermore, a simple way is considered for obtaining an optimal value of an auxiliary parameter via minimizing the residual error over the domain of problem. Graphical and numerical results reconfirm the accuracy and efficiency of developed algorithm.