Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
The BMS Algorithm
verfasst von : Shojiro Sakata
Erschienen in: Gröbner Bases, Coding, and Cryptography
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present a sketch of the
n
-dimensional (
n
-D) Berlekamp–Massey algorithm (alias Berlekamp–Massey–Sakata or BMS algorithm) w.r.t.
n
-D arrays. That is: (1) How is it related to Gröbner basis? (2) What problem can it solve? (3) How does it work? (4) Its variations. First we discuss another problem closely related to our main problem, and introduce some concepts about
n
-D linear recurrences and modules of
n
-D arrays as their general solutions. These two problems are just the inverse (or rather dual) to each other, which can be solved by the Buchberger algorithm (Buchberger in Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Ph.D. thesis, Innsbruck,
1965
; J. Symb. Comput. 41(3–4):475–511,
2006
; Multidimensional systems theory, Reidel, Dordrecht, pp. 184–232,
1985
; Mora in Gröbner technology, this volume, pp. 11–25,
2009b
), and the BMS algorithm, respectively. Furthermore, we discuss some properties of BMS algorithm and its outputs, including its computational complexity, as well as several variations of the BMS algorithm.