{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T00:11:03Z","timestamp":1759104663679,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"3-4","license":[{"start":{"date-parts":[[2006,9,1]],"date-time":"2006-09-01T00:00:00Z","timestamp":1157068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Commun. Comput. Algebra"],"published-print":{"date-parts":[[2006,9]]},"abstract":"<jats:p>A contemporary and exciting application of Gr\u00f6bner 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. Gr\u00f6bner 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.<\/jats:p><jats:p>While there are numerous existing algorithms to compute Gr\u00f6bner 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 Gr\u00f6bner bases of zero-dimensional ideals that is optimized for the case when the number<jats:italic>m<\/jats:italic>of points is much smaller than the number<jats:italic>n<\/jats:italic>of indeterminates. The algorithm identifies those variables that are<jats:italic>essential<\/jats:italic>, that is, in the support of the standard monomials associated to a polynomial ideal, and computes the relations in the Gr\u00f6bner basis in terms of these variables. When<jats:italic>n<\/jats:italic>is much larger than<jats:italic>m<\/jats:italic>, the complexity is dominated by<jats:italic>nm<\/jats:italic><jats:sup>3<\/jats:sup>. The algorithm has been implemented and tested in the computer algebra system<jats:italic>Macaulay 2<\/jats:italic>. We provide a comparison of its performance to the Buchberger-M\u00f6ller algorithm, as built into the system.<\/jats:p>","DOI":"10.1145\/1279721.1279722","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"67-78","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Computing Gr\u00f6bner bases of ideals of few points in high dimensions"],"prefix":"10.1145","volume":"40","author":[{"given":"Winfried","family":"Just","sequence":"first","affiliation":[{"name":"Ohio University, Athens, OH"}]},{"given":"Brandilyn","family":"Stigler","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, OH"}]}],"member":"320","published-online":{"date-parts":[[2006,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2000.0411"},{"volume-title":"Graduate Studies in Mathematics","year":"1994","author":"Adams W.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtbi.2005.05.010"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1081\/AGB-120017343"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(02)00140-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/646657.700398"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"B. Buchberger and H. M. M\u00f6ller The construction of multivariate polynomials with preassigned zeroes Computer Algebra : EUROCAM '82 (J. Calmet ed.) Lecture Notes in Computer Science vol. 144 Springer Berlin 1982 pp. 24 -- 31 . B. Buchberger and H. M. M\u00f6ller The construction of multivariate polynomials with preassigned zeroes Computer Algebra: EUROCAM '82 (J. Calmet ed.) Lecture Notes in Computer Science vol. 144 Springer Berlin 1982 pp. 24--31.","DOI":"10.1007\/3-540-11607-9_3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2003.08.009"},{"key":"e_1_2_1_10_1","unstructured":"CoCoATeam CoCoA: A system for doing Computations in Commutative Algebra Available at http:\/\/cocoa.dima.unige.it 2006 . CoCoATeam CoCoA: A system for doing Computations in Commutative Algebra Available at http:\/\/cocoa.dima.unige.it 2006."},{"key":"e_1_2_1_11_1","volume-title":"Using algebraic geometry","author":"Cox D.","year":"2005","edition":"2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11617983_11"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(99)00005-5"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/780506.780516"},{"key":"e_1_2_1_15_1","unstructured":"D. Grayson and M. Stillman Macaulay 2 a software system for research in algebraic geometry Available at http:\/\/www.math.uiuc.edu\/Macaulay2 2006 . D. Grayson and M. Stillman Macaulay 2 a software system for research in algebraic geometry Available at http:\/\/www.math.uiuc.edu\/Macaulay2 2006."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-004-0156-8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195079517.001.0001","volume-title":"Origins of order: Self-organization and selection in evolution","author":"Kauffman S.","year":"1993"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtbi.2004.04.037"},{"key":"e_1_2_1_19_1","unstructured":"M. Lederer The vanishing ideal of a finite set of closed points in affine space Available at http:\/\/arxiv.org\/abs\/math\/0604133 2006 . M. Lederer The vanishing ideal of a finite set of closed points in affine space Available at http:\/\/arxiv.org\/abs\/math\/0604133 2006."},{"key":"e_1_2_1_20_1","first-page":"103","article-title":"Gr\u00f6bner bases of ideals defined by functionals with an application to ideals of projective points, Applicable Algebra in Engineering","volume":"4","author":"Marinari M.","year":"1993","journal-title":"Communication and Computing"},{"key":"e_1_2_1_21_1","first-page":"106","volume-title":"Computational Algebraic Geometry and Commutative Algebra, Cortona-91","author":"Mora T.","year":"1993"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1017\/CBO9780511565847.010","volume-title":"Gr\u00f6bner Bases and Applications (New York)","author":"Robbiano L.","year":"1998"}],"container-title":["ACM Communications in Computer Algebra"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1279721.1279722","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1279721.1279722","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:51:33Z","timestamp":1750258293000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1279721.1279722"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9]]},"references-count":21,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2006,9]]}},"alternative-id":["10.1145\/1279721.1279722"],"URL":"https:\/\/doi.org\/10.1145\/1279721.1279722","relation":{},"ISSN":["1932-2240"],"issn-type":[{"type":"print","value":"1932-2240"}],"subject":[],"published":{"date-parts":[[2006,9]]},"assertion":[{"value":"2006-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}