Certifying Zeros of Polynomial Systems Using Interval Arithmetic
Open Access
- 21 March 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 49 (1) , 1-14
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.Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft (445466444)
- European Research Council
- European Union’s Horizon 2020 (787840)
This publication has 25 references indexed in Scilit:
- Algorithm 921ACM Transactions on Mathematical Software, 2012
- Verification methods: Rigorous results using floating-point arithmeticActa Numerica, 2010
- Phase stability analysis using interval Newton method with NRTL modelFluid Phase Equilibria, 2005
- Algorithm 795ACM Transactions on Mathematical Software, 1999
- INTLAB — INTerval LABoratory1999
- A polyhedral method for solving sparse polynomial systemsMathematics of Computation, 1995
- Coefficient-parameter polynomial continuationApplied Mathematics and Computation, 1989
- Newton’s Method Estimates from Data at One Point1986
- A Test for Existence of Solutions to Nonlinear SystemsSIAM Journal on Numerical Analysis, 1977
- Newton-Algorithmen zur Bestimmung von Nullstellen mit FehlerschrankenComputing, 1969