Towards Mixed Gröbner Basis Algorithms

DOI10.1145/3208976.3209018MaRDI QIDQ5120180zbMATH OpenOpenAlexFDO

Authors Matías R. Bender, Jean-Charles Faugère, Elias P. Tsigaridas

Publication date 9 September 2020

Published in Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

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

zbMATH Keywords

Gröbner basismixed sparse Gröbner basismultihomogeneous polynomial systemsolving polynomial systemsparse polynomial systemtoric variety

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Symbolic computation and algebraic computation (68W30)

Abstract: One of the biggest open problems in computational algebra is the design of efficient algorithms for Gr{"o}bner basis computations that take into account the sparsity of the input polynomials. We can perform such computations in the case of unmixed polynomial systems, that is systems with polynomials having the same support, using the approach of Faug{`e}re, Spaenlehauer, and Svartz [ISSAC'14]. We present two algorithms for sparse Gr{"o}bner bases computations for mixed systems. The first one computes with mixed sparse systems and exploits the supports of the polynomials. Under regularity assumptions, it performs no reductions to zero. For mixed, square, and 0-dimensional multihomogeneous polynomial systems, we present a dedicated, and potentially more efficient, algorithm that exploits different algebraic properties that performs no reduction to zero. We give an explicit bound for the maximal degree appearing in the computations.

Recommendations

• Sparse Gröbner bases: the unmixed case
• Gröbner basis over semigroup algebras. Algorithms and applications for sparse polynomial systems
• The Sparse Basis Problem and Multilinear Algebra
• scientific article; zbMATH DE number 503188
• Gröbner basis methods in mixture experiments and generalisations
• scientific article; zbMATH DE number 4137921
• Computing a structured Gröbner basis approximately
• scientific article; zbMATH DE number 1263330
• scientific article; zbMATH DE number 1254280
• On the relation between the MXL family of algorithms and Gröbner basis algorithms

Cited in

(11)

• Guessing Gröbner bases of structured ideals of relations of sequences
• Numerical root finding via Cox rings
• Chordal graphs in triangular decomposition in top-down style
• Sparse Gröbner bases: the unmixed case
• Toric eigenvalue methods for solving sparse polynomial systems
• Gröbner basis over semigroup algebras. Algorithms and applications for sparse polynomial systems
• Koszul-type determinantal formulas for families of mixed multilinear systems
• Mixed subdivisions suitable for the greedy Canny-Emiris formula
• Yet another eigenvalue algorithm for solving polynomial systems
• Bigraded Castelnuovo-Mumford regularity and Gröbner bases
• Solving bihomogeneous polynomial systems with a zero-dimensional projection

This page was built for publication: Towards Mixed Gröbner Basis Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5120180)