New progress in real and complex polynomial root-finding

Matrix methods are increasingly popular for polynomial root-finding. The idea is to approximate the roots as the eigenvalues of the companion or generalized companion matrix associated with an input polynomial. The algorithms also solve secular equation. QR algorithm is the most customary method for eigen-solving, but we explore the inverse Rayleigh quotient iteration instead, which turns out to be competitive with the most popular root-finders because of its excellence in exploiting matrix structure. To advance the iteration we preprocess the matrix and incorporate Newton’s linearization, repeated squaring, homotopy continuation techniques, and some heuristics. The resulting algorithms accelerate the known numerical root-finders for univariate polynomial and secular equations, and are particularly well suited for the acceleration by using parallel processing. Furthermore, even on serial computers the acceleration is dramatic for numerical approximation of the real roots in the typical case where they are much less numerous than all complex roots.     

Finding roots of arbitrary high order polynomials based on neural network recursive partitioning method

Copyright by Science in China Press 2004 Finding the roots of polynomials is an often-encountered problem in signal proc-essing such as the design of filters and minimum phase system, spectral analysis, speech signal processing, channel coding and decoding, etc. So far, there are many methods that can be used to solve the roots-finding problems[1—5]. These conventional methods, how-ever, are almost all designed based on non-Neumann computers with serial processing properties[4—6]. Recently…     

Eliciting dependability requirements: a control cases based approach

At present,great demands are posed on software dependability.But how to elicit the dependability requirements is still a challenging task.This paper proposes a novel approach to address this issue.The essential idea is to model a dependable software system as a feedforward-feedback control system,and presents the use cases+control cases model to express the requirements of the dependable software systems.In this model,while the use cases are adopted to model the functional requirements,two kinds of control cases(namely the feedforward control cases and the feedback control cases)are designed to model the dependability requirements.The use cases+control cases model provides a unified framework to integrate the modeling of the functional requirements and the dependability requirements at a high abstract level.To guide the elicitation of the dependability requirements,a HAZOP based process is also designed.A case study is conducted to illustrate the feasibility of the proposed approach.     

A graphical technique for nonlinear algebraic equations

A graphical root-finding procedure is proposed for nonlinear algebraic equations. It employs two graphs of the zero-curves of the real and imaginary parts of the polynomial. It gives information on the approximate location for every root together with its multiplicity on the basis of the argument principle. Locally convergent iterative method for roots may enjoy this information for their implementation. Some numerical examples are shown with the graphs.     

Accelerating generators of iterative methods for finding multiple roots of nonlinear equations

Two accelerating generators that produce iterative root-finding methods of arbitrary order of convergence are presented. Primary attention is paid to algorithms for finding multiple roots of nonlinear functions and, in particular, of algebraic polynomials. First, two classes of algorithms for solving nonlinear equations are studied: those with a known order of multiplicity and others with no information on multiplicity. We also demonstrate the acceleration of iterative methods for the simultaneous approximations of multiple roots of algebraic polynomials. A discussion about the computational efficiency of the root-solvers considered and three numerical examples are given.     

Univariate Polynomials: Nearly Optimal Algorithms for Numerical Factorization and Root-finding

To approximate all roots (zeros) of a univariate polynomial, we develop two effective algorithms and combine them in a single recursive process. One algorithm computes a basic well isolated zero-free annulus on the complex plane, whereas another algorithm numerically splits the input polynomial of the n th degree into two factors balanced in the degrees and with the zero sets separated by the basic annulus. Recursive combination of the two algorithms leads to computation of the complete numerical factorization of a polynomial into the product of linear factors and further to the approximation of the roots. The new root-finder incorporates the earlier techniques of Schönhage, Neff/Reif, and Kirrinnis and our old and new techniques and yields nearly optimal (up to polylogarithmic factors) arithmetic and Boolean cost estimates for the computational complexity of both complete factorization and root-finding. The improvement over our previous record Boolean complexity estimates is by roughly the factor of n for complete factorization and also for the approximation of well-conditioned (well isolated) roots, whereas the same algorithm is also optimal (under both arithmetic and Boolean models of computing) for the worst case input polynomial, whose roots can be ill-conditioned, forming clusters. (The worst case complexity bounds for root-finding are supported by our previous algorithms as well.) All algorithms allow processor efficient acceleration to achieve solution in polylogarithmic parallel time.     

The complex dynamic of conjugate gradient method

Conjugate gradient method is a root-finding algorithm to non-linear equations. In this paper, we suggest extending this method for a polynomial to the complex plane. Through the experimental and theoretical mathematics method, we drew the following conclusions: (1) the conjugate gradient is a dynamical system with two complex parameters; (2) locally conditions for convergence to any roots of complex functions is given; (3) the conjugate gradient method may fail to converge to all roots for cubic with three simple roots; (4) the boundary of conjugate gradient basins are fractals in some cases, and depends on the parameters; (5) the algorithm is then improved by introducing a method to determine the optimal parameters.     

Sparse implicitization by interpolation: Characterizing non-exactness and an application to computing discriminants

We revisit implicitization by interpolation in order to examine its properties in the context of sparse elimination theory. Based on the computation of a superset of the implicit support, implicitization is reduced to computing the nullspace of a numeric matrix. The approach is applicable to polynomial and rational parameterizations of curves and (hyper)surfaces of any dimension, including the case of parameterizations with base points. Our support prediction is based on sparse (or toric) resultant theory, in order to exploit the sparsity of the input and the output. Our method may yield a multiple of the implicit equation: we characterize and quantify this situation by relating the nullspace dimension to the predicted support and its geometry. In this case, we obtain more than one multiple of the implicit equation; the latter can be obtained via multivariate polynomial GCD (or factoring). All of the above techniques extend to the case of approximate computation, thus yielding a method of sparse approximate implicitization, which is important in tackling larger problems. We discuss our publicly available Maple implementation through several examples, including the benchmark of a bicubic surface. For a novel application, we focus on computing the discriminant of a multivariate polynomial, which characterizes the existence of multiple roots and generalizes the resultant of a polynomial system. This yields an efficient, output-sensitive algorithm for computing the discriminant polynomial.     

一种快速分解大整数的小因子的优化分解树OFT算法

分解大整数的小因子是解决IFP，DLP问题的诸多攻击方法中的重要运算模块．本文在目前分解大整数小因子算法的基础上，提出的优化分解树(Optimized Factorization Tree)算法，利用树型数据结构和相应的构造算法与回溯算法，配合以作者提出的分解表截支方法和优化分组策略，可以将分解大整数小因子的速度提高50％以上．该算法还可以为大整数素性判别做高效过滤，快速识别大部分合数．     

Polynomial methods for structure from motion

The authors analyze the limitations of structure from motion (SFM) methods presented in the literature and propose the use of a polynomial system of equations, with the unit quaternions representing rotation, to recover SFM under perspective projection. The authors combine the equations by the method of resultants with the MAXIMA symbolic algebra system, reducing the system to a single polynomial. Its real roots are then found with Sturm sequences. Since this system has multiple solutions, a hypothesize-and-verify scheme is used to eliminate incorrect ones. The scheme diminishes the sensitivity of using polynomial equations. The authors examine the effect of different rotation axes and angles on SFM accuracy and compare the performance of the algorithm to a few earlier approaches. Generally, it is found that a large amount of motion is the most important factor in getting good SFM accuracy     

Quasiseparable structures of companion pencils under the QZ-algorithm

Abstract Matrix methods based on the QR eigenvalue algorithm applied to a companion matrix are customary for polynomial root-finding. These methods take advantage of recent results showing that the quasiseparable structure of the input matrix is maintained under the iterative process. The property enables the QR-iteration for a companion matrix to be performed in linear time using a linear memory space. In this note we show the invariance of the quasiseparable structure in the case where the algorithm we deal with is now the QZ-algorithm acting on companion pencils instead of companion matrices.     

Ray-tracing polymorphic multidomain spectral/hp elements for isosurface rendering

The purpose of this paper is to present a ray-tracing isosurface rendering algorithm for spectral/hp (high-order finite) element methods in which the visualization error is both quantified and minimized. Determination of the ray-isosurface intersection is accomplished by classic polynomial root-finding applied to a polynomial approximation obtained by projecting the finite element solution over element-partitioned segments along the ray. Combining the smoothness properties of spectral/hp elements with classic orthogonal polynomial approximation theory, we devise an adaptive scheme which allows the polynomial approximation along a ray-segment to be arbitrarily close to the true solution. The resulting images converge toward a pixel-exact image at a rate far faster than sampling the spectral/hp element solution and applying classic low-order visualization techniques such as marching cubes.     

多项式方程区间内重根的快速判定和裁剪

目的多项式求实根问题有着广泛的应用。改进传统的裁剪方法,在多项式重根的情形下,保持计算稳定性的同时显著地提高相应的收敛阶。方法提出了基于R~3空间内的3次裁剪方法。该方法继承了传统裁剪求根方法的优点,充分利用了Bernstein基函数较好的计算稳定性,同时给出简单方法判别重根的存在性,从而使得重根的情形可以转化为单根的情形。结果与已有的基于R~1和R~2空间的3次裁剪方法相比,本文方法可以具有更好的逼近效果。单根情形下,本文方法与基于R~2空间的3次裁剪方法同时具有5次收敛阶,略高于基于R~1空间3次裁剪方法的4次收敛阶;m(≥2)重根情形下,本文方法理论上可具有5次收敛阶,明显优于已有的基于R~1和R~2空间的3次裁剪方法的4/m或5/m收敛阶。基于R~1,R~2和R~3空间的3次裁剪方法的计算时间复杂度大致相当,均为O(n~2)。结论本文方法可以快速判定重根的情形,同时具有更高的收敛阶和更好的逼近效果。     

Real-time ray casting of algebraic B-spline surfaces

Piecewise algebraic B-spline surfaces (ABS surfaces) are capable of modeling globally smooth shapes of arbitrary topology. These can be potentially applied in geometric modeling, scientific visualization, computer animation and mathematical illustration. However, real-time ray casting the surface is still an obstacle for interactive applications, due to the large amount of numerical root findings of nonlinear polynomial systems that are required. In this paper, we present a GPU-based real-time ray casting method for ABS surfaces. To explore the powerful parallel computing capacity of contemporary GPUs, we adopt iterative numerical root-finding algorithms, e.g., the Newton-Raphson and regula falsi algorithms, rather than recursive ones. To facilitate convergence of the Newton-Raphson or regula falsi algorithm, their initial guesses are determined through rasterization of the isotopic isosurface, and the isosurface is generated based on regular criteria for surface domain subdivision. Meanwhile, polar surfaces are adopted to identify single roots or to isolate different roots, i.e., ray and surface intersections. As an important geometric feature, the silhouette curve is elaborately computed to floating-point accuracy, which can be applied in further anti-aliasing processes. The experimental results show that the proposed method can render thousands of piecewise algebraic surface patches of degrees 6-9 in real time.     

Parallel Polynomial Operations on SMPs: an Overview

SMP-based parallel algorithms and implementationsfor polynomial factoring and GCD are overviewed. Topics include polynomial factoring modulo small primes, univariate and multivariatep-adic lifting, and reformulation of lift basis. Sparse polynomial GCD is also covered.     

Approximate polynomial GCD over integers

Symbolic numeric algorithms for polynomials are very important, especially for practical computations since we have to operate with empirical polynomials having numerical errors on their coefficients. Recently, for those polynomials, a number of algorithms have been introduced, such as approximate univariate GCD and approximate multivariate factorization for example. However, for polynomials over integers having coefficients rounded from empirical data, changing their coefficients over reals does not remain them in the polynomial ring over integers; hence we need several approximate operations over integers. In this paper, we discuss computing a polynomial GCD of univariate or multivariate polynomials over integers approximately. Here, “approximately” means that we compute a polynomial GCD over integers by changing their coefficients slightly over integers so that the input polynomials still remain over integers.     

A matrix pencil based numerical method for the computation of theGCD of polynomials

The paper presents a new numerical method for the computation of the greatest common divisor (GCD) of an m-set of polynomials of R[s], P _m,d, of maximal degree d. It is based on a previously proposed theoretical procedure (Karcanias, 1989) that characterizes the GCD of P_m,d as the output decoupling zero polynomial of a linear system S(Aˆ,Cˆ) that may be associated with P_m,d . The computation of the GCD is thus reduced to finding the finite zeros of the pencil sW-AW, where W is the unobservable subspace of S(Aˆ,Cˆ). If k=dim W, the GCD is determined as any nonzero entry of the kth compound C_k(sW-AˆW). The method defines the exact degree of GCD, works satisfactorily with any number of polynomials and evaluates successfully approximate solutions     

List decoding codes on Garcia–Stictenoth tower using Gröbner basis

An account of the interpolation and the root-finding steps of list decoding of one-point codes is given. The interpolation step is reduced to the problem of finding the minimal element of the Gröbner basis of a submodule of a free module over a polynomial ring of one variable. The procedure for root-finding of the interpolation polynomial going modulo a large degree place is described from the tower point of view.     

The Laguerre-and-sums-of-powers algorithm for the efficient and reliable approximation of all polynomial roots

We prove the first sufficient convergence criterion for Laguerre’s root-finding algorithm, which by empirical evidence is highly efficient. The criterion is applicable to simple roots of polynomials with degree greater than 3. The “Sums of Powers Algorithm” (SPA), which is a reliable iterative root-finding method, can be used to fulfill the condition for each root. Therefore, Laguerre’s method together with the SPA is now an efficient and reliable algorithm (LaSPA). In computational mathematics these results solve a central task which was first attacked by L. Euler 266 years ago.     

Using PVsolve to Analyze and Locate Positions of Parallel Vectors

A new method for finding the locus of parallel vectors is presented, called PVsolve. A parallel-vector operator has been proposed as a visualization primitive, as several features can be expressed as the locus of points where two vector fields are parallel. Several applications of the idea have been reported, so accurate and efficient location of such points is an important problem. Previously published methods derive a tangent direction under the assumption that the two vector fields are parallel at the current point in space, then extend in that direction to a new point. PVsolve includes additional terms to allow for the fact that the two vector fields may not be parallel at the current point, and uses a root-finding approach. Mathematical analysis sheds new light on the feature flow field technique (FFF) as well. The root-finding property allows PVsolve to use larger step sizes for tracing parallel-vector curves, compared to previous methods, and does not rely on sophisticated differential equation techniques for accuracy. Experiments are reported on fluid flow simulations, comparing FFF and PVsolve.