The indomitable Berlekamp/Massey algorithm
Erich Kaltofen (North Carolina State University, USA)
The numbers 1,1,2,3,5,8,13,21,... are linearly generated. But how to compute the generator from an initial segement of the sequence? And how long a segment? And how to update the recursion when an element down the line doesn't fit. The Toeplitz solvers up to the early 1960s couldn't, until Elwyn Berlekamp's 1967 BCH decoding algorithm.
My talk will give a simple self-contained explanation on the workings of the classical Berlekamp-Massey algorithm, based structured column echelon forms, i.e., sigma bases. I shall also mention a Berlekamp/Massey algorithm for linearly generated matrix sequences with early termination, Fatou's 1906 lemma, a fraction free algorithm for normalizable linearly generated matrix sequences, and explicit counts how many Toeplitz matrices with entries prescribed to fixed values or ranging over a finite field are singular.
This is joint work with George Yuhasz.