On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers (Q533873): Difference between revisions

This paper develops a new algorithm for real root isolation of a system of multivariate polynomial functions. This algorithm is the multivariate extension of the novel Continued Fraction algorithm for univariate polynomials. The authors present a comprehensive complexity analysis for this algorithm and report the running times for a C++ implementation of this method which is freely available. The problem of computing roots of univariate polynomials is one of the most studied problems in mathematics and computer science. In recent years most efforts have been concentrated on subdivision-based algorithms where the localization of the roots is based on simple tests such as \textit{Descartes' Rule of Signs} or, more recently, on the computation of lower bounds of the positive real roots underlying Continued Fraction subdivision algorithms. The analysis of subdivision methods for the approximation of isolated roots of multivariate systems is much less advanced. In this paper, the authors present a new adaptive algorithm for polynomial system real solving that acts in monomial basis (as opposed to the more standard Bernstein basis representation), and exploits the continued fraction expansion of the coordinates of the real roots. This method yields the best rational approximation of the real roots. Further, all computations are performed with integers, thus this is a division-free algorithm. The authors present a thorough bit complexity analysis of the algorithm, when oracles for lower bounds and real root counting are available. In all cases, the bounds established in this paper for the multivariate case match the best known bounds for the univariate case when this method is restricted to the latter case. The authors also present bounds in the real RAM model for a family of subdivision algorithms in terms of the real \textit{condition number} of the system. In particular, the authors show that the logarithm of the condition number of the system is involved linearly in the complexity bound. The theoretical cornerstone of this new approach is a correspondence between the coefficients of a multivariate polynomial represented in the Bernstein basis and in a tensor-monomial basis. This correspondence leads to \textit{homography} representations of polynomial functions that use only integer arithmetic and are feasible over unbounded regions. The authors then develop an algorithm to split this representation and obtain a subdivision scheme for the domain of multivariate polynomial functions. Algorithm 1.1: Subdivision scheme Input: A set of equations \(f_1, \dots, f_s \in \mathbb{Z}[x_1,\dots,x_n]\) represented over a domain \(I\). Output: A list of disjoint domains, each containing exactly one real root of \(f_1 = \dots = f_s = 0\). Initialize a stack \(Q\) and push \((I, f_1, \dots, f_s)\); While \(Q\) is not empty do {\parindent=6mm\begin{itemize}\item[(a)] Pop a systen \((I, f_1, \dots, f_s)\) from \(Q\) and: \item[(b)] Perform a precondition process and/or reduction process to refine the domain. \item[(c)] Apply an exclusion test to identify if the domain contains no root. \item[(d)] Apply an inclusion test to identify if the domain contains a single root. In this case output \((I, f_1, \dots, f_s)\). \item[(e)] If both tests fail, then split the representation into a number of sub-domains and push them to \(Q\). \end{itemize}} The instance of this general scheme that the authors produce generalizes the continued fraction method for univariate polynomials; the realization of the main steps ((b)-(e)) is summarized as follows: {\parindent=6mm\begin{itemize}\item[(b)] Perform a precondition process and compute a lower bound on the roots of the system, in order to reduce the domain. \item[(c)] Apply interval analysis or sign inspection to identify if some \(f_i\) has a constant sign in the domain, i.e., if the domain does not contain a root. \item[(d)] Apply Miranda's test to identify if the domain contains a single root. In this case output \((I, f_1, \dots, f_s)\). \item[(e)] If both tests fail then split the representation at \((1,\dots,1)\) and continue. \end{itemize}}