Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

In-depth comparison of the Berlekamp – Massey – Sakata and the Scalar-FGLM algorithms: the non adaptive variants

Jérémy Berthomieu 1 Jean-Charles Faugère 1
1 PolSys - Polynomial Systems
Inria de Paris, LIP6 - Laboratoire d'Informatique de Paris 6
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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [40 references]  Display  Hide  Download

https://hal.inria.fr/hal-01516708
Contributor : Jérémy Berthomieu <>
Submitted on : Wednesday, September 20, 2017 - 5:43:27 PM
Last modification on : Friday, January 8, 2021 - 5:44:01 PM

Files

main_part1.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

  • HAL Id : hal-01516708, version 2
  • ARXIV : 1709.07168

Citation

Jérémy Berthomieu, Jean-Charles Faugère. In-depth comparison of the Berlekamp – Massey – Sakata and the Scalar-FGLM algorithms: the non adaptive variants. 2017. ⟨hal-01516708v2⟩

Share

Metrics

Record views

779

Files downloads

377