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.     

The number of roots of a lacunary bivariate polynomial on a line

We prove that a polynomial f∈R[x,y]$f\in \mathbb{R}[x,y]$ with t$t$ non-zero terms, restricted to a real line y=ax+b$y=ax+b$, either has at most 6t−4$6t-4$ zeros or vanishes over the whole line. As a consequence, we derive an alternative algorithm for deciding whether a linear polynomial y−ax−b∈K[x,y]$y-ax-b\in K[x,y]$ divides a lacunary polynomial f∈K[x,y]$f\in K[x,y]$, where K$K$ is a real number field. The number of bit operations performed by the algorithm is polynomial in the number of non-zero terms of f$f$, in the logarithm of the degree of f$f$, in the degree of the extension K/Q$K/\mathbb{Q}$ and in the logarithmic height of a$a$, b$b$ and f$f$.     

On the computing time of the continued fractions method

The maximum computing time of the continued fractions method for polynomial real root isolation is at least quintic in the degree of the input polynomial. This computing time is realized for an infinite sequence of polynomials of increasing degrees, each having the same coefficients. The recursion trees for those polynomials do not depend on the use of root bounds in the continued fractions method. The trees are completely described. The height of each tree is more than half the degree. When the degree exceeds one hundred, more than one third of the nodes along the longest path are associated with primitive polynomials whose low-order and high-order coefficients are large negative integers. The length of the forty-five percent highest order coefficients and of the ten percent lowest order coefficients is at least linear in the degree of the input polynomial multiplied by the level of the node. Hence the time required to compute one node from the previous node using classical methods is at least proportional to the cube of the degree of the input polynomial multiplied by the level of the node. The intervals that the continued fractions method returns are characterized using a matrix factorization algorithm.     

Generation and recognition of digital planes using multi-dimensional continued fractions

This paper extends, in a multi-dimensional framework, pattern recognition techniques for generation or recognition of digital lines. More precisely, we show how the connection between chain codes of digital lines and continued fractions can be generalized by a connection between tilings and multi-dimensional continued fractions. This leads to a new approach for generating and recognizing digital hyperplanes.     

On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers

We elaborate on a correspondence between the coefficients of a multivariate polynomial represented in the Bernstein basis and in a tensor-monomial basis, which leads to homography representations of polynomial functions that use only integer arithmetic (in contrast to the Bernstein basis) and are feasible over unbounded regions. Then, we study an algorithm to split this representation and obtain a subdivision scheme for the domain of multivariate polynomial functions. This implies a new algorithm for real root isolation, MCF, that generalizes the Continued Fraction (CF) algorithm of univariate polynomials.A partial extension of Vincent’s Theorem for multivariate polynomials is presented, which allows us to prove the termination of the algorithm. Bounding functions, projection and preconditioning are employed to speed up the scheme. The resulting isolation boxes have optimized rational coordinates, corresponding to the first terms of the continued fraction expansion of the real roots. Finally, we present new complexity bounds for a simplified version of the algorithm in the bit complexity model, and also bounds in the real RAM model for a family of subdivision algorithms in terms of the real condition number of the system. Examples computed with our C++ implementation illustrate the practical aspects of our method.     

指数函数多项式的实根分离算法

针对超越函数多项式的实根分离问题,提出了一种指数函数多项式的区间分离算法exRoot,将非多项式型实函数的实根分离问题转化为多项式正负性判定问题进而对其求解。首先,利用泰勒替换法构造目标函数的多项式区间套;然后,将指数函数的求根问题转化为多项式在区间内正负性的判定问题;最后,给出综合算法,并且试探性地应用于实特征值线性系统的可达性判定问题。所提算法在Maple中实现,输出的结果可读,且高效易行。区别于HSOLVER和数值计算方法fsolve,exRoot回避了直接讨论根的存在性问题,理论上具有终止性和完备性,且可达到任意精度,应用于最优化问题时可避免数值解带来的系统误差。     

Exact algorithms for the implementation of cauchy's rule

Cauchy's little known rule for computing a lower (or upper) bound on the values of the positive roots of a polynomial equation has proven to be of great importance; namely it constitutes an indispensable and crucial part of the fastest method existing for the isolation of the real roots of an equation, a method which was recently developed by the author of this article. In this paper efficient, exact (infinite precision) algorithms, along with their computing time analysis, are presented for the implementation of this important rule.