Simple algorithms for approximating all roots of a polynomial with real roots

We present a simple algorithm for approximating all roots of a polynomial p(x) when it has only real roots. The algorithm is based on some interesting properties of the polynomials appearing in the Extended Euclidean Scheme for p(x) and p′(x). For example, it turns out that these polynomials are orthogonal; as a consequence, we are able to limit the precision required by our algorithm in intermediate steps. A parallel implementation of this algorithm yields a P-uniform NC₂ circuit, and the bit complexity of its sequential implementation is within a polylog factor of the bit complexity of the best known algorithm for the problem.     

The computation of multiple roots of a polynomial

This paper considers structured matrix methods for the calculation of the theoretically exact roots of a polynomial whose coefficients are corrupted by noise, and whose exact form contains multiple roots. The addition of noise to the exact coefficients causes the multiple roots of the exact form of the polynomial to break up into simple roots, but the algorithms presented in this paper preserve the multiplicities of the roots. In particular, even though the given polynomial is corrupted by noise, and all computations are performed on these inexact coefficients, the algorithms ‘sew’ together the simple roots that originate from the same multiple root, thereby preserving the multiplicities of the roots of the theoretically exact form of the polynomial. The algorithms described in this paper do not require that the noise level imposed on the coefficients be known, and all parameters are calculated from the given inexact coefficients. Examples that demonstrate the theory are presented.     

The number of roots of a polynomial outside a circle

We obtain a new criterion in terms of determinant inequalities that all the roots of a real polynomial should lie inside the unit circle, i.e., a criterion for the stability of periodic motions. In comparison with the Shur-Kon criterion, the number of determinants is halved.The results of this paper were published without proof in [2].Translated from Matematicheskie Zametki, Vol. 13, No. 1, pp. 3–12, January, 1973.     

A method for finding the roots of a polynomial

Summary Two variants of a method for finding the roots of a polynomial are described. A proof of the method for a general polynomial with complex coefficients is not based on neighbourhoods of saddle points which are sufficiently small. The speed of convergence is guaranteed since the method is a modification of the downhill method and since it can be used in combination with an arbitrary method which quickly converges in practice, but whose convergence cannot be proved.     

Iterations of homogeneous polynomial transformations with positive coefficients

A study is made of the behavior as k of the iterations T^k(x) of a homogeneous polynomial transformation T acting from Rⁿ to Rⁿ according to the formula (T(x))_i=Q_i (x), i=1, 2,..., n, where Q_i(x) is a homogeneous polynomial of degree m>1 with positive coefficients.Translated from Matematicheskie Zametki, Vol. 6, No. 4, pp. 411–416, October, 1969.In conclusion I should like to thank S. A. Molchanov for proposing the topic and S. M. Natanzon for his help with the paper.     

On roots of polynomials with positive coefficients

We prove that an algebraic number α is a root of a polynomial with positive rational coefficients if and only if none of its conjugates is a nonnegative real number. This settles a recent conjecture of Kuba.     

Note on roots location of a symmetric polynomial with respect to the imaginary axis

In the theory of the separation of roots of algebraic equations, the well-known Routh–Hurwitz–Fujiwara theorem enables us to separate the complex roots of a polynomial with complex coefficients in terms of the inertia of a related Hermitian matrix. Unfortunately, it fails if the polynomial has a nontrivial factor which is symmetric with respect to the imaginary axis. In this article, we present a method to overcome the fault and formulate the inertia of a scalar polynomial with complex coefficients in terms of the inertia of several Hermitian matrices based on a factorization of a monic symmetric polynomial into products of monic symmetric polynomials with only simple roots in the complex plane and on computing the inertia of each factor by means of a subtle perturbation.     

Inclusion of the roots of a polynomial based on Gerschgorin's theorem

Summary In this note a new companion matrix is presented which can be interpreted as a product of Werner's companion matrices [13]. Gerschgorin's theorem yields an inclusion of the roots of a polynomial which is best in the sense of [4] and generalizes a result of L. Elsner [5]. This inclusion is better than the one due to W. Börsch-Supan in [1].Dedicated to Professor E. Stein on the occasion of his 60th birthday.     

On the cost of approximating all roots of a complex polynomial

This work examines the computational complexity of a homotopy algorithm in approximating all roots of a complex polynomialf. It is shown that, probabilistically, monotonic convergence to each of the roots occurs after a determined number of steps. Moreover, in all subsequent steps, each rootz is approximated by a complex numberx, where ifx ₀ =x, x _j =x _j–1 –f(x _j–1)/f(x _j–1),j = 1, 2,, then |x _j –z| < (1/|x ₀ –z|)|x _j–1–z|².     

A PL homotopy for finding all the roots of a polynomial

This paper presents a constructive method which gives, for any polynomialF(Z) of the degreen, approximate values of all the roots ofF(Z).. The point of the method is on the use of a piecewise linear function (Z, t) which approximates a homotopyH(Z, t) betweenF(Z) and a polynomialG(Z) of the degreen withn known simple roots. It is shown that the set of solutions to (Z, t) = 0 includesn distinct paths,m of which converges to a root ofF(Z) if and only if the root has the multiplicitym. Starting from givenn roots ofG(Z), a complementary pivot algorithm generates thosen paths.This work was supported by grants from Management Science Development Foundation and Takeda Science Foundation.     

Computing the real roots of a polynomial by the exclusion algorithm

We describe a new algorithm for localizing the real roots of a polynomialP(x). This algorithm determines intervals on whichP(x) does not possess any root. The remainder set contains the real roots ofP(x) and can be arbitrarily small.     

Completely positive reformulations of polynomial optimization problems with linear constraints

A polynomial optimization problem (POP) is an optimization problem in which both the objective and constraints can be written in terms of polynomials on the decision variables. Recently, it has been shown that under appropriate assumptions POPs can be reformulated as conic problems over the cone of completely positive tensors; which generalize the set of completely positive matrices. Here, we show that by explicitly handling the linear constraints in the formulation of the POP, one obtains a generalization of the completely positive reformulation of quadratically constrained quadratic programs recently introduced by Bai et al. (Math Program 1–28, 2016).     

Asymptotic behavior of roots of random polynomial equations

We derive several new results on the asymptotic behavior of the roots of random polynomial equations, including conditions under which the distributions of the zeros of certain random polynomials tend to the uniform distribution on the circumference of a circle centered at the origin. We also derive a probabilistic analog of the Cauchy-Hadamand theorem that enables us to obtain the radius of convergence of a random power series.     

Completely positive reformulations for polynomial optimization

Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well established body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution schemes for quadratic polynomial optimization problems have been designed by drawing on conic programming tools, and the extensively studied cones of completely positive and of copositive matrices. In particular, this approach has been applied to solve key combinatorial optimization problems. Along this line of research, we consider polynomial optimization problems that are not necessarily quadratic. For this purpose, we use a natural extension of the cone of completely positive matrices; namely, the cone of completely positive tensors. We provide a general characterization of the class of polynomial optimization problems that can be formulated as a conic program over the cone of completely positive tensors. As a consequence of this characterization, it follows that recent related results for quadratic problems can be further strengthened and generalized to higher order polynomial optimization problems. Also, we show that the conditions underlying the characterization are conceptually the same, regardless of the degree of the polynomials defining the problem. To illustrate our results, we discuss in further detail special and relevant instances of polynomial optimization problems.     

On the minimum real roots of the adjoint polynomial of a graph

For a graph G, we denote by h(G,x) the adjoint polynomial of G. Let β(G) denote the minimum real root of h(G,x). In this paper, we characterize all the connected graphs G with .     

Finding roots of a real polynomial simultaneously by means of Bairstow's method

Aberth's method for finding the roots of a polynomial was shown to be robust. However, complex arithmetic is needed in this method even if the polynomial is real, because it starts with complex initial approximations. A novel method is proposed for real polynomials that does not require any complex arithmetic within iterations. It is based on the observation that Aberth's method is a systematic use of Newton's method. The analogous technique is then applied to Bairstow's procedure in the proposed method. As a result, the method needs half the computations per iteration than Aberth's method. Numerical experiments showed that the new method exhibited a competitive overall performance for the test polynomials.     

关于对偶Steiner多项式的根的注记

受凸体的Steiner多项式的启发,定义了星体的对偶Steiner多项式,并利用对偶Aleksandrov-Fenchel不等式讨论了对偶Steiner多项式的根.进而,得到了关于对偶Steiner多项式的根的一些不等式,这些不等式恰好是关于Steiner多项式的根的不等式的对偶形式.