Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 


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?)

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.