Computing mixed volume and all mixed cells in quermassintegral time

DOI10.1007/s10208-016-9320-1zbMath1383.65050arXiv1412.0480OpenAlexW219205466MaRDI QIDQ1683740

Gregorio Malajovich

Publication date: 1 December 2017

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.0480

zbMATH Keywords

numerical resultsmixed volumehomotopy algorithmscomplexity boundssparse polynomialstropical algebraic geometry

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Numerical computation of solutions to systems of equations (65H10) Toric varieties, Newton polyhedra, Okounkov bodies (14M25) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Enumerative problems (combinatorial problems) in algebraic geometry (14N10) Mixed volumes and related topics in convex geometry (52A39)

Related Items (9)

Do most polynomials generate a prime ideal? ⋮ A polyhedral homotopy algorithm for real zeros ⋮ The Tropical Nullstellensatz and Positivstellensatz for Sparse Polynomial Systems ⋮ Unmixing the mixed volume computation ⋮ Sparse trace tests ⋮ Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric ⋮ Efficient edge-skeleton computation for polytopes defined by oracles ⋮ Pruning Algorithms for Pretropisms of Newton Polytopes ⋮ Euclidean distance degree and mixed volume

Uses Software

• DEMiCs
• MixedVol
• PHCpack
• VolEsti

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Do most polynomials generate a prime ideal?
• Geometry of maximum likelihood estimation in Gaussian graphical models
• Mixed volume computation in parallel
• High probability analysis of the condition number of sparse polynomial systems
• Dynamic enumeration of all mixed cells
• A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor
• Computing mixed discriminants, mixed volumes, and permanents
• Efficient incremental algorithms for the sparse resultant and the mixed volume
• Mixed-volume computation by dynamic lifting applied to polynomial system solving
• Connectivity of tropicalizations
• On the expected number of zeros of nonlinear equations
• On the complexity of sparse elimination
• Computing Tropical Curves via Homotopy Continuation
• Root counts of semi-mixed systems, and an application to counting nash equilibria
• Powers of tensors and fast matrix multiplication
• Algorithm 846
• On The Complexity of Computing Mixed Volumes
• Algorithm 795
• Efficient Random-Walk Methods for Approximating Polytope Volume
• A Polyhedral Method for Solving Sparse Polynomial Systems
• Multiplying matrices faster than coppersmith-winograd
• Mixed volume computation via linear programming
• Finding mixed cells in the mixed volume computation

This page was built for publication: Computing mixed volume and all mixed cells in quermassintegral time