Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Gröbner bases and gradings for partial difference ideals

Author: Roberto La Scala
Journal: Math. Comp. 84 (2015), 959-985
MSC (2010): Primary 12H10; Secondary 13P10, 16W22, 16W50
Published electronically: July 31, 2014
MathSciNet review: 3290971
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Matthias Aschenbrenner and Christopher J. Hillar, Finite generation of symmetric ideals, Trans. Amer. Math. Soc. 359 (2007), no. 11, 5171-5192. MR 2327026 (2008g:13030),
  • [2] George M. Bergman, The diamond lemma for ring theory, Adv. in Math. 29 (1978), no. 2, 178-218. MR 506890 (81b:16001),
  • [3] A. M. Bigatti, M. Caboara, and L. Robbiano, Computing inhomogeneous Gröbner bases, J. Symbolic Comput. 46 (2011), no. 5, 498-510. MR 2781934 (2012c:13061),
  • [4] 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 (2012g:13049),
  • [5] B. Buchberger, Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems, Aequationes Math. 4 (1970), 374-383 (German). MR 0268178 (42 #3077)
  • [6] Richard M. Cohn, Difference Algebra, Interscience Publishers John Wiley & Sons, New York-London-Sydeny, 1965. MR 0205987 (34 #5812)
  • [7] W. Decker, G.-M. Greuel, G. Pfister, and H. Schönemann,
    SINGULAR 3-1-5 -- A computer algebra system for polynomial computations (2012).
  • [8] David Eisenbud, Commutative Algebra, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR 1322960 (97a:13001)
  • [9] 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.
  • [10] 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.
  • [11] 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 (2007h:65084),
  • [12] 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.
  • [13] Michel Gondran and Michel Minoux, Graphs, Dioids and Semirings, New Models and Algorithms. Operations Research/Computer Science Interfaces Series, vol. 41, Springer, New York, 2008. MR 2389137 (2009g:16066)
  • [14] 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 (2006j:39002)
  • [15] Graham Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. (3) 2 (1952), 326-336. MR 0049867 (14,238e)
  • [16] 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,
  • [17] E. R. Kolchin, Differential Algebra and Algebraic Groups, Academic Press, New York, 1973. Pure and Applied Mathematics, Vol. 54. MR 0568864 (58 #27929)
  • [18] R. La Scala, Extended letterplace correspondence for nongraded noncommutative ideals and related algorithms, preprint (2012), 1-20. arXiv:1206.6027
  • [19] 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 (2010m:16031),
  • [20] 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,
  • [21] 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.
  • [22] Decio Levi, Lie symmetries for lattice equations, Note Mat. 23 (2004/05), no. 2, 139-156. MR 2141114 (2006b:37157)
  • [23] Alexander Levin, Difference Algebra, Algebra and Applications, vol. 8, Springer, New York, 2008. MR 2428839 (2009m:12010)
  • [24] 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 (2004h:81034)
  • [25] J. F. Ritt, Differential Equations From the Algebraic Standpoint. Amer. Math. Soc. Colloquium Publ., Vol. 14, AMS, New York, 1932.
  • [26] Joseph Fels Ritt, Differential Algebra, American Mathematical Society Colloquium Publications, Vol. XXXIII, American Mathematical Society, New York, N. Y., 1950. MR 0035763 (12,7c)
  • [27] Werner M. Seiler, Involution, The formal theory of differential equations and its applications in computer algebra. Algorithms and Computation in Mathematics, vol. 24, Springer-Verlag, Berlin, 2010. MR 2573958 (2011h:35003)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 12H10, 13P10, 16W22, 16W50

Retrieve articles in all journals with MSC (2010): 12H10, 13P10, 16W22, 16W50

Additional Information

Roberto La Scala
Affiliation: Dipartimento di Matematica, via Orabona 4, 70125 Bari, Italia

Keywords: Partial difference equations, Gr\"obner bases, actions on algebras, gradings on algebras
Received by editor(s): December 14, 2011
Received by editor(s) in revised form: November 6, 2012, May 30, 2013, and July 9, 2013
Published electronically: July 31, 2014
Additional Notes: The author was partially supported by Università di Bari
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society