Certified homotopy tracking using the Krawczyk method
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916265540452352 |
|---|---|
| author | Duff, Timothy Lee, Kisun |
| author_facet | Duff, Timothy Lee, Kisun |
| contents | We revisit the problem of certifying the correctness of approximate solution paths computed by numerical homotopy continuation methods. We propose a conceptually simple approach based on a parametric variant of the Krawczyk method from interval arithmetic. Unlike most previous methods for certified path-tracking, our approach is applicable in the general setting of parameter homotopies commonly used to solve polynomial systems of equations. We also describe a novel preconditioning strategy and give theoretical correctness and termination results. Experiments using a preliminary implementation of the method indicate that our approach is competitive with specialized methods appearing previously in the literature, in spite of our more general setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_07053 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Certified homotopy tracking using the Krawczyk method Duff, Timothy Lee, Kisun Numerical Analysis Symbolic Computation Algebraic Geometry 65H14 We revisit the problem of certifying the correctness of approximate solution paths computed by numerical homotopy continuation methods. We propose a conceptually simple approach based on a parametric variant of the Krawczyk method from interval arithmetic. Unlike most previous methods for certified path-tracking, our approach is applicable in the general setting of parameter homotopies commonly used to solve polynomial systems of equations. We also describe a novel preconditioning strategy and give theoretical correctness and termination results. Experiments using a preliminary implementation of the method indicate that our approach is competitive with specialized methods appearing previously in the literature, in spite of our more general setting. |
| title | Certified homotopy tracking using the Krawczyk method |
| topic | Numerical Analysis Symbolic Computation Algebraic Geometry 65H14 |
| url | https://arxiv.org/abs/2402.07053 |