Halley-Like Method with Corrections for the Inclusion of Polynomial Zeros

In this paper we present iteration methods of Halley's type for the simultaneous inclusion of all zeros of a polynomial. Using the concept of the R-order of convergence of mutually dependent sequences, we present the convergence analysis for the total-step and the single-step methods with Newton's corrections. The suggested algorithms possess a great computational efficiency since the increase of the convergence rate is attained without additional calculations. A numerical example is given. Received: June 23, 1998     

Weierstrass-like Methods with Corrections for the Inclusion of Polynomial Zeros

In this paper, we present iterative methods of Weierstress’ type for the simultaneous inclusion of all simple zeros of a polynomial. The main advantage of the proposed methods is the increase of the convergence rate attained by applying suitable correction terms. Using the concept of the R-order of convergence of mutually dependent sequences, we present the convergence analysis for the total-step and the single-step methods. Numerical examples are given.     

Derivative Free Inclusion Methods for Polynomial Zeros

Two iterative methods for the simultaneous inclusion of complex zeros of a polynomial are presented. Both methods are realized in circular interval arithmetic and do not use polynomial derivatives. The first method of the fourth order is composed as a combination of interval methods with the order of convergence two and three. The second method is constructed using double application of the inclusion method of Weierstrass’ type in serial mode. It is shown that its R-order of convergence is bounded below by the spectral radius of the corresponding matrix. Numerical examples illustrate the convergence rate of the presented methods     

Detection and Validation of Clusters of Polynomial Zeros

We consider the task of partitioning the zeros of a real or complex polynomial into clusters and of determining their location and multiplicity for polynomials with coefficients of limited accuracy. We derive computational procedures for the solution of this task which combine symbolic computation with floating-point arithmetic. The validation of the existence ofmzeros in a specified small disk is described.     

Inclusion of Zeros of Nowhere Differentiable n-Dimensional Functions

A method is described for calculating verified error bounds for zeros of a system of nonlinear equations f(x) = 0 with continuous f : R" R". We do not require existence of partial derivatives of f, and the function f may even be known only up to some finite precision > 0.An inclusion may contain infinitely many zeros of f. An example of a continuous but nowhere differentiable function is given.     

Exact Computation of Polynomial Zeros Expressible by Square Roots

In this paper we give an efficient algorithm to find symbolically correct zeros of a polynomial f ∈ R[X] which can be represented by square roots. R can be any domain if a factorization algorithm over R[X] is given, including finite rings or fields, integers, rational numbers, and finite algebraic or transcendental extensions of those. Asymptotically, the algorithm needs O(T_f(d²)) operations in R, where T_f(d) are the operations for the factorization algorithm over R[X] for a polynomial of degree d. Thus, the algorithm has polynomial running time for instance for polynomials over finite fields or the rationals. We also present a quick test for deciding whether a given polynomial has zeros expressible by square roots and describe some additional methods for special cases.     

基于包含度的子图匹配方法

子图匹配是图论中最基本的操作.研究子图匹配的一个变种,即：在一个节点拥有若干元素的大图数据库中,找到与给定查询图结构同构并且对应节点元素的加权集合包含度大于给定值的所有子图,称作基于包含度的子图匹配（subgraph matching with inclusion degree,简称SMID）.该查询能够应用于多种场景,包括论文检索、社区发现、企业招聘等.为高效实现SMID,设计了同时包含节点元素和图结构信息的数据签名与查询签名,在离线处理阶段,利用数据签名为数据图建立动态签名树（DS-Tree）,以加快在线处理时图节点的匹配过程.为解决DS-Tree占用空间大的问题,设计了一种DS-Tree压缩方法,在对查询效率影响不大的情况下减小了索引空间.为进一步加快查询效率,还提出了支配子图查询算法.在真实数据和人工数据上的实验结果表明,所提出的方法在效率和扩展性方面优于现有其他方法.     

多项式数据通路的优化方法

为了实现多项式数据通路的高层次综合,采用有序的、简化的和正则的带权值广义表模型表达该多项式。提出了基于带权值广义表的优化方法,该方法以自顶向下的方式遍历带权值广义表中的节点,迭代地识别其相应的加法割和乘法割,进而形成一个可允许割序列;根据可允许割序列产生相应可调度的数据流图。实验结果表明,采用该方法得到的数据流图与已有方法得到的相比,在延迟上具有一定的优势。     

Toric Newton Method for Polynomial Homotopies

This paper defines a generalization of Newton’s method to deal with solution paths defined by polynomial homotopies that lead to extremal values. Embedding the solutions in a toric variety leads to explicit scaling relations between coefficients and solutions. Toric Newton is a symbolic-numeric algorithm where the symbolic pre-processing exploits the polyhedral structures. The numerical stage uses the additional variables introduced by the homogenization to scale the components of the solution vectors to the complex unit circle. Toric Newton generates appropriate affine charts and enables one to approximate the magnitude of large solutions of polynomial systems.     

On The Convergence Of Some Interval Methods For Simultaneous Computation Of Polynomial Zeros

In this paper we consider the convergence of a certain interval method for simultaneous computation of polynomial zeros. Under the legitimacy of suitable isolation of the roots in a restrictive respective circular disks it is established in a limiting sense a finite positive constant in existence for which convergence is certain. This positive constant which is the limiting convergence factor is dependent on the minimum distance between the zeros of the polynomial. This provides a qualitative information that may be found useful on the occasion the roots are clustered. The climax however, is an introduction of a new interval method and an improved modification of an existing one considered.     

A Modification of Newton's Method for Analytic Mappings Having Multiple Zeros

We propose a modification of Newton's method for computing multiple roots of systems of analytic equations. Under mild assumptions the iteration converges quadratically. It involves certain constants whose product is a lower bound for the multiplicity of the root. As these constants are usually not known in advance, we devise an iteration in which not only an approximation for the root is refined, but also approximations for these constants. Numerical examples illustrate the effectiveness of our approach. Received: August 17, 1998     

Ridge Polynomial神经网络带动量项异步梯度算法的收敛性

将动量项引入到Ridge Polynomial神经网络异步梯度训练算法的误差函数中,有效地改善了算法的收敛效率,并从理论上分析了Ridge Polynomial神经网络的带动量项的异步梯度算法的收敛性,给出了算法的单调性和收敛性(包括强收敛性和弱收敛性)。算法的这些收敛性质对于如何选取学习率和初始权值来进行高效的网络训练是非常重要的。最后通过计算机仿真实验验证了带动量项的异步梯度算法的高效性和理论分析的正确性。     

Kernel Polynomial Method on GPU

The simulation of lattice model systems for quantum materials is one of the most important approaches to understand quantum properties of matter in condensed matter physics. The main task in the simulation is to diagonalize a Hamiltonian matrix for the system and evaluate the electronic density of energy states. Kernel polynomial method (KPM) is one of the promising simulation methods. Because KPM contains a fine-grain recursive part in the algorithm, it is hard to parallelize it under the thread level parallelism such as on a supercomputer or a cluster computer. This paper focuses on methods to parallelize KPM on a massively parallel environment of GPU, aiming to achieve high parallelism for more speedups than the recent CPUs. This paper proposes two implementation methods called the full map and the sliding window methods, and evaluates the performances in the recent GPU platform. To enlarge available simulation sizes and at the same time to enhance the performance, this paper also describes additional optimization techniques depending on the GPU architecture.     

一种匹配Z变换的零点匹配方法

匹配Z变换是将模拟控制器变为数字控制器的一种数字化方法，若模拟控制器的复数零点的虚部ω0大于采样角频率ω8的一半，这时数字控制器的频率特性将会产生严重混叠。本文针对这个问题进行了研究，提出了一种零点匹配方法。     

模糊保险箱的多项式表示方法

在模糊保险箱方案中,通常采用多个干扰点与用户特征点混合构成的集合表示保险箱,这种方法存在多种安全缺陷。为此,提出一种新的保险箱构造方案,该方案利用随机点与用户特征集合构造一个随机多项式,运用该多项式系数表示保险箱。分析结果表明,该方案可以抵抗已知的对模糊保险箱的多种攻击,具有更高的安全性,并能节约存储空间。     

A Polynomial Quantum Algorithm for Approximating the Jones Polynomial

The Jones polynomial, discovered in 1984, is an important knot invariant in topology. Among its many connections to various mathematical and physical areas, it is known (due to Witten) to be intimately connected to Topological Quantum Field Theory ( ). The works of Freedman, Kitaev, Larsen and Wang provide an efficient simulation of by a quantum computer, and vice versa. These results implicitly imply the existence of an efficient (namely, polynomial) quantum algorithm that provides a certain additive approximation of the Jones polynomial at the fifth root of unity, e ^{2π i/5}, and moreover, that this problem is -complete. Unfortunately, this important algorithm was never explicitly formulated. Moreover, the results of Freedman et al. are heavily based on , which makes the algorithm essentially inaccessible to computer scientists. We provide an explicit and simple polynomial quantum algorithm to approximate the Jones polynomial of an n strands braid with m crossings at any primitive root of unity e ^{2π i/k} , where the running time of the algorithm is polynomial in m, n and k. Our algorithm is based, rather than on , on well known mathematical results (specifically, the path model representation of the braid group and the uniqueness of the Markov trace for the Temperley-Lieb algebra). By the results of Freedman et al., our algorithm solves a complete problem. Our algorithm works by encoding the local structure of the problem into the local unitary gates which are applied by the circuit. This structure is significantly different from previous quantum algorithms, which are mostly based on the Quantum Fourier transform. Since the results of the current paper were presented in their preliminary form, these ideas have been extended and generalized in several interesting directions. Most notably, Aharonov, Arad, Eban and Landau give a simplification and extension of these results that provides additive approximations for all points of the Tutte polynomial, including the Jones polynomial at any point, and the Potts model partition function at any temperature and any set of coupling strengths. We hope and believe that the ideas presented in this work will have other extensions and generalizations.     

适用于含公共零点SIMO信道的盲均衡算法

在含公共零点单输入多输出(SIMO)模型的基础上,提出一种针对含公共零点的SIMO信道的直接无限冲击响应(IIR)盲均衡算法。该算法利用IIR预测均衡算法对输入信号进行初始均衡和对均衡结果进行相偏纠正,通过最小均方误差准则提高算法在高斯白噪声环境中的适应性,克服IIR预测算法中的相位偏转问题与IIR预测算法对信噪比敏感的缺点。仿真实验结果表明,该算法对IIR信道及含公共零点信道都具有较好的均衡效果。     

PHoMpara – Parallel Implementation of the Polyhedral Homotopy Continuation Method for Polynomial Systems

The polyhedral homotopy continuation method is known to be a successful method for finding all isolated solutions of a system of polynomial equations. PHoM, an implementation of the method in C++, finds all isolated solutions of a polynomial system by constructing a family of modified polyhedral homotopy functions, tracing the solution curves of the homotopy equations, and verifying the obtained solutions. A software package PHoMpara parallelizes PHoM to solve a polynomial system of large size. Many characteristics of the polyhedral homotopy continuation method make parallel implementation efficient and provide excellent scalability. Numerical results include some large polynomial systems that had not been solved.     

两个多项式阵最大公因子的计算

本文给出了用对多项式阵的系数阵进行初等变换的方法确定两个多项式阵的最大公因子及其互质部分的一种算法.     

基于SVM的多项式循环程序秩函数生成

程序终止性问题是自动程序验证领域中的一个研究热点.秩函数探测是进行终止性分析的主要方法.针对单重无条件分支的多项式循环程序,将其秩函数计算问题归结为二分类问题,从而可利用支持向量机（SVM）算法来计算程序的秩函数.与基于量词消去技术的秩函数计算方法不同,该方法能在可接受的时间范围内探测到更为复杂的秩函数.