Certifying Zeros of Polynomial Systems Using Interval Arithmetic
Paul Breiding, Kemal Rose, Sascha Timme
Abstract
We establish interval arithmetic as a practical tool for certification in numerical algebraic geometry. Our software HomotopyContinuation.jl now has a built-in function certify , which proves the correctness of an isolated nonsingular solution to a square system of polynomial equations. The implementation rests on Krawczyk’s method. We demonstrate that it dramatically outperforms earlier approaches to certification. We see this contribution as a powerful new tool in numerical algebraic geometry, which can make certification the default and not just an option.
Topics & Concepts
Interval arithmeticInvertible matrixPolynomialInterval (graph theory)CertificationCorrectnessMathematicsFunction (biology)Algebraic equationComputer scienceAlgebraic numberArithmeticSquare (algebra)Real algebraic geometryAlgebra over a fieldDiscrete mathematicsAlgorithmPure mathematicsMathematical analysisGeometryCombinatoricsEvolutionary biologyNonlinear systemBiologyPolitical sciencePhysicsLawQuantum mechanicsBounded functionPolynomial and algebraic computationNumerical Methods and AlgorithmsCryptography and Residue Arithmetic