Algorithm 921

Abstract

Smale’s α -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 α -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.