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.     

On arrangements of roots for a real hyperbolic polynomial and its derivatives

In this paper we count the number ?_n^(0,k), k?n−1, of connected components in the space Δ_n^(0,k) of all real degree n polynomials which a) have all their roots real and simple; and b) have no common root with their kth derivatives. In this case, we show that the only restriction on the arrangement of the roots of such a polynomial together with the roots of its kth derivative comes from the standard Rolle's theorem. On the other hand, we pose the general question of counting all possible root arrangements for a polynomial p(x) together with all its nonvanishing derivatives under the assumption that the roots of p(x) are real. Already the first nontrivial case n=4 shows that the obvious restrictions coming from the standard Rolle's theorem are insufficient. We prove a generalized Rolle's theorem which gives an additional restriction on root arrangements for polynomials.     

A family of centered forms for a polynomial

The general centered form for multi-variate polynomials is investigated and a computing procedure is proposed that results in a certain superset. Based on this procedure the optimal centered forms for monomials and for some special cases of polynomials are investigated.     

Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems

Summary. The eigenproblem method calculates the solutions of systems of polynomial equations . It consists in fixing a suitable polynomial and in considering the matrix corresponding to the mapping where the equivalence classes are modulo the ideal generated by The eigenspaces contain vectors, from which all solutions of the system can be read off. This access was investigated in [1] and [16] mainly for the case that is nonderogatory. In the present paper, we study the case where have multiple zeros in common. We establish a kind of Jordan decomposition of reflecting the multiplicity structure, and describe the conditions under which is nonderogatory. The algorithmic analysis of the eigenproblem in the general case is indicated. Received May 20, 1994     

Computational aspects of multivariate polynomial interpolation: Indexing the coefficients

An algorithm is derived for generating the information needed to pass efficiently between multi-indices of neighboring degrees, of use in the construction and evaluation of interpolating polynomials and in the construction of good bases for polynomial ideals. This revised version was published online in June 2006 with corrections to the Cover Date.     

Using FFT-based techniques in polynomial and matrix computations: recent advances and applicatons

Computations with univariate polynomials, like the evaluation of product, quotient, remainder, greatest common divisor, etc, are closely related to linear algebra computations performed with structured matrices having the Toeplitz-like or the Hankel-like structures.

The discrete Fourier transform, and the FFT algorithms for its computation, constitute a powerful tool for the design and analysis of fast algorithms for solving problems involving polynomials and structured matrices.

We recall the main correlations between polynomial and matrix computations and present two recent results in this field: in particular, we show how Fourier methods can speed up the solution of a wide class of problems arising in queueing theory where certain Markov chains, defined by infinite block Toeplitz matrices in generalized Hessenberg form, must be solved. Moreover, we present a new method for the numerical factorization of polynomials based on a matrix generalization of Koenig's theorem. This method, that relies on the evaluation/interpolation technique at the Fourier points, reduces the problem of polynomial factorization to the computation of the LU decomposition of a banded Toeplitz matrix with its rows and columns suitably permuted. Numerical experiments that show the effectiveness of our algorithms are presented     

On the new fourth-order methods for the simultaneous approximation of polynomial zeros

A new iterative method of the fourth-order for the simultaneous determination of polynomial zeros is proposed. This method is based on a suitable zero-relation derived from the fourth-order method for a single zero belonging to the Schröder basic sequence. One of the most important problems in solving polynomial equations, the construction of initial conditions that enable both guaranteed and fast convergence, is studied in detail for the proposed method. These conditions are computationally verifiable since they depend only on initial approximations, the polynomial coefficients and the polynomial degree, which is of practical importance. The construction of improved methods in ordinary complex arithmetic and complex circular arithmetic is discussed. Finally, numerical examples and the comparison with existing fourth-order methods are given.     

The number of centered forms for a polynomial

A general centered form for polynomials is defined. This centered form is based on the concept of an arrangement of the variables of the polynomial. A formula for the number of arrangements of a term and of a polynomial is given. Some examples are computed showing that even polynomials with moderately many variables may have a very large number of possible centered forms.     

Incomplete Gröbner basis as a preconditioner for polynomial systems

Precondition plays a critical role in the numerical methods for large and sparse linear systems. It is also true for nonlinear algebraic systems. In this paper incomplete Gröbner basis (IGB) is proposed as a preconditioner of homotopy methods for polynomial systems of equations, which transforms a deficient system into a system with the same finite solutions, but smaller degree. The reduced system can thus be solved faster. Numerical results show the efficiency of the preconditioner.     

On a class of higher order methods for simultaneous rootfinding of generalized polynomials

Summary Using the argument principle higher order methods for simultaneous computation of all zeros of generalized polynomials (like algebraic, trigonometric and exponential polynomials or exponential sums) are derived. The methods can also be derived following the continuation principle from [3]. Thereby, the unified approach of [7] is enlarged to arbitrary orderN. The local convergence as well as a-priori and a-posteriori error estimates for these methods are treated on a general level. Numerical examples are included.     

Numerical factorization of a polynomial by rational Hermite interpolation

We derive a class of iterative formulae to find numerically a factor of arbitrary degree of a polynomialf(x) based on the rational Hermite interpolation. The iterative formula generates the sequence of polynomials which converge to a factor off(x). It has a high convergence order even for a factor which includes multiple zeros. Some numerical examples are also included.     

Analysis of two Chebyshev-like third order methods free from second derivatives for solving systems of nonlinear equations

In this paper, two Chebyshev-like third order methods free from second derivatives are considered and analyzed for systems of nonlinear equations. The methods can be obtained by having different approximations to the second derivatives present in the Chebyshev method. We study the local and third order convergence of the methods using the point of attraction theory. The computational aspects of the methods are also studied using some numerical experiments including an application to the Chandrasekhar integral equations in Radiative Transfer.     

Monotonieeigenschaften des Steffensen-Verfahrens

Steffensen's method is slightly generalized by introducing a real parameter. In this way one can get different monotonicity properties, depending on the choice of this parameter. These monotonicity statements give the possibility of bracketing the solution of a given problem. In a special case they even ensure the convergence and the existence of a solution. Furthermore there are given sufficient conditions, which show that Steffensen's method converges at least as quickly as Newton's method. A numerical example shows the efficiency of the theorems and compares Steffensen's and Newton's method.

     

Numerical experiments on the accuracy of the Chebyshev–Frobenius companion matrix method for finding the zeros of a truncated series of Chebyshev polynomials

For a function f(x)$f(x)$ that is smooth on the interval x∈[a,b]$x\in [a,b]$ but otherwise arbitrary, the real-valued roots on the interval can always be found by the following two-part procedure. First, expand f(x)$f(x)$ as a Chebyshev polynomial series on the interval and truncate for sufficiently large N. Second, find the zeros of the truncated Chebyshev series. The roots of an arbitrary polynomial of degree N  , when written in the form of a truncated Chebyshev series, are the eigenvalues of an N×N$N\times N$ matrix whose elements are simple, explicit functions of the coefficients of the Chebyshev series. This matrix is a generalization of the Frobenius companion matrix. We show by experimenting with random polynomials, Wilkinson's notoriously ill-conditioned polynomial, and polynomials with high-order roots that the Chebyshev companion matrix method is remarkably accurate for finding zeros on the target interval, yielding roots close to full machine precision. We also show that it is easy and cheap to apply Newton's iteration directly to the Chebyshev series so as to refine the roots to full machine precision, using the companion matrix eigenvalues as the starting point. Lastly, we derive a couple of theorems. The first shows that simple roots are stable under small perturbations of magnitude ε$\epsilon$ to a Chebyshev coefficient: the shift in the root _x*$x_{*}$ is bounded by ε/df/dx(_x*)+O(ε²)$\epsilon /\mathrm{d}f/\mathrm{d}x(x_{*})+\mathrm{O}({\epsilon }^2)$ for sufficiently small ε$\epsilon$. Second, we show that polynomials with definite parity (only even or only odd powers of x) can be solved by a companion matrix whose size is one less than the number of nonzero coefficients, a vast cost-saving.     

On new higher order families of simultaneous methods for finding polynomial zeros

Two one parameter families of iterative methods for the simultaneous determination of simple zeros of algebraic polynomials are presented. The construction of these families are based on a one parameter family of the third order for finding a single root of nonlinear equation f(x)=0. Some previously derived simultaneous methods can be obtained from the presented families as special cases. We prove that the local convergence of the proposed families is of the order four. Numerical results are included to demonstrate the convergence properties of considered methods.     

Differential Galois theory and non-integrability of planar polynomial vector fields

We study a necessary condition for the integrability of the polynomials vector fields in the plane by means of the differential Galois Theory. More concretely, by means of the variational equations around a particular solution it is obtained a necessary condition for the existence of a rational first integral. The method is systematic starting with the first order variational equation. We illustrate this result with several families of examples. A key point is to check whether a suitable primitive is elementary or not. Using a theorem by Liouville, the problem is equivalent to the existence of a rational solution of a certain first order linear equation, the Risch equation. This is a classical problem studied by Risch in 1969, and the solution is given by the “Risch algorithm”. In this way we point out the connection of the non integrability with some higher transcendent functions, like the error function.     

A bivariate preprocessing paradigm for the Buchberger-Möller algorithm

For the last almost three decades, since the famous Buchberger-Möller (BM) algorithm emerged, there has been wide interest in vanishing ideals of points and associated interpolation polynomials. Our paradigm is based on the theory of bivariate polynomial interpolation on cartesian point sets that gives us a related degree reducing interpolation monomial and Newton bases directly. Since the bases are involved in the computation process as well as contained in the final output of the BM algorithm, our paradigm obviously simplifies the computation and accelerates the BM process. The experiments show that the paradigm is best suited for the computation over finite prime fields that have many applications.     

An efficient start system for multi-homogeneous polynomial continuation

Summary When solving a system of polynomial equations using homotopy continuation, the number of solution paths can often be significantly reduced by casting the equations in multi-homogeneous form. This requires a multi-homogeneous start system having a full set of nonsingular solutions that can be easily computed. We give a general form of such a start system that works for any multi-homogeneous structure and that can be used efficiently in continuation.     

Point estimation of simultaneous methods for solving polynomial equations: A survey (II)

The construction of computationally verifiable initial conditions which provide both the guaranteed and fast convergence of the numerical root-finding algorithm is one of the most important problems in solving nonlinear equations. Smale's “point estimation theory” from 1981 was a great advance in this topic; it treats convergence conditions and the domain of convergence in solving an equation f(z)=0$f(z)=0$ using only the information of f   at the initial point _z0$z_0$. The study of a general problem of the construction of initial conditions of practical interest providing guaranteed convergence is very difficult, even in the case of algebraic polynomials. In the light of Smale's point estimation theory, an efficient approach based on some results concerning localization of polynomial zeros and convergent sequences is applied in this paper to iterative methods for the simultaneous determination of simple zeros of polynomials. We state new, improved initial conditions which provide the guaranteed convergence of frequently used simultaneous methods for solving algebraic equations: Ehrlich–Aberth's method, Ehrlich–Aberth's method with Newton's correction, Börsch-Supan's method with Weierstrass’ correction and Halley-like (or Wang–Zheng) method. The introduced concept offers not only a clear insight into the convergence analysis of sequences generated by the considered methods, but also explicitly gives their order of convergence. The stated initial conditions are of significant practical importance since they are computationally verifiable; they depend only on the coefficients of a given polynomial, its degree n and initial approximations to polynomial zeros.