Sparse systems and algorithmic equidimensional decomposition

2025/05/12 by Herrero, Maria Isabel, Jeronimo, Gabriela, Sabia, Juan
#13P15 #14Q20 #68W30 #Algebraic Geometry (math.AG) #FOS: Mathematics

paper · doi:10.48550/arxiv.2505.08097

Abstract

We present a new probabilistic algorithm that characterizes the equidimensional components of the affine algebraic variety defined by an arbitrary sparse polynomial system with prescribed supports. For each equidimensional component, the algorithm computes a witness set, namely a finite set obtained by intersecting the component with a generic linear variety of complementary dimension. The complexity of the algorithm is polynomial in combinatorial invariants associated to the supports of the polynomials involved.

Citations

• A Direttissimo Algorithm for Equidimensional Decomposition
• General witness sets for numerical algebraic geometry
• Solving Decomposable Sparse Systems
• Solving polynomial systems via homotopy continuation and monodromy
• Affine solution sets of sparse polynomial systems
• Deformation techniques for sparse systems
• Why Polyhedra Matter in Non-Linear Equation Solving
• The computational complexity of the Chow form
• Straight--Line Programs in Geometric Elimination Theory

Related

• Affine solution sets of sparse polynomial systems
• Elimination for generic sparse polynomial systems
• The computational complexity of the Chow form
• Deformation techniques for sparse systems
• A Direttissimo Algorithm for Equidimensional Decomposition