A priori bounds for certified Krawczyk homotopy tracking
arXiv:2512.01355
Abstract
We establish the first complexity analysis for Krawczyk-based certified homotopy tracking. It consists of explicit a priori stepsize bounds ensuring the success of the Krawczyk test, and an iteration count bound proportional to the weighted length of the solution path. Our a priori bounds reduce the overhead of interval arithmetic, resulting in fewer iterations than previous methods. Experiments using a proof-of-concept implementation validate the results.
16 pages, 1 figure, 3 tables