Complexity of sparse polynomial solving 3: Infinity
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913904416784384 |
|---|---|
| author | Malajovich, Gregorio |
| author_facet | Malajovich, Gregorio |
| contents | A theory of numerical path-following in toric varieties was suggested in two previous papers. The motivation is solving systems of polynomials with real or complex coefficients. When those polynomials are not assumed 'dense', solving them over projective space or complex space may introduce spurious, degenerate roots or components. Spurious roots may be avoided by solving over toric varieties.
In this paper, a homotopy algorithm is locally defined on charts of the toric variety. Its complexity is bounded linearly by the condition length, that is the integral along the lifted path (coefficients and solution) of thetoric condition number. Those charts allow for stable computations near "toric infinity",which was not possible within the technology of the previous papers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_17086 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity of sparse polynomial solving 3: Infinity Malajovich, Gregorio Algebraic Geometry Numerical Analysis 65H10, 65H20, 14M25, 14Q20 G.1.5 A theory of numerical path-following in toric varieties was suggested in two previous papers. The motivation is solving systems of polynomials with real or complex coefficients. When those polynomials are not assumed 'dense', solving them over projective space or complex space may introduce spurious, degenerate roots or components. Spurious roots may be avoided by solving over toric varieties. In this paper, a homotopy algorithm is locally defined on charts of the toric variety. Its complexity is bounded linearly by the condition length, that is the integral along the lifted path (coefficients and solution) of thetoric condition number. Those charts allow for stable computations near "toric infinity",which was not possible within the technology of the previous papers. |
| title | Complexity of sparse polynomial solving 3: Infinity |
| topic | Algebraic Geometry Numerical Analysis 65H10, 65H20, 14M25, 14Q20 G.1.5 |
| url | https://arxiv.org/abs/2506.17086 |