Gröbner bases and gradings for partial difference ideals

La Scala, Roberto

doi:10.1090/S0025-5718-2014-02859-7

Gröbner bases and gradings for partial difference ideals
HTML articles powered by AMS MathViewer

by Roberto La Scala PDF

Math. Comp. 84 (2015), 959-985 Request permission

Abstract:

In this paper we introduce a working generalization of the theory of Gröbner bases for algebras of partial difference polynomials with constant coefficients. One obtains symbolic (formal) computation for systems of linear or non-linear partial difference equations arising, for instance, as discrete models or by the discretization of systems of differential equations. From an algebraic viewpoint, the algebras of partial difference polynomials are free objects in the category of commutative algebras endowed with the action by endomorphisms of a monoid isomorphic to $\mathbb {N}^r$. Then, the investigation of Gröbner bases in this context contributes also to the current research trend consisting in studying polynomial rings under the action of suitable symmetries that are compatible with effective methods. Since the algebras of difference polynomials are not Noetherian, we propose in this paper a theory for grading them that provides a Noetherian subalgebra filtration. This implies that the variants of Buchberger’s algorithm we developed for difference ideals terminate in the finitely generated graded case when truncated up to some degree. Moreover, even in the non-graded case, we provide criterions for certifying completeness of eventually finite Gröbner bases when they are computed within sufficiently large bounded degrees. We generalize also the concepts of homogenization and saturation, and related algorithms, to the context of difference ideals. The feasibility of the proposed methods is shown by an implementation in Maple that is the first to provide computations for systems of non-linear partial difference equations. We make use of a test set based on the discretization of concrete systems of non-linear partial differential equations.

References

Matthias Aschenbrenner and Christopher J. Hillar, Finite generation of symmetric ideals, Trans. Amer. Math. Soc. 359 (2007), no. 11, 5171–5192. MR 2327026, DOI 10.1090/S0002-9947-07-04116-5
George M. Bergman, The diamond lemma for ring theory, Adv. in Math. 29 (1978), no. 2, 178–218. MR 506890, DOI 10.1016/0001-8708(78)90010-5
A. M. Bigatti, M. Caboara, and L. Robbiano, Computing inhomogeneous Gröbner bases, J. Symbolic Comput. 46 (2011), no. 5, 498–510. MR 2781934, DOI 10.1016/j.jsc.2010.10.002
Andries E. Brouwer and Jan Draisma, Equivariant Gröbner bases and the Gaussian two-factor model, Math. Comp. 80 (2011), no. 274, 1123–1133. MR 2772115, DOI 10.1090/S0025-5718-2010-02415-9
B. Buchberger, Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems, Aequationes Math. 4 (1970), 374–383 (German). MR 268178, DOI 10.1007/BF01844169
Richard M. Cohn, Difference algebra, Interscience Publishers John Wiley & Sons, New York-London-Sydeny, 1965. MR 0205987
W. Decker, G.-M. Greuel, G. Pfister, and H. Schönemann, Singular 3-1-5 — A computer algebra system for polynomial computations (2012). http://www.singular.uni-kl.de
David Eisenbud, Commutative algebra, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR 1322960, DOI 10.1007/978-1-4612-5350-1
V. P. Gerdt, Consistency analysis of finite difference approximations to PDE systems. In: Adam G. et al. (Eds.), Proc. of Mathematical Modeling and Computational Physics. MMCP 2011, 28–42, Lecture Notes in Comput. Sci., 7175, Springer, Heidelberg, 2012.
V. P. Gerdt and Y. A. Blinkov, Involution and difference schemes for the Navier-Stokes equations. In: Gerdt V.P. et al. (Eds.), Proc. of Computer Algebra in Scientific Computing. CASC 2009, 94–105, Lecture Notes in Comput. Sci., 5743, Springer, Berlin, 2009.
Vladimir P. Gerdt, Yuri A. Blinkov, and Vladimir V. Mozzhilkin, Gröbner bases and generation of difference schemes for partial differential equations, SIGMA Symmetry Integrability Geom. Methods Appl. 2 (2006), Paper 051, 26. MR 2240724, DOI 10.3842/SIGMA.2006.051
V. P. Gerdt and D. Robertz, A Maple package for computing Gröbner bases for linear recurrence relations. Nucl. Instrum. Methods, 599 (2006), 215–219. http://wwwb.math.rwth-aachen.de/Janet
Michel Gondran and Michel Minoux, Graphs, dioids and semirings, Operations Research/Computer Science Interfaces Series, vol. 41, Springer, New York, 2008. New models and algorithms. MR 2389137
E. A. Grove and G. Ladas, Periodicities in nonlinear difference equations, Advances in Discrete Mathematics and Applications, vol. 4, Chapman & Hall/CRC, Boca Raton, FL, 2005. MR 2193366
Graham Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. (3) 2 (1952), 326–336. MR 49867, DOI 10.1112/plms/s3-2.1.326
Christopher J. Hillar and Abraham Martín del Campo, Finiteness theorems and algorithms for permutation invariant chains of Laurent lattice ideals, J. Symbolic Comput. 50 (2013), 314–334. MR 2996883, DOI 10.1016/j.jsc.2012.06.006
E. R. Kolchin, Differential algebra and algebraic groups, Pure and Applied Mathematics, Vol. 54, Academic Press, New York-London, 1973. MR 0568864
R. La Scala, Extended letterplace correspondence for nongraded noncommutative ideals and related algorithms, preprint (2012), 1–20. arXiv:1206.6027
Roberto La Scala and Viktor Levandovskyy, Letterplace ideals and non-commutative Gröbner bases, J. Symbolic Comput. 44 (2009), no. 10, 1374–1393. MR 2543425, DOI 10.1016/j.jsc.2009.03.002
Roberto La Scala and Viktor Levandovskyy, Skew polynomial rings, Gröbner bases and the letterplace embedding of the free associative algebra, J. Symbolic Comput. 48 (2013), 110–131. MR 2980469, DOI 10.1016/j.jsc.2012.05.003
V. Levandovskyy and B. Martin, A symbolic approach to generation and analysis of finite difference schemes of partial differential equations. In: Langer U. et al. (Eds.), Numerical and Symbolic Scientific Computing: Progress and Prospects. Springer (2012), 123–156.
Decio Levi, Lie symmetries for lattice equations, Note Mat. 23 (2004/05), no. 2, 139–156. MR 2141114
Alexander Levin, Difference algebra, Algebra and Applications, vol. 8, Springer, New York, 2008. MR 2428839, DOI 10.1007/978-1-4020-6947-5
David A. Meyer and Noland Wallach, Invariants for multiple qubits: the case of 3 qubits, Mathematics of quantum computation, Comput. Math. Ser., Chapman & Hall/CRC, Boca Raton, FL, 2002, pp. 77–97. MR 2007943
J. F. Ritt, Differential Equations From the Algebraic Standpoint. Amer. Math. Soc. Colloquium Publ., Vol. 14, AMS, New York, 1932.
Joseph Fels Ritt, Differential Algebra, American Mathematical Society Colloquium Publications, Vol. XXXIII, American Mathematical Society, New York, N. Y., 1950. MR 0035763
Werner M. Seiler, Involution, Algorithms and Computation in Mathematics, vol. 24, Springer-Verlag, Berlin, 2010. The formal theory of differential equations and its applications in computer algebra. MR 2573958, DOI 10.1007/978-3-642-01287-7