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.     

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     

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.     

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.     

有向回路法和网格法:多边形内外点判别的新算法

该文把简单多边形视作一个有向回路,利用多边形的环绕方向和区域划分提出了两种判别内外点的新算法:有向回路法和网格法。有向回路法利用了多边形的方向性,在某些情况下可以不必遍历多边形的所有边。该算法程序简单,时间复杂度为O(n),平均性能优于复杂度为Θ(n)的射线法和标号法,但只能处理凸多边形。网格法是有向回路法的改进算法,利用了多边形的方向性和区域划分。网格法将n边形的包围盒划分为(n-1)×(n-1)个网格:如果待处理的点在某个网格内,则仅根据经过该网格的所有边就可以判断该点的内外性。网格法可以处理任意简单多边形,包括带孔的多边形;最坏情况下的时间复杂度为O(lgn),空间复杂度为Θ(n2)。     

Zeros of the system matrix

This note provides an easy characterization of the zeros of the system matrix in terms of a strong version of system reachability and observabillty. Interpreted in abstract terms, it yields Wonham and Morse's characterization of zero. The results hold for systems defined over an arbitrary field.     

参数曲线曲面自由变形的多项式因子方法

为得到理想的造型效果,提出一种空间参数曲线曲面自由变形的方法.首先引入基于多项式的伸缩因子,并构造了空间变形矩阵;然后将变形矩阵或伸缩因子作用于待变形曲线曲面方程,从而得到形变效果.实验结果表明,该方法计算简单、易于控制,可得到较好的变形效果.     

Enumerative Coding for Constant-Weight Binary Sequences with Constrained Run-Length of Zeros

We suggest a method for computing the number of dklr-sequences with given number of ones. Based on these results and the well-known method of Babkin and Cover, enumerative encoding and decoding for constant-weight dklr-sequences is obtained.     

基于多项式变换的参数估计方法

本文给出一种采用DPT估计SNCK信号时宽—带宽积的方法,并通过仿真该估计方法的性能与其它估计方法进行比较.首先给出SNCK信号参数估计的一般过程.为了便于计算和理论推导,根据估计出的中心频率将接收到的SNCK信号搬移到零频,从而进一步估计其它参数,如采用DPT估计SNCK信号时宽带宽积.本文将重点研究采用DPT算法估计SNCK信号值的方法.     

一种多项式时间的路径敏感的污点分析方法

提出了一种解决静态污点分析方法在进行路径敏感的分析时面临的路径爆炸的问题的方法.该方法将污圹点分析问题转化为加权下推自动机的广义下推后继问题,进一步利用污点数据在程序中的可达性,减少后续分析中需要精确执行的路径数.从而该方法能够以多项式的时间复杂度实现程序状态空间遍历,并能在发现程序违反安全策略时自动生成反例路径.设计实验使用该方法对击键记录行为进行了刻画,对恶意代码程序和合法软件进行了两组分析实验,并与现有的方法进行了对比分析.实验证明本文的方法可以有效地对具有较多分支的程序进行路径敏感的污点分析,同时具有较小的时间复杂度和空间复杂度