Complexity Of Computing Complex Zeros Of Structured Polynomial Systems

on YouTube ↗59m

" summary

An algorithm black box solve uses randomized homotopy continuation on unitary-orbit inputs to compute an approximate zero with probability ≥ 1 − ε under a regularity (square‑free) promise, charging O(L(F) · (Γ(F) log Γ(F) + log(1/ε)) · poly(N,D)) arithmetic steps on average, where L(F) counts black‑box evaluations and Γ is the gamma parameter controlling Newton radius. For Gaussian algebraic branching programs Γ^2 ≤ O(D^3(D + N log D)) so the expected cost is polynomial in N, D and L; step sizes and higher derivatives are estimated by randomized interpolation sampling and the method terminates almost surely.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 1:25Problem Statement
3. 4:10Homotopic continuation
4. 7:15The problem with dense models
5. 8:09What does structured mean
6. 10:20Blackbox solve
7. 16:08Unitary invariance
8. 18:25Probabilistic analysis
9. 23:33Questions
10. 26:25Model
11. 28:37Algebraic Branching
12. 30:57Consequence
13. 34:15What is behind
14. 43:02Numerical continuation
15. 50:52Smooth Analysis