2015/03/30 by Jesús A. De Loera, De Loera, Jesús A., Sonja Petrović +3
Computer Science · Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Algebraic Geometry (math.AG) #Combinatorics (math.CO) #Commutative Algebra (math.AC) #Commutative Algebra and Its Applications #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.1503.08804
openalex publication_date 2015/03/30 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
This paper transfers a randomized algorithm, originally used in geometric\noptimization, to computational problems in commutative algebra. We show that\nClarkson's sampling algorithm can be applied to two problems in computational\nalgebra: solving large-scale polynomial systems and finding small generating\nsets of graded ideals. The cornerstone of our work is showing that the theory\nof violator spaces of G "artner et al. applies to polynomial ideal problems.\nTo show this, one utilizes a Helly-type result for algebraic varieties. The\nresulting algorithms have expected runtime linear in the number of input\npolynomials, making the ideas interesting for handling systems with very large\nnumbers of polynomials, but whose rank in the vector space of polynomials is\nsmall (e.g., when the number of variables and degree is constant).\n