Gröbner bases and their application to the Cauchy problem on finitely generated affine monoids. (May 2017)

• Record Type: Journal Article
• Authors: Scheicher, Martin
• Is Part Of: Journal of symbolic computation. Volume 80:Part 2(2017)
• Page Start: 416
• Page End: 450
• Publication Date: 2017-05
• Subjects: 13P10 -- 39A06; Gröbner basis -- Generalised term order -- Cauchy problem for partial difference equations; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2016.07.002
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: For finitely generated submonoids of the integer lattice and submodules over the associated monoid algebra, we investigate Gröbner bases with respect to generalised term orders. Up to now, this theory suffered two disadvantages: The algorithm for computing the Gröbner 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 Gröbner bases to one over a polynomial ring and use the conventional Gröbner 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.