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

DOI10.1016/J.JSC.2019.09.001zbMATH Open1446.68201arXiv1806.00978OpenAlexW2971450578MaRDI QIDQ2188986FDOQ2188986

Authors: Jérémy Berthomieu, Jean-Charles Faugère 

Publication date: 15 June 2020

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: The Berlekamp--Massey--Sakata algorithm and the Scalar-FGLM algorithm both compute the ideal of relations of a multidimensional linear recurrent sequence.Whenever quering a single sequence element is prohibitive, the bottleneck of these algorithms becomes the computation of all the needed sequence terms. As such, having adaptive variants of these algorithms, reducing the number of sequence queries, becomes mandatory.A native adaptive variant of the Scalar-FGLM algorithm was presented by its authors, the so-called Adaptive Scalar-FGLM algorithm.In this paper, our first contribution is to make the Berlekamp--Massey--Sakata algorithm more efficient by making it adaptive to avoid some useless relation test-ings. This variant allows us to divide by four in dimension 2 and by seven in dimension 3 the number of basic operations performed on some sequence family.Then, we compare the two adaptive algorithms. We show that their behaviors differ in a way that it is not possible to tweak one of the algorithms in order to mimic exactly the behavior of the other. We detail precisely the differences and the similarities of both algorithms and conclude that in general the Adaptive Scalar-FGLM algorithm needs fewer queries and performs fewer basic operations than the Adaptive Berlekamp--Massey--Sakata algorithm.We also show that these variants are always more efficient than the original algorithms.

Full work available at URL: https://arxiv.org/abs/1806.00978

Recommendations

• On Berlekamp-Massey and Berlekamp-Massey-Sakata algorithms
• Polynomial-division-based algorithms for computing linear recurrence relations
• Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences
• Guessing Gröbner bases of structured ideals of relations of sequences
• The Berlekamp-Massey algorithm revisited

zbMATH Keywords

[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Gr%EF%BF%BD%EF%BF%BDbner+basis+computation&go=Go Gr��bner basis computation]BMS algorithmalgorithms comparisonmultidimensional linear recurrent sequenceSCALAR-FGLM algorithm

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Cites Work

• Ideals, Varieties, and Algorithms
• Using Algebraic Geometry
• Title not available (Why is that?)
• On a class of error correcting binary group codes
• Shift-register synthesis and BCH decoding
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Basic analytic combinatorics of directed lattice paths
• Walks confined in a quadrant are not always D-finite
• Walks with small steps in the quarter plane
• On 3-dimensional lattice walks confined to the positive octant
• Decoding of differential AG codes
• Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems
• Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices
• On the matrix berlekamp-massey algorithm
• Sparse FGLM algorithms
• The correction capability of the Berlekamp-Massey-Sakata algorithm with majority voting
• Decoding binary 2-D cyclic codes by the 2-D Berlekamp-Massey algorithm
• Extension of the Berlekamp-Massey algorithm to N dimensions
• Finding a minimal set of linear recurring relations capable of generating a given finite two-dimensional array
• A simple Hankel interpretation of the Berlekamp-Massey algorithm
• Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences
• Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences
• Finding a basis for the characteristic ideal of an n-dimensional linear recurring sequence
• The BMS Algorithm
• A Polynomial-Division-Based Algorithm for Computing Linear Recurrence Relations
• Guessing Linear Recurrence Relations of Sequence Tuplesand P-recursive Sequences with Linear Algebra
• A fraction free matrix Berlekamp/Massey algorithm
• Fast Decoding of Dual Multipoint Codes From Algebraic Curves Up to the Kirfel–Pellikaan Bound
• The dynamic dictionary of mathematical functions (DDMF)

Cited In (2)

• Polynomial-division-based algorithms for computing linear recurrence relations
• Guessing Gröbner bases of structured ideals of relations of sequences

Uses Software

• DDMF

This page was built for publication: In-depth comparison of the Berlekamp-Massey-Sakata and the Scalar-FGLM algorithms: the adaptive variants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2188986)