On the cost of computing roots of polynomials

Recently Smale has obtained probabilistic estimates of the cost of computing a zero of a polynomial using a global version of Newton's method. Roughly speaking, his result says that, with the exception of a set of polynomials where the method fails or is very slow, the cost grows as a polynomial in the degree. He also asked whether similar results hold for PL homotopy methods. This paper gives such a result for a special algorithm of the PL homotopy type devised by Kuhn. Its main result asserts that the cost of computing some zero of a polynomial of degreen to an accuracy of ε (measured by the number of evaluations of the polynomial) grows no faster than O(n ³ log₂(n/ε)). This is a worst case analysis and holds for all polynomials without exception. This work was supported, in part, by National Science Foundation Grant MCS79-10027 and, in part, by a fellowship of the Guggenheim Foundation.     

On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials

LetS be a triangulation of andf(z) = z ^d +a _d–1 z ^d–1++a ₀, a complex polynomial. LetF be the piecewise linear approximation off determined byS. For certainS, we establish an upper bound on the complexity of an algorithm which finds zeros ofF. This bound is a polynomial in terms ofn, max{a _i } _i , and measures of the sizes of simplices inS.     

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.     

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.     

On a polynomial inequality

Let p(z)=a₀+?+anzn and q(z)=b₀+? be polynomials of degree respectively n and less than n such that

     

Computation of all solutions to a system of polynomial equations

This paper proposes a homotopy continuation method for approximating all solutions to a system of polynomial equations in several complex variables. The method is based on piecewise linear approximation and complementarity theory. It utilizes a skilful artificial map and two copies of the triangulationJ ₃ with continuous refinement of grid size to increase the computational efficiency and to avoid the necessity of determining the grid size a priori. Some computational results are also reported.     

On the computational complexity of piecewise-linear homotopy algorithms

We show that piecewise-linear homotopy algorithms may take a number of steps that grows exponentially with the dimension when solving a system of linear equations whose solution lies close to the starting point. Our examples are based on an example of Murty exhibiting exponential growth for Lemke's algorithm for the linear complementarity problem.This research was supported in part by NSF grant ECS-7921279 and by a Guggenheim Fellowship.     

On the zeros of a polynomial and its derivatives

If is univariate polynomial with complex coefficients having all its zeros inside the closed unit disk, then the Gauss-Lucas theorem states that all zeros of lie in the same disk. We study the following question: what is the maximum distance from the arithmetic mean of all zeros of to a nearest zero of ? We obtain bounds for this distance depending on degree. We also show that this distance is equal to for polynomials of degree 3 and polynomials with real zeros.

     

A polynomial time algorithm for solving the fermat-weber location problem with mixed norms

This paper discusses the Fermat-Weber location problem, manages to apply the ellipsoid method to this problem and proves the ellipsoid method can be terminated at an approximately optimal location in polynomial time, verifies the ellipsoid method is robust for the lower dimensional location problem     

On polynomials orthogonal to all powers of a given polynomial on a segment

In this paper we investigate the following “polynomial moment problem”: for a given complex polynomial P(z) and distinct a,b∈C to describe polynomials q(z) orthogonal to all powers of P(z) on [a,b]. We show that for given P(z), q(z) the condition that q(z) is orthogonal to all powers of P(z) is equivalent to the condition that branches of the algebraic function Q(P⁻¹(z)), where , satisfy a certain system of linear equations over Z. On this base we provide the solution of the polynomial moment problem for wide classes of polynomials. In particular, we give the complete solution for polynomials of degree less than 10.     

Computational complexity of a piecewise linear homotopy algorithm

We give a bound on the number of steps required by the piecewise linear algorithm based on component wise homotopy (proposed by the author for structured problems) when solving a linear problem. When the coefficient matrix is symmetric and positive definite, this bound is polynomial inn and linear in the condition number of the matrix. We also investigate the expected value of the bound for a particular distribution of such matrices. This research has been partially supported by the grant MCS 80-05154 from the National Science Foundation.     

On a polynomial inequality of E. J. Remez

We prove a result which extends a well-known polynomial inequality of E. J. Remez and another one due to W. A. Markov.

     

On the complexity of approximating the maximal inscribed ellipsoid for a polytope

We give a new polynomial bound on the complexity of approximating the maximal inscribed ellipsoid for a polytope.Research supported by NSF Grant DMS-8706133.Research supported by NSF Grant DMS-8904406.     

On a simultaneous method of Newton-Weierstrass’ type for finding all zeros of a polynomial

Combining a suitable two-point iterative method for solving nonlinear equations and Weierstrass’ correction, a new iterative method for simultaneous finding all zeros of a polynomial is derived. It is proved that the proposed method possesses a cubic convergence locally. Numerical examples demonstrate a good convergence behavior of this method in a global sense. It is shown that its computational efficiency is higher than the existing derivative-free methods.     

Newton's method for linear complementarity problems

This paper presents an iterative, Newton-type method for solving a class of linear complementarity problems. This class was discovered by Mangasarian who had established that these problems can be solved as linear programs. Cottle and Pang characterized solutions of the problems in terms of least elements of certain polyhedral sets. The algorithms developed in this paper are shown to converge to the least element solutions. Some applications and computational results are also discussed.     

On approximating complex quadratic optimization problems via semidefinite programming relaxations

In this paper we study semidefinite programming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems, as well as problems in control theory. For instance, they include the MAX-3-CUT problem where the Laplacian matrix is positive semidefinite (in particular, some of the edge weights can be negative). We present a generic algorithm and a unified analysis of the SDP relaxations which allow us to obtain good approximation guarantees for our models. Specifically, we give an -approximation algorithm for the discrete problem where the decision variables are k-ary and the objective matrix is positive semidefinite. To the best of our knowledge, this is the first known approximation result for this family of problems. For the continuous problem where the objective matrix is positive semidefinite, we obtain the well-known π /4 result due to Ben-Tal et al. [Math Oper Res 28(3):497–523, 2003], and independently, Zhang and Huang [SIAM J Optim 16(3):871–890, 2006]. However, our techniques simplify their analyses and provide a unified framework for treating those problems. In addition, we show for the first time that the gap between the optimal value of the original problem and that of the SDP relaxation can be arbitrarily close to π /4. We also show that the unified analysis can be used to obtain an Ω(1/ log n)-approximation algorithm for the continuous problem in which the objective matrix is not positive semidefinite. This research was supported in part by NSF grant DMS-0306611.     

A concise proof of the Kronecker polynomial system solver from scratch

Nowadays polynomial system solvers are involved in sophisticated computations in algebraic geometry as well as in practical engineering. The most popular algorithms are based on Gröbner bases, resultants, Macaulay matrices, or triangular decompositions. In all these algorithms, multivariate polynomials are expanded in a monomial basis, and the computations mainly reduce to linear algebra. The major drawback of these techniques is the exponential explosion of the size of the polynomials needed to represent highly positive dimensional solution sets. Alternatively, the “Kronecker solver” uses data structures to represent the input polynomials as the functions that compute their values at any given point. In this paper, we present the first self-contained and student friendly version of the Kronecker solver, with a substantially simplified proof of correctness. In addition, we enhance the solver in order to compute the multiplicities of the zeros without any extra cost.     

The polynomial hierarchy and a simple model for competitive analysis

The multi-level linear programs of Candler, Norton and Townsley are a simple class of sequenced-move games, in which players are restricted in their moves only by common linear constraints, and each seeks to optimize a fixed linear criterion function in his/her own continuous variables and those of other players. All data of the game and earlier moves are known to a player when he/she is to move. The one-player case is just linear programming.We show that questions concerning only the value of these games exhibit complexity which goes up all levels of the polynomial hierarchy and appears to increase with the number of players.For three players, the games allow reduction of the ₂ and ₂ levels of the hierarchy. These levels essentially include computations done with branch-and-bound, in which one is given an oracle which can instantaneously solve NP-complete problems (e.g., integer linear programs). More generally, games with (p + 1) players allow reductions of _p and _p in the hierarchy.An easy corollary of these results is that value questions for two-player (bi-level) games of this type is NP-hard.The author's work has been supported by the Alexander von Humboldt Foundation and the Institut fur Okonometrie und Operations Research of the University of Bonn, Federal Republic of Germany; grant ECS8001763 of the National Science Foundation, USA; and a grant from the Georgia Tech Foundation.     

On approximating the roots of some transcendental equations

A study is made of an approximation by means of algebraic numbers of fixed degree of the roots of the equation P(z, a^z)=0, a A, a 0, 1, where P(x, y) is a polynomial with integral rational coefficients.Translated from Matematicheskie Zametki, Vol. 7, No. 2, pp. 203–210, February, 1970.