Computing generating sets of lattice ideals and Markov bases of lattices

DOI10.1016/J.JSC.2009.04.006MaRDI QIDQ840713zbMATH OpenOpenAlexFDO

Authors Raymond Hemmecke, Peter N. Malkin

Publication date 14 September 2009

Published in Journal of Symbolic Computation (Search for Journal in Brave)

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

integer programming lattice ideals Markov bases

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Integer programming (90C10)

Abstract: In this article, we present a new algorithm for computing a generating set of a lattice ideal. This algorithm is based on a project-and-lift approach and is implemented in 4ti2. We also include a computational comparison of several existing implementations to compute such generating sets.

Review text

Let \({L}\subseteq\mathbb{Z}^n\) be a lattice. In this paper, the authors exhibit a new algorithm, called the Project-and-Lift algorithm, which computes a Markov basis of \({L}\). A Markov basis of \(L\) is by definition a finite subset \(M\) of \(L\) such that for any \(\alpha\), \(\beta\in\mathbb{N}^n\) with \(\alpha-\beta\in L\), there exists a sequence \(z_1, \ldots, z_k\in\mathbb{N}^n\) such that \(z_1=\alpha\), \(z_k=\beta\) and either \(z_i-z_{i+1}\in M\) or \(z_{i+1}-z_i\in M\) for \(i=1, \ldots, k-1\). It is known that \(M\subseteq L\) is a Markov basis of \(L\) if and only if \(J(M)=\{x^{u^+}-x^{u^-}\mid u\in M\}\) is a Gröbner basis of the lattice ideal \(I(L)=\langle x^{u^+}-x^{u^-}\mid u\in L\rangle\) in \(K[x_1, \ldots, x_n]\), where \(K\) is a field, \(x=x_1, \ldots, x_n\) are indeterminates, \(u^\pm=(u_1^\pm,\ldots, u_n^\pm)\) and \(u_i^\pm=\max\{\pm u_i,0\}\) for \(i=1, \ldots, n\). The main points of the Project-and-Lift algorithm are: (1) find a coordinate subspace \(\mathbb{R}^m\) of \(\mathbb{R}^n\) (\(m\) need not be the first \(m\) coordinates) such that one can find a Markov basis of \(p_{n,m}(L)\) easily, e.g., by using the Hermite Normal Form, where \(p_{n,m}\) is the canonical projection and (2) construct a Markov basis of \(p_{n,l+1}(L)\) from that of \(p_{n,l}(L)\). The authors show, be experiments, that Project-and-Lift algorithm is significantly faster that existing algorithms.

Recommendations

Cites work

Cited in

(28)

Describes a project that uses

Uses Software

This page was built for publication: Computing generating sets of lattice ideals and Markov bases of lattices

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