In-depth comparison of the Berlekamp -- Massey -- Sakata and the Scalar-FGLM algorithms: the non adaptive variants
Preprint
Abstract
We compare thoroughly the Berlekamp -- Massey -- Sakata algorithm and the Scalar-FGLM algorithm, which compute both the ideal of relations of a multi-dimensional linear recurrent sequence. Suprisingly, their behaviors differ. We detail in which way they do and prove that it is not possible to tweak one of the algorithms in order to mimic exactly the behavior of the other.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Sparse FGLM algorithmsJournal of Symbolic Computation, 2017
- A fraction free Matrix Berlekamp/Massey algorithmLinear Algebra and its Applications, 2013
- Symmetric tensor decompositionLinear Algebra and its Applications, 2010
- Walks with small steps in the quarter plane2010
- Basic analytic combinatorics of directed lattice pathsTheoretical Computer Science, 2002
- Fast rational interpolation, Reed-Solomon decoding, and the linear complexity profiles of sequencesIEEE Transactions on Information Theory, 1997
- Extension of the Berlekamp-Massey algorithm to N dimensionsInformation and Computation, 1990
- A simple Hankel interpretation of the Berlekamp-Massey algorithmLinear Algebra and its Applications, 1989
- Finding a minimal set of linear recurring relations capable of generating a given finite two-dimensional arrayJournal of Symbolic Computation, 1988
- On a class of error correcting binary group codesInformation and Control, 1960