Algorithm 921: alphaCertified: Certifying Solutions to Polynomial Systems
Smale's alpha-theory uses estimates related to the convergence of Newton's method to certify that Newton iterations will converge quadratically to solutions to a square polynomial system. The program alphaCertified implements algorithms based on alpha-theory to certify solutions of polynomial systems using both exact rational arithmetic and arbitrary precision floating point arithmetic. It also implements algorithms that certify whether a given point corresponds to a real solution, and algorithms to heuristically validate solutions to overdetermined systems. Examples are presented to demonstrate the algorithms.
algorithms certified solutions polynomial system verification alpha theory numerical algebraic geometry