Computing Gröbner bases of ideals of few points in high dimensions

DOI10.1145/1279721.1279722MaRDI QIDQ5269710zbMATH OpenOpenAlexFDO

Authors Winfried Just, Brandilyn Stigler

Publication date 27 June 2017

Published in ACM Communications in Computer Algebra (Search for Journal in Brave)

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

zbMATH Keywords

run-time complexityGröbner basesessential variablesBuchberger-Möller algorithmcomputational biology applications

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) General biology and biomathematics (92B05)

Abstract: A contemporary and exciting application of Groebner bases is their use in computational biology, particularly in the reverse engineering of gene regulatory networks from experimental data. In this setting, the data are typically limited to tens of points, while the number of genes or variables is potentially in the thousands. As such data sets vastly underdetermine the biological network, many models may fit the same data and reverse engineering programs often require the use of methods for choosing parsimonious models. Grobner bases have recently been employed as a selection tool for polynomial dynamical systems that are characterized by maps in a vector space over a finite field. While there are numerous existing algorithms to compute Groebner bases, to date none has been specifically designed to cope with large numbers of variables and few distinct data points. In this paper, we present an algorithm for computing Grobner bases of zero-dimensional ideals that is optimized for the case when the number m of points is much smaller than the number n of indeterminates. The algorithm identifies those variables that are essential, that is, in the support of the standard monomials associated to a polynomial ideal, and computes the relations in the Groebner bases in terms of these variables. When n is much larger than m, the complexity is dominated by nm^3. The algorithm has been implemented and tested in the computer algebra system Macaulay 2. We provide a comparison of its performance to the Buchberger-Moeller algorithm, as built into the system.

Recommendations

• On the complexity of computing critical points with Gröbner bases
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Gröbner bases of ideals defined by functionals with an application to ideals of projective points
• scientific article; zbMATH DE number 5375015
• The number of Gröbner bases in finite fields (research)

Cited in

(9)

• Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
• On the complexity of computing critical points with Gröbner bases
• Threaded Gröbner bases: a Macaulay2 package
• A bivariate preprocessing paradigm for the Buchberger-Möller algorithm
• scientific article; zbMATH DE number 4214184 (Why is no real title available?)
• The number of Gröbner bases in finite fields (research)
• Computation of Janet bases for toric ideals
• Degröbnerization: a political manifesto
• Common eigenvector approach to exact order reduction for Roesser state-space models of multidimensional systems

Describes a project that uses

Uses Software

• Macaulay2

This page was built for publication: Computing Gröbner bases of ideals of few points in high dimensions

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