Counting the number of distinct real roots of certain polynomials by Bezoutian and the Galois groups over the rational number field

In this article, we count the number of distinct real roots of certain polynomials in terms of Bezoutian form. As an application, we construct certain irreducible polynomials over the rational number field which have given number of real roots and by the result of Oz Ben-Shimol [On Galois groups of prime degree polynomials with complex roots, Algebra Disc. Math. 2 (2009), pp. 99–107], we obtain an algorithm to construct irreducible polynomials of prime degree p whose Galois groups are isomorphic to S _p or A _p .     

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.     

On the roots of the orthogonal polynomials and residual polynomials associated with a conjugate gradient method

In this paper we explore two sets of polynomials, the orthogonal polynomials and the residual polynomials, associated with a preconditioned conjugate gradient iteration for the solution of the linear system Ax = b. In the context of preconditioning by the matrix C, we show that the roots of the orthogonal polynomials, also known as generalized Ritz values, are the eigenvalues of an orthogonal section of the matrix C A while the roots of the residual polynomials, also known as pseudo-Ritz values (or roots of kernel polynomials), are the reciprocals of the eigenvalues of an orthogonal section of the matrix (C A)^?1. When C A is selfadjoint positive definite, this distinction is minimal, but for the indefinite or nonselfadjoint case this distinction becomes important. We use these two sets of roots to form possibly nonconvex regions in the complex plane that describe the spectrum of C A.     

Efficient p-adic Cell Decompositions for Univariate Polynomials

Cell decompositions are constructed for polynomials f(x)Z_p[x] of degree n, such that n<p, using O(n²) cells. When f is square-free this yields a polynomial-time algorithm for counting and approximating roots in Z_p. These results extend to give a polynomial-time algorithm in the bit model for fZ[x].     

A binary powering Schur algorithm for computing primary matrix roots

An algorithm for computing primary roots of a nonsingular matrix A is presented. In particular, it computes the principal root of a real matrix having no nonpositive real eigenvalues, using real arithmetic. The algorithm is based on the Schur decomposition of A and has an order of complexity lower than the customary Schur based algorithm, namely the Smith algorithm.     

Stably computing the multiplicity of known roots given leading coefficients

We show that a monic univariate polynomial over a field of characteristic zero, with k distinct nonzero known roots, is determined by precisely k of its proper leading coefficients. Furthermore, we give an explicit, numerically stable algorithm for computing the exact multiplicities of each root over $\mathbb{C}$. We provide a version of the result and accompanying algorithm when the field is not algebraically closed by considering the minimal polynomials of the roots. Then, we demonstrate how these results can be used to obtain the full homogeneous spectra of symmetric tensors—in particular, complete characteristic polynomials of hypergraphs.     

Smooth roots of hyperbolic polynomials with definable coefficients

We prove that the roots of a definable C ^∞ curve of monic hyperbolic polynomials admit a definable C ^∞ parameterization, where ‘definable’ refers to any fixed o-minimal structure on (ℝ,+, ·). Moreover, we provide sufficient conditions, in terms of the differentiability of the coefficients and the order of contact of the roots, for the existence of C ^p (for p ∈ ℕ) arrangements of the roots in both the definable and the non-definable case. These conditions are sharp in the definable and, under an additional assumption, also in the non-definable case. In particular, we obtain a simple proof of Bronshtein’s theorem in the definable setting. We prove that the roots of definable C ^∞ curves of complex polynomials can be desingularized by means of local power substitutions t ↦ ±t ^N . For a definable continuous curve of complex polynomials we show that any continuous choice of roots is actually locally absolutely continuous.     

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|².     

Ein konvergentes Iterationsverfahren zur Bestimmung der Nullstellen eines Polynoms

Summary In order to determine the roots of a polynomialp, a sequence of numbers {x _k} is constructed such that the associated sequence {|p(x _k)|} decreases monotonically. To determine a new iteration pointx _k+1 such that |p(x _k+1)|<-|p(x _k)| ( is a positive real constant, <1, depending only on the degree ofp), we determine a circleK aroundx _k which contains no root ofp and compute the values ofp atN points which are distributed equally on the circumference ofK (N again depends only on the degree ofp); at least one of theN points is shown to satisfy the given condition. Computing the function values by means of Fourier synthesis according to Cooley-Tukey [2] and combining our iteration step with the normal step of the method of Nickel [1], we obtain a numerically safe and fast algorithm for determining the roots of arbitrary polynomials.     

Recurrence Relations for the Coefficients in Series Expansions with Respect to Semi-Classical Orthogonal Polynomials

Let {P _k } be a sequence of the semi-classical orthogonal polynomials. Given a function f satisfying a linear second-order differential equation with polynomial coefficients, we describe an algorithm to construct a recurrence relation satisfied by the coefficients a _k [f] in f= _k a _k [f]P _k . A systematic use of basic properties (including some nonstandard ones) of the polynomials {P _k } results in obtaining a recurrence of possibly low order. Recurrences for connection or linearization coefficients related to the first associated generalized Gegenbauer, Bessel-type and Laguerre-type polynomials are given explicitly.     

Numerical computation of polynomial zeros by means of Aberth's method

An algorithm for computing polynomial zeros, based on Aberth's method, is presented. The starting approximations are chosen by means of a suitable application of Rouché's theorem. More precisely, an integerq 1 and a set of annuliA _i,i=1,...,q, in the complex plane, are determined together with the numberk _i of zeros of the polynomial contained in each annulusA _i. As starting approximations we choosek _i complex numbers lying on a suitable circle contained in the annulusA _i, fori=1,...,q. The computation of Newton's correction is performed in such a way that overflow situations are removed. A suitable stop condition, based on a rigorous backward rounding error analysis, guarantees that the computed approximations are the exact zeros of a nearby polynomial. This implies the backward stability of our algorithm. We provide a Fortran 77 implementation of the algorithm which is robust against overflow and allows us to deal with polynomials of any degree, not necessarily monic, whose zeros and coefficients are representable as floating point numbers. In all the tests performed with more than 1000 polynomials having degrees from 10 up to 25,600 and randomly generated coefficients, the Fortran 77 implementation of our algorithm computed approximations to all the zeros within the relative precision allowed by the classical conditioning theorems with 11.1 average iterations. In the worst case the number of iterations needed has been at most 17. Comparisons with available public domain software and with the algorithm PA16AD of Harwell are performed and show the effectiveness of our approach. A multiprecision implementation in MATHEMATICA is presented together with the results of the numerical tests performed.Work performed under the support of the ESPRIT BRA project 6846 POSSO (POlynomial System SOlving).     

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.     

Extensions of thep-adic fields generated by the roots of a single polynomial in two variables

One of the generalizations of the Hilbert's Irreducibility Theorem states that if F(X, Y) is irreducible in Q _p [X, Y] then, for almost every n N, F(n, Y) is irreducible in Q _p [Y]. Let E{p, d} be the set of all the extensions of Q _p of degree d. We shall prove that for each subset S E{p, d}there exist polynomials F(X, Y) such that the set of extensions of Q _p generated by the roots of F (n, Y)is exactly S. Moreover we shall prove that all the functions f are induced by polynomials F(X) Z[X].M. S. C. N. 11S05, (11S15).The author would like to thank Prof. Roberto Dvornicich for several useful conversations and advices.     

A new computational approach for stochastic fluid models of multiplexers with heterogeneous sources

In this paper we derive an efficient computational procedure for the system in which fluid is produced byN ₁ on-off sources of type 1,N ₂ on-off sources of type 2 and transferred to a buffer which is serviced by a channel of constant capacity. This is a canonical model for multiservice ATM multiplexing, which is hard to analyze and also of wide interest. This paper's approach to the computation of the buffer overflow probability,G(x) = Pr{buffer content >x}, departs from all prior approaches in that it transforms the computation ofG(x) for a particularx into a recursive construction of an interpolating polynomial. For the particular case of two source types the interpolating polynomial is in two variables. Our main result is the derivation of recursive algorithms for computing the overflow probabilityG(x) and various other performance measures using their respective relations to two-dimensional interpolating polynomials. To make the computational procedure efficient we first derive a new system of equations for the coefficients in the spectral expansion formula forG(x) and then use specific properties of the new system for efficient recursive construction of the polynomials. We also develop an approximate method with low complexity and analyze its accuracy by numerical studies. We computeG(x) for different values ofx, the mean buffer content and the coefficient of the dominant exponential term in the spectral expansion ofG(x). The accuracy of the approximations is reasonable when the buffer utilization characterized by G(0) is more than 10^–2.     

Level structure of Zhegalkin polynomials,properties of test sets,and an annihilator search algorithm

Properties of the Boolean functions specified by the Zhegalkin polynomials in n variables of degree not greater than k are investigated from the viewpoint of placing their unit (zero) points on a unit cube. Properties of test sets for the Zhegalkin polynomials are considered, where the key role is played by the irredundant test sets. A deterministic algorithm for finding all the annihilators for a given polynomial is described including minimal-degree annihilators that have applications in cryptology. In the available algorithms for finding annihilators, the problem is reduced to solving systems of linear Boolean equations. Reducing the dimension of these systems decreases the algorithmic complexity of solving the problem. The proposed algorithm makes it possible to decrease the complexity of finding annihilators by reducing the dimension of such systems but it does not reduce the asymptotic complexity of solving systems of linear Boolean equations.     

Modifications of Newton’s method for even-grade palindromic polynomials and other twined polynomials

The paper describes some modifications of Newton??s method for refining the zeros of even-grade f(x)-twined (f(x)-egt) polynomials, defined as polynomials whose roots appear in pairs {x _i ,f(x _i )}. Particular attention is given to even-grade palindromic (egp) polynomials. The algorithms are derived from certain symmetric division processes for computing a symmetric quotient and a symmetric remainder of two given f(x)-egt polynomials. Numerical results indicate that the presented algorithms can be more accurate than other methods which do not take into consideration the symmetry of the coefficients.     

Pseudo-Orthogonal Polynomials

We consider the classical problem of transforming an orthogonality weight of polynomials by means of the space R _n . We describe systems of polynomials called pseudo-orthogonal on a finite set of n points. Like orthogonal polynomials, the polynomials of these systems are connected by three-term relations with tridiagonal matrix which is nondecomposable but does not enjoy the Jacobi property. Nevertheless these polynomials possess real roots of multiplicity one; moreover, almost all roots of two neighboring polynomials separate one another. The pseudo-orthogonality weights are partly negative. Another result is the analysis of relations between matrices of two different orthogonal systems which enables us to give explicit conditions for existence of pseudo-orthogonal polynomials.     

Algorithm for calculating the roots of polynomials with coefficients in the ring of polynomials over an arbitrary integral domain

A deterministic algorithm for calculating the roots of polynomials in one variable with coefficients in the ring of polynomials in several variables over an arbitrary integral domain is constructed. An estimate for the arithmetic complexity of the algorithm in the worst case is obtained.     

Recurrence relations for the coefficients of the Fourier series expansions with respect to q-classical orthogonal polynomials

We propose an algorithm to construct recurrence relations for the coefficients of the Fourier series expansions with respect to the q-classical orthogonal polynomials p_k(x;q). Examples dealing with inversion problems, connection between any two sequences of q-classical polynomials, linearization of ϑ_m(x) p_n(x;q), where ϑ_m(x) is x^mor (x;q)_m, and the expansion of the Hahn-Exton q-Bessel function in the little q-Jacobi polynomials are discussed in detail. This revised version was published online in June 2006 with corrections to the Cover Date.     

Joint bounds for the Perron roots of nonnegative matrices with applications

Given a finite set {A_x}_{x ∈ X} of nonnegative matrices, we derive joint upper and lower bounds for the row sums of the matrices D⁻¹ A^(x) D, x ∈ X, where D is a specially chosen nonsingular diagonal matrix. These bounds, depending only on the sparsity patterns of the matrices A^(x) and their row sums, are used to obtain joint two-sided bounds for the Perron roots of given nonnegative matrices, joint upper bounds for the spectral radii of given complex matrices, bounds for the joint and lower spectral radii of a matrix set, and conditions sufficient for all convex combinations of given matrices to be Schur stable. Bibliography: 20 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 334, 2006, pp. 30–56.