Certifying Solutions to Overdetermined and Singular Polynomial Systems over Q

on YouTube ↗31m

" summary

A practical algorithm certifies exact rational roots of overdetermined and isosingular polynomial systems by combining homotopy-computed approximations with a mixed symbolic–numeric reconstruction of a rational univariate representation, refining via Newton and exact checks to decide zeros. It avoids pessimistic worst‑case lower bounds (double‑exponential gaps) by computing the algebraic representation for the instance, is parallelizable with complexity polynomial in the output size in nondegenerate cases, and handles singular roots by deflation via Jacobian minors; examples: compress and cyclic systems (multiple and double roots) are certified.

AI-written summary · about

" chapters (15)

1. 0:00Start
2. 0:56Certifying square systems
3. 1:57Difficulties with overdetermined systems
4. 3:25alphaCertified approach
5. 7:16Observation
6. 9:59Our Algorithm on a Toy Example
7. 12:22Toy Example, Cont
8. 14:43Our results
9. 15:13Best Case Scenario
10. 16:26Worst Case Scenario
11. 16:45Certification of isosingular points
12. 18:19Isosingular Deflation
13. 20:48Example Gapresse system
14. 22:42Example cont
15. 23:25Conclusions