2014/04/17 by Jonathan D. Hauenstein, Victor Y. Pan, Hauenstein, Jonathan D. +3
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA) #Numerical Methods and Algorithms #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.1404.5525
openalex publication_date 2014/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study iterative methods on the coefficients of the rational univariate representation (RUR) of a given algebraic set, called global Newton iteration. 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, but 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.