2014/08/12 by Tulay Ayyildiz Akoglu, Jonathan D. Hauenstein, Akoglu, Tulay Ayyildiz +3
Computer Science · Mathematics · #Algebraic Geometry (math.AG) #FOS: Computer and information sciences #FOS: Mathematics #Formal Methods in Verification #Numerical Analysis (math.NA) #Numerical Methods and Algorithms #Numerical methods for differential equations #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.1408.2721
openalex publication_date 2014/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper is concerned with certifying that a given point is near an exact\nroot of an overdetermined or singular polynomial system with rational\ncoefficients. The difficulty lies in the fact that consistency of\noverdetermined systems is not a continuous property. Our certification is based\non hybrid symbolic-numeric methods to compute the exact "rational univariate\nrepresentation" (RUR) of a component of the input system from approximate\nroots. For overdetermined polynomial systems with simple roots, we compute an\ninitial RUR from approximate roots. The accuracy of the RUR is increased via\nNewton iterations until the exact RUR is found, which we certify using exact\narithmetic. Since the RUR is well-constrained, we can use it to certify the\ngiven approximate roots using alpha-theory. To certify isolated singular roots,\nwe use a determinantal form of the "isosingular deflation", which adds new\npolynomials to the original system without introducing new variables. The\nresulting polynomial system is overdetermined, but the roots are now simple,\nthereby reducing the problem to the overdetermined case. We prove that our\nalgorithms have complexity that are polynomial in the input plus the output\nsize upon successful convergence, and we use worst case upper bounds for\ntermination when our iteration does not converge to an exact RUR. Examples are\nincluded to demonstrate the approach.\n