Guessing Linear Recurrence Relations of Sequence Tuples and P-recursive Sequences with Linear Algebra

Jérémy Berthomieu 1 Jean-Charles Faugère 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : Given several $n$-dimensional sequences, we first present an algorithm for computing the Gröbner basis of their module of linear recurrence relations. A P-recursive sequence $(u_{\mathbf{i}})_{\mathbf{i}\in\mathbb{N}^n}$ satisfies linear recurrence relations with polynomial coefficients in $\mathbf{i}$, as defined by Stanley in 1980. Calling directly the aforementioned algorithm on the tuple of sequences $\left((\mathbf{i}^{\mathbf{j}}\,u_{\mathbf{i}})_{\mathbf{i}\in\mathbb{N}^n}\right)_{\mathbf{j}}$ for retrieving the relations yields redundant relations. Since the module of relations of a P-recursive sequence also has an extra structure of a $0$-dimensional right ideal of an Ore algebra, we design a more efficient algorithm that takes advantage of this extra structure for computing the relations. Finally, we show how to incorporate Gröbner bases computations in an Ore algebra $\mathbb{K}\langle t_1,\ldots,t_n,x_1,\ldots,x_n\rangle$, with commutators $x_k\,x_{\ell}-x_{\ell}\,x_k=t_k\,t_{\ell}-t_{\ell}\,t_k=t_k\,x_{\ell}-x_{\ell}\,t_k=0$ for $k\neq\ell$ and $t_k\,x_k-x_k\,t_k=x_k$, into the algorithm designed for P-recursive sequences. This allows us to compute faster the Gr\"obner basis of the ideal spanned by the first relations, such as in \textsc{2D}/\textsc{3D}-space walks examples.
Type de document :
Communication dans un congrès
41st International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, ON, Canada. pp.95-102, 2016, 〈10.1145/2930889.2930926〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01314266
Contributeur : Jérémy Berthomieu <>
Soumis le : mercredi 11 mai 2016 - 09:52:18
Dernière modification le : lundi 29 mai 2017 - 14:22:49
Document(s) archivé(s) le : mercredi 16 novembre 2016 - 00:33:36

Fichier

main_HAL.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Jérémy Berthomieu, Jean-Charles Faugère. Guessing Linear Recurrence Relations of Sequence Tuples and P-recursive Sequences with Linear Algebra. 41st International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, ON, Canada. pp.95-102, 2016, 〈10.1145/2930889.2930926〉. 〈hal-01314266〉

Partager

Métriques

Consultations de
la notice

260

Téléchargements du document

118