2014 | OriginalPaper | Chapter
A Note on Global Newton Iteration Over Archimedean and Non-Archimedean Fields
Authors : Jonathan D. Hauenstein, Victor Y. Pan, Agnes Szanto
Published in: Computer Algebra in Scientific Computing
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.