Polynomial-division-based algorithms for computing linear recurrence relations (Q820938)

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.