Mixed Volume Computation in (another) Mixed Volume Time
summary
Presents a randomized algorithm that replaces exhaustive combinatorics with a geometry-driven bound proportional to mixed volumes, using Legendre transforms, Legendre transform and tropical curve exploration, and recursive cuts by random affine hyperplanes to compute the lower mixed subdivision. Claims near-output-sensitive complexity (geometric term VD tied to mixed volumes) and reports a concrete speedup: 613 seconds for Katsura17 vs ~21 hours in a prior implementation. Implementation works but needs numerical care and randomization for connectivity.
AI-written summary · about
chapters (9)
- 0:00Mixed volume computation intro
- 6:29Mixed volume structure for homotopy
- 11:35Live mixed volume calculation
- 18:24Geometric tools for new algorithm
- 24:05Visualizing mixed cells in tropical geometry
- 27:16Tropical curves and connectivity
- 30:09Recursive algorithm with random hyperplanes
- 33:23Complexity and stability challenges
- 34:48Acoustics model example and conclusion