Characterization of the Affine Solutions of Sparse Polynomial Systems

on YouTube ↗26m

" summary

Gives a combinatorial characterization of affine components of sparse polynomial systems and a probabilistic symbolic algorithm that computes geometric resolutions of each component by reducing to zero-dimensional sparse solves and Newton lifting; complexity is polynomial in n, support sizes, degrees, mixed volumes and a fine-mixed-subdivision invariant but can blow up because there can be 2^n components; degree bounds are improved for square systems; uses homotopy to produce a witness-point superset for non-generic inputs and no full implementation yet.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 1:52Geometric resolution
3. 3:25Sets of zeros of sparse polynomial systems
4. 7:34Algorithm for the toric case
5. 10:03Components in the affine space
6. 10:51Combinatorial description of V(F)
7. 12:20Algorithm GenericAffineSolve for generic sparse systems
8. 13:52The result for generic sparse systems
9. 15:00Unmixed case
10. 17:14Non-generic sparse systems
11. 19:08Solving non-generic square sparse systems
12. 20:16Algorithm PointsInEquidComps for non-generic square sparse systems
13. 20:57The result for non-generic square sparse systems