Search

Let \(f_1, \ldots , f_m\) be univariate polynomials with rational coefficients and \(\mathcal {I}:=\langle f_1, \ldots , f_m\rangle \subset {\mathbb Q}[x]\) be the ideal they generate. Assume that we are given approximations \(\{z_1, \ldots , z_k\}\subset \mathbb {Q}[i]\) for the common roots \(\{\xi _1, \ldots , \xi _k\}=V(\mathcal {I})\subseteq {\mathbb C}\). In this study, we describe a symbolic-numeric algorithm to construct a rational matrix, called Hermite matrix, from the approximate roots \(\{z_1, \ldots , z_k\}\) and certify that this matrix is the true Hermite matrix corresponding to the roots \(V({\mathcal I})\). Applications of Hermite matrices include counting and locating real roots of the polynomials and certifying their existence.

In this paper, we study iterative methods on the coefficients of the rational univariate representation (RUR) of a given algebraic set, called a global Newton iterations. We compare two natural approaches to define locally quadratically convergent iterations: the first one involves Newton iteration applied to the approximate roots individually and then interpolation to find the RUR of these approximate roots; the second one considers the coefficients in the exact RUR as zeroes of a high dimensional map defined by polynomial reduction and applies Newton iteration on this map. We prove that over fields with a p-adic valuation these two approaches give the same iteration function. However, over fields equipped with the usual Archimedean absolute value they are not equivalent. In the latter case, we give explicitly the iteration function for both approaches. Finally, we analyze the parallel complexity of the different versions of the global Newton iteration, compare them, and demonstrate that they can be efficiently computed. The motivation for this study comes from the certification of approximate roots of overdetermined and singular polynomial systems via the recovery of an exact RUR from approximate numerical data.