×

Gröbner bases and their application to the Cauchy problem on finitely generated affine monoids. (English) Zbl 1349.13061

Summary: 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.

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
39A06 Linear difference equations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berkesch, C.; Schreyer, F. O., Syzygies, finite length modules, and random curves, (Eisenbud, D.; Iyengar, S. B.; Singh, A. K.; Stafford, J. T.; van den Bergh, M., Commutative Algebra and Noncommutative Algebraic Geometry. Volume I: Expository Articles (2015), Cambridge University Press: Cambridge University Press Cambridge), 25-52 · Zbl 1359.13029
[2] Bourlès, H.; Marinescu, B.; Oberst, U., The injectivity of the canonical signal module for multidimensional linear systems of difference equations with variable coefficients, Multidimens. Syst. Signal Process (2015) · Zbl 1321.93053
[3] Bousquet-Mélou, M.; Petkovšek, M., Linear recurrences with constant coefficients: the multivariate case, Discrete Math., 225, 1-3, 51-75 (2000) · Zbl 0963.05005
[4] Conti, P.; Traverso, C., Buchberger algorithm and integer programming, (Applied Algebra, Algebraic Algorithms and Error-correcting Codes. Applied Algebra, Algebraic Algorithms and Error-correcting Codes, New Orleans, LA, 1991. Applied Algebra, Algebraic Algorithms and Error-correcting Codes. Applied Algebra, Algebraic Algorithms and Error-correcting Codes, New Orleans, LA, 1991, Lect. Notes Comput. Sci., vol. 539 (1991), Springer: Springer Berlin), 130-139 · Zbl 0771.13014
[5] Cox, D.; Little, J.; Schenck, H., Toric Varieties (2011), American Mathematical Society: American Mathematical Society Providence · Zbl 1223.14001
[6] Kreuzer, M.; Robbiano, L., Computational Commutative Algebra. 1 (2000), Springer: Springer Berlin · Zbl 0956.13008
[7] Lang, S., Algebra (2002), Springer: Springer New York · Zbl 0984.00001
[8] Lim, J. S., Two-dimensional signal processing, (Lim, J. S.; Oppenheim, A. V., Advanced Topics in Signal Processing (1988), Prentice-Hall: Prentice-Hall Englewood Cliffs), 338-415
[9] Miller, E.; Sturmfels, B., Combinatorial Commutative Algebra, Grad. Texts Math., vol. 227 (2005), Springer: Springer New York · Zbl 1090.13001
[10] Nekrasova, T. I., On the Cauchy problem for multidimensional difference equations in rational cone, J. Sib. Fed. Univ. Math. Phys., 8, 2, 184-191 (2015) · Zbl 1525.39009
[11] Oberst, U., Multidimensional constant linear systems, Acta Appl. Math., 20, 1-175 (1990) · Zbl 0715.93014
[12] Oberst, U.; Pauer, F., The constructive solution of linear systems of partial difference and differential equations with constant coefficients, Multidimens. Syst. Signal Process., 12, 3-4, 253-308 (2001) · Zbl 1014.35015
[13] (Park, H.; Regensburger, G., Gröbner Bases in Control Theory and Signal Processing. Gröbner Bases in Control Theory and Signal Processing, Radon Series on Computational and Applied Mathematics, vol. 3 (2007), de Gruyter) · Zbl 1130.93007
[14] Pauer, F.; Unterkircher, A., Gröbner bases for ideals in Laurent polynomial rings and their application to systems of difference equations, Appl. Algebra Eng. Commun. Comput., 9, 4, 271-291 (1999) · Zbl 0978.13017
[15] Pauer, F.; Zampieri, S., Gröbner bases with respect to generalized term orders and their application to the modelling problem, J. Symb. Comput., 21, 2, 155-168 (1996) · Zbl 0869.39001
[16] Robbiano, L., Term orderings on the polynomial ring, (EUROCAL ’85, vol. 2. EUROCAL ’85, vol. 2, Linz, 1985. EUROCAL ’85, vol. 2. EUROCAL ’85, vol. 2, Linz, 1985, Lect. Notes Comput. Sci., vol. 204 (1985), Springer: Springer Berlin), 513-517
[17] Scheicher, M., Gröbner bases over finitely generated affine monoids and applications. The direct sum case, (Proceedings of the 22nd International Symposium on the Mathematical Theory of Networks and Systems (MTNS). Proceedings of the 22nd International Symposium on the Mathematical Theory of Networks and Systems (MTNS), Minneapolis, USA (2016)), 174-181
[18] Schrijver, A., Theory of Linear and Integer Programming (1986), John Wiley & Sons: John Wiley & Sons Chichester · Zbl 0665.90063
[19] Shannon, D.; Sweedler, M., Using Gröbner bases to determine algebra membership, split surjective algebra homomorphisms determine birational equivalence, J. Symb. Comput., 6, 2-3, 267-273 (1988) · Zbl 0681.68052
[20] Sturmfels, B., Gröbner Bases and Convex Polytopes (1996), American Mathematical Society: American Mathematical Society Providence · Zbl 0856.13020
[21] Theis, C., Der Buchberger-Algorithmus für torische Ideale und seine Anwendung in der ganzzahligen Optimierung (1999), Universität des Saarlandes, Master’s thesis
[22] Zampieri, S., A solution of the Cauchy problem for multidimensional discrete linear shift-invariant systems, Linear Algebra Appl., 202, 143-162 (1994) · Zbl 0802.93036
[23] Zerz, E.; Oberst, U., The canonical Cauchy problem for linear systems of partial difference equations with constant coefficients over the complete \(r\)-dimensional integral lattice \(Z^r\), Acta Appl. Math., 31, 3, 249-273 (1993) · Zbl 0794.39005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.