Polynomial-division-based algorithms for computing linear recurrence relations (Q820938)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Polynomial-division-based algorithms for computing linear recurrence relations |
scientific article |
Statements
Polynomial-division-based algorithms for computing linear recurrence relations (English)
0 references
29 September 2021
0 references
In this paper the authors address the ``guessing problem'', i.e., the problem of determining, for a given finite part of an infinite multidimensional sequence, a set of recurrence relations that the sequence is likely to satisfy. This is a fundamental problem in computer algebra, which is also related to cyclic code decoding. An early work in this direction is the Berlekamp-Massey-Sakata algorithm, which is the multidimensional generalization of the celebrated Berlekamp-Massey algorithm. The authors propose a new algorithm, the so-called Polynomial Scalar-FGLM algorithm, that is completely based on polynomial arithmetic. This new algorithm is connected both to the Berlekamp-Massey-Sakata algorithm and to the previous work of the authors (scalar-FGLM algorithm). The paper is concluded by some computational experiments where the authors compare the performance of different algorithms for computing the ideal of recurrence relations for certain table families.
0 references
Gröbner bases
0 references
linear recurrent sequences
0 references
Berlekamp-Massey-Sakata algorithm
0 references
extended Euclidean algorithm
0 references
Padé approximants
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references