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.     

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.     

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 .     

Inverse scattering in one-dimensional nonconservative media

The inverse scattering problem arising in wave propagation in one-dimensional non-conservative media is analyzed. This is done in the frequency domain by considering the Schrödinger equation with the potentialikP(x)+Q(x), wherek ² is the energy andP(x) andQ(x) are real integrable functions. Using a pair of uncoupled Marchenko integral equations,P(x) andQ(x) are recovered from an appropriate set of scattering data including bound-state information. Some illustrative examples are provided.Dedicated to M.G. Kreîn, one of the founding fathers of inverse scattering theory.     

On levi–typ conditions for hypoellipticity of certain diffrential operators

The hypoelliticity is discussed for operators of the form P=D² _x+a(x)D² _y+b(x)D_ywhere a (x) and b (x) are real–valued C^∞ functions satisfying a(0)=0 and a(x) >0 for x≠0.We seek the conditions for P to be hypoelliptic, especially in the case where both a (x) and b(x) vanish to infinite order on x=0.     

Solution of Equations with One Variable

Let a function f(x) C ^(r)[a,b], r 0, and take values that have different signs at the endpoints of the interval [a,b]. In the article, we propose effective methods for calculating real roots of the equation f(x)=0 on the given interval [a,b]. We substantiate this method and make a comparison between this method and the chord and Newton methods.     

On a continuous analog of the gradient method

In a real Hilbert space H we consider the nonlinear operator equation P(x)=0 and the continuous gradient methodx (t)= –P (x)^* P (x), x (0) = x₀. Two theorems on the convergence of the process (*) to the solution of the equation P(x)=0 are proved.Translated from Matematicheskie Zametki, Vol. 3, No. 4, pp. 421–426, April, 1968.     

On the Baxter functional equation

Summary A new shorter proof is given for the Theorem of P. Volkmann and H. Weigel determining the continuous solutionsf:R R of the Baxter functional equationf(f(x)y + f(y)x – xy) = f(x)f(y). The proof is based on the well known theorem of J. Aczél describing the continuous, associative, and cancellative binary operations on a real interval.     

Geometrical solution of some cubic equations with non-real roots

A general cubic equation ax ³ + bx ² + cx + d = 0 where a, b, c, d ∈R, a ≠ 0 has three roots with two possibilities—either all three roots are real or one root is real and the remaining two roots are imaginary. Dealing with the second possibility this paper attempts to give the geometrical locations of the imaginary roots of the equation under three different sets of conditions. These sets of conditions include: (i) the real root of the given cubic equation is given, (ii) the real part of an imaginary root is given, and (iii) the imaginary part of an imaginary root is given.     

Mean value estimates in lattice point theory

LetQ(u) be a positive definite quadratic form inr2 variables with a real symmetric coefficient matrix of determinantD. Given a real vectorb with 0b _j <1, forx>0 letA(x) be the number of lattice points in the ellipsoidQ(u+b)x, letV(x) be the volume of this ellipsoid andP(x)=A(x)–V(x). Let . By introduction of a parameter we shall show how the treatment of estimates onP(x) and onM(x) can be unified.     

A new algorithm for special Vandermonde systems

In this paper a new algorithm for solving special Vandermonde systems is presented, useful when then points defining the matrix are thek th roots ofm complex numbers (n=km); if they are real and positive andn=2m, the usual case of real points symmetrically ranged around zero is obtained. The algorithm is based on an inverse matrix formulation by means of the Kronecker product and is particularly suitable for parallel implementation. Its computational complexity is analysed and compared both in the sequential and parallel formulation.     

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.     

The modulator of the local time

Let x(t), 0 ≦ t ≦ 1, be a real measurable function having a local time α(x, t) which is a continuous function of t for almost all x. It is also assumed that, for some m ≧ 2 and some real interval B, α^m(x, 1) is integrable over B. The modulator is a function M_m(t, B), t > 0, denned in terms of α. It is shown that the modulator serves as a measure of the smoothness of the L_m(B)-valued function α(., t) with respect to t. Then it is shown that the modulator plays a central role in precisely describing certain irregularity properties of x(t). The results are applied to the case where x(t) is the sample function of a real stochastic process. In this way new results are obtained for large classes of Gaussian and Markov processes.     

Root Configurations for Hyperbolic Polynomials of Degree 3, 4, and 5

A real polynomial of one real variable is (strictly) hyperbolic if it has only real (and distinct) roots. There are 10 (resp. 116) possible non-degenerate configurations between the roots of a strictly hyperbolic polynomial of degree 4 (resp. 5) and of its derivatives (i.e., configurations without equalities between roots). The standard Rolle theorem allows 12 (resp. 286) such configurations. The result is based on the study of the hyperbolicity domain of the family P(x,a)=x ⁿ+a ₁ x ^n-1+...+a _n for n=4,5 (i.e., of the set of values of aⁿ for which the polynomial is hyperbolic) and its stratification defined by the discriminant sets Res(P ⁽ⁱ⁾,P ^(j))=0, 0 i < jn-1.     

Parallel laguerre iterations: The complex case

Summary Consider a polynomialP(z) of degreeN whose zeros are known to lie insideN closed disks, each disk containing one and only one root. In this paper we show that if the given disks are sufficiently well separated, then the first derivative ofP(z) never vanishes inside the initial inclusion regions. The formulation of the square-root iteration in terms of circular regions is then possible and leads to an iterative scheme with degree four convergence. The corresponding algorithm makes use of circular arithmetic and in particular of the definition of square root of a disk. A criterion for the selection of the appropriate square-root set is also given. The procedure can be used to simultaneously refine all (complex or real) roots ofP(z) together with their error bounds.This work was partially supported through the Canada Council 1974–1975 Award No. W740421     

On the Malgrange condition for complex polynomials of two variables

 We show that if P  ℂ[X, Y] is nonconstant, the set K _∞ (P) of points where the Malgrange condition fails to hold coincides with the roots of a constructible polynomial in one variable. This strengthens weaker related results in the literature. The proof given here is purely analytical and bypasses the algebraic and topological arguments involved in other approaches. Applications to both the real and complex Jacobian Conjectures and to the reducibility of P-z are discussed. Received: 11 October 2001 / Revised version: 2 April 2002 Mathematics Subject Classification (2000): 12D05, 14D06, 14R15, 32B10     

An alternative-conditional functional equation and the orthogonally additive functionals

Let X be a real inner product space of dimension greater than 2 and f be a real functional defined on X. Applying some ideas from the recent studies made on the alternative-conditional functional equation

Bounding the Roots of Ideal and Open Set Polynomials

Let P be a preorder (i.e., reflexive, transitive relation) on a finite set X. The ideal polynomial of P is the function where d_k is the number of ideals (i.e. downwards closed sets) of cardinality k in P. We provide upper bounds for the moduli of the roots of ideal_P(x) in terms of the width of P. We also provide examples of preorders with roots of large moduli. The results have direct applications to the generating polynomials counting open sets in finite topologies. Received December 15, 2004     

The greatest prime factor of the integers in a short interval (III)

LetP(x) denote the greatest prime factor of II_z<n≤x+x1/2 n. In this paper, we prove thatP(x)>x ^0.723 holds true for a sufficiently largex. Project supported by the Tian Yuan Itam in the National Natural Science Foundation of China.     

Combining Binary Search and Newton′s Method to Compute Real Roots for a Class of Real Functions

We generalize a hybrid algorithm of binary search and Newton′s method to compute real roots for a class of real functions. We show that the algorithm computes a root inside (0, R] with error ϵ in O(log log(R/ϵ)) time, where one function evaluation or one arithmetic operation counts for one unit of time. This work is based on Smale′s criterion for using Newton′s method and Renegar′s result of approximating roots of polynomials.