alphaCertified: certifying solutions to polynomial systems
For researchers and practitioners solving polynomial systems, this provides a practical tool for certifying solutions with rigorous mathematical guarantees.
The paper presents alphaCertified, a program that uses Smale's alpha-theory to certify solutions to polynomial systems, providing rigorous guarantees that Newton's method converges quadratically to solutions. It handles both exact rational and arbitrary precision floating point arithmetic, and includes algorithms for certifying real solutions and heuristically validating overdetermined systems.
Smale's alpha-theory uses estimates related to the convergence of Newton's method to give criteria implying 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 to polynomial systems using both exact rational arithmetic and arbitrary precision floating point arithmetic. It also implements an algorithm to certify whether a given point corresponds to a real solution to a real polynomial system, as well as algorithms to heuristically validate solutions to overdetermined systems. Examples are presented to demonstrate the algorithms.