Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleThe BMS algorithm.
Author(s) Shojiro Sakata
TypeBook, Chapter in Book, Conference Proceeding
AbstractWe 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.
ISBN978-3-540-93805-7/hbk; 978-3-5
URL http://link.springer.com/chapter/10.1007%2F978-3-540-93806-4_9
PublisherBerlin: Springer
Translation No
Refereed No