Refined bit complexity for the computation of at least onepoint per connected component of a smooth completeintersection real algebraic set
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916923309031424 |
|---|---|
| author | Elliott, Jesse Giesbrecht, Mark Gillot, Edern Din, Mohab Safey El Schost, Éric |
| author_facet | Elliott, Jesse Giesbrecht, Mark Gillot, Edern Din, Mohab Safey El Schost, Éric |
| contents | We refine the bit complexity analysis of an algorithm for the computation of at least one point per connected component of a smooth real algebraic set, yielding exponential speedup (with respect to the number of variables) compared to prior works. The algorithm which is analyzed is based on the critical point method, reducing the problem to computations of critical points associated to the restriction of generic projections on lines to the studied variety. Our refinement, and the subsequent improved complexity statement, comes from a better utilization of the multi-affine structure of polynomial systems encoding these sets of critical points. The bit-size estimates on the size of the output produced by this algorithm are also improved by this refinement. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_20607 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Refined bit complexity for the computation of at least onepoint per connected component of a smooth completeintersection real algebraic set Elliott, Jesse Giesbrecht, Mark Gillot, Edern Din, Mohab Safey El Schost, Éric Symbolic Computation We refine the bit complexity analysis of an algorithm for the computation of at least one point per connected component of a smooth real algebraic set, yielding exponential speedup (with respect to the number of variables) compared to prior works. The algorithm which is analyzed is based on the critical point method, reducing the problem to computations of critical points associated to the restriction of generic projections on lines to the studied variety. Our refinement, and the subsequent improved complexity statement, comes from a better utilization of the multi-affine structure of polynomial systems encoding these sets of critical points. The bit-size estimates on the size of the output produced by this algorithm are also improved by this refinement. |
| title | Refined bit complexity for the computation of at least onepoint per connected component of a smooth completeintersection real algebraic set |
| topic | Symbolic Computation |
| url | https://arxiv.org/abs/2508.20607 |