A deterministic algorithm for isolating real roots of a real polynomial

We describe a bisection algorithm for root isolation of polynomials with real coefficients. It is assumed that the coefficients can be approximated with arbitrary precision; exact computation in the field of coefficients is not required. We refer to such coefficients as bitstream coefficients. The algorithm is simpler, deterministic and has better asymptotic complexity than the randomized algorithm of Eigenwillig et al. (2005). We also discuss a partial extension to multiple roots.     

New bivariate polynomial expansion with boundary data on the simplex

We introduce an extension to the two-dimensional simplex of the univariate two-point expansion formula for sufficiently smooth real functions introduced in [13]; it is a polynomial expansion with algebraic degree of exactness. This expansion is applied to obtain a new class of embedded boundary-type cubature formulae on the simplex.      

On the minimum of a positive polynomial over the standard simplex

We present a new positive lower bound for the minimum value taken by a polynomial P$P$ with integer coefficients in k$k$ variables over the standard simplex of R^k${\mathbb{R}}^k$, assuming that P$P$ is positive on the simplex. This bound depends only on the number of variables k$k$, the degree d$d$ and the bitsize τ$\tau$ of the coefficients of P$P$ and improves all the previous bounds for arbitrary polynomials which are positive over the simplex.     

Sorting-based localization and stable computation of zeros of a polynomial. I

A method of stable address sorting is designed for localization and approximate computation of real and complex zeros of a polynomial. In an arbitrary domain, a software implementation of the method allows one to localize and to calculate with high accuracy all zeros of a polynomial, including the case when they are ill-separated. The vicinity of each zero dynamically decreases during localizing the boundaries of the domains of all zeros. Algorithms developed are formally described in the Object Pascal language and are implemented in the Delphi 7 environment. Some upper-bound estimates of a parallel version of the method are given. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 165–182, January–February 2007.     

Classification of type I-censored bivariate data

Type I, or limits of detection censoring occurs when a random variable is only observable between fixed and known limits. The classification problem, when the feature vectors to be used to classify are bivariate type I-censored observations, is considered. A Bayes’ optimal classifier is constructed under the assumption that the underlying distribution is Gaussian and it is shown that the decision boundary between classes is not continuous as in the uncensored case. Examples of the decision boundary are presented and simulation studies are used to illustrate the methods described. The resultant classifier is applied to simulated electrical impedance tomography data and a medical data set as illustrations.     

Finding the roots of a polynomial on an MIMD multicomputer

This paper introduces the parallelization on a distributed memory multicomputer of two iterative methods for finding all the roots of a given polynomial. The parallel algorithms share the computation of the roots among the processors and perform a total exchange of the data at each step. Since the amount of communications is the main drawback of this approach, we study the effect of the network topology on the performance of the algorithms. Particularly, we show that among the different classical processors networks topologies (ring, 2d-torus or n-cube), the hypercube topology minimizes the communications. For each topology is computed the optimal number of processors. Experiments on the hypercube FPS T40 illustrate the results.     

A new general Routh-like algorithm to determine the number of RHP roots of a real or complex polynomial

A new Routh-like algorithm for determining the number of right-half plane (RHP) roots of a polynomial with real or complex coefficients is given. It includes the Routh algorithm for real polynomials as a special case. Moreover, the algorithm also applies directly to the singular case wherein the leading coefficient of a row, but not the entire row, vanishes, needing far fewer computations than the heuristicepsilon- method about which there was a vigorous discussion in these TRANSACTIONS a few years ago, and further not requiring investigation of an auxiliary polynomial. The algorithm is illustrated by a few examples. The proof of the algorithm is based on the Principle of the Argument, and thus also constitutes a simple proof of the Routh algorithm in the regular case.     

The number of limit cycles for a family of polynomial systems

In this paper, the number of limit cycles in a family of polynomial systems was studied by the bifurcation methods. With the help of a computer algebra system (e.g., Maple 7.0), we obtain that the least upper bound for the number of limit cycles appearing in a global bifurcation of systems (2.1) and (2.2) is 5n + 5 + (1 − (−1)ⁿ)/2 for c ≠ 0 and n for c ≡ 0.     

Note on the absolute value of the roots of a polynomial

Some simple formulas are derived which give bounds for the absolute value of the roots of a polynomial with complex coefficients. A conjecture on the condition for some roots to be located in certain circular regions is also proposed.     

A note on the location of the roots of a polynomial

Two new theorems and two corollaries are presented which give sufficient conditions for a polynomial to have all its roots inside the unit circle. These results unify and extend certain earlier stability tests for discrete time systems. The significance of the new results is illustrated by a couple of examples.     

On the stability radius of a Schur polynomial

The robust Schur stability of a polynomial with uncertain coefficients will be investigated. The stability hypersphere for such polynomials will be determined in terms of Tshebyshev Polynomials.     

Computation of the stability radius of a Hurwitz polynomial with diamond-like uncertainties

This paper considers the stability radius problem of Hurwitz polynomials whose coefficients have Hölder 1-norm-bounded uncertainties. We show that the solution to this problem demands the computation of the minimum of a piece-wise real-rational function ρ(λ), called the stability radius function. It is then shown that the calculations of ρ(λ) at the intersection points where ρ(λ) changes its representation and at the stationary points where ρ′(λ)=0 can be reduced to two sets of eigenvalue problems of matrices of the form H_β⁻¹H_γ, where both H_β and H_γ are frequency-independent Hurwitz matrices. Using root locus technique, we analyze this function further and prove that, in some special cases, the minimum of this function can be achieved only at the intersection points. Extensions of the eigenvalue approach to cover other robust stability problems are also discussed.     

Taylor polynomial solutions of systems of linear differential equations with variable coefficients

A Taylor collocation method has been presented for numerically solving systems of high-order linear ordinary, differential equations with variable coefficients. Using the Taylor collocation points, this method transforms the ODE system and the given conditions to matrix equations with unknown Taylor coefficients. By means of the obtained matrix equation, a new system of equations corresponding to the system of linear algebraic equations is gained. Hence by finding the Taylor coefficients, the Taylor polynomial approach is obtained. Also, the method can be used for the linear systems in the normal form. To illustrate the pertinent features of the method, examples are presented and results are compared.     

Isochronicity and normal forms of polynomial systems of ODEs

We propose a generalization of the notion of isochronicity for real polynomial autonomous systems to the case of complex two dimensional systems of ODEs. We study the generalized problem in the case of a quadratic system and a system with homogeneous cubic nonlinearities. Main tools of the study are algorithms of computational algebra based on the Groebner basis theory.     

The fastest exact algorithms for the isolation of the real roots of a polynomial equation

This paper discusses a set of algorithms which, given a polynomial equation with integer coefficients and without any multiple roots, uses exact (infinite precision) integer arithmetic and the Vincent-Uspensky-Akritas theorem to compute intervals containing the real roots of the polynomial equation. Theoretical computing time bounds are developed for these algorithms which are proven to be the fastest existing; this fact is also verified by the empirical results which are included in this article.     

On the stability of a general polynomial in the space of Markov parameters

Markov parameters and the associated stability criterion were first introduced for continuous-time real polynomials. Recently, robust stability of such polynomials was considered in Markov parameters space, where efficient robust stability tests were obtained based on the Markov theorem. This has motivated the authors to extend the above idea to more general types of polynomials, and develop Markov parameters and the associated stability criterion for complex continuous-time as well as real and complex discrete-time polynomials. Moreover, for each polynomial type, we present compact relations in order to recover the coefficients of a polynomial corresponding to a given set of Markov parameters. The stability results presented here may be useful for 1-D and 2-D filtering and control applications.