Grobner bases and their application to the Cauchy problem on finitely generated affine monoids

摘要

For finitely generated submonoids of the integer lattice and sub modules over the associated monoid algebra, we investigate Grobner bases with respect to generalised term orders. Up to now, this theory suffered two disadvantages: The algorithm for computing the Grobner bases was slow and it was not known whether there existed generalised term orders for arbitrary finitely generated submonoids. This limited the applicability of the theory. Here, we describe an algorithm which transports the problem of computing the Grobner bases to one over a polynomial ring and use the conventional Grobner theory to solve it, thus making it possible to apply known, optimised algorithms to it. Furthermore, we construct generalised term orders for arbitrary finitely generated submonoids. As an application we solve the Cauchy problem (initial value problem) for systems of linear partial difference equations over finitely generated submonoids. (C) 2016 Elsevier Ltd. All rights reserved.