# Berlekamp/Massey Algorithms for Linearly Generated Matrix Sequences

Title: | Berlekamp/Massey Algorithms for Linearly Generated Matrix Sequences |

Author: | Yuhasz, George Louis |

Advisors: | Dr. Agnes Szanto, Committee Member Dr. Michael Singer, Committee Member Dr. Ilse Ipsen, Committee Member Dr. Erich Kaltofen, Committee Chair |

Abstract: | The Berlekamp/Massey algorithm computes the unique minimal generator of a linearly generated scalar sequence. The matrix generalization of the Berlekamp/Massey algorithm, the Matrix Berlekamp/Massey algorithm, computes a minimal matrix genera- tor of a linearly generated matrix sequence. The Matrix Berlekamp/Massey algorithm has applications in multivariable control theory and exact sparse linear algebra. The fraction free version of the Matrix Berlekamp/Massey algorithm can be adapted into a linear solver for block Hankel matrices. A thorough investigation of the Matrix Berlekamp/Massey algo- rithm and the fraction free Matrix Berlekamp/Massey algorithm is presented. A description of the algorithms and their invariants are given. The underlying linear algebra of the algo- rithms is explored. The connection between the update procedures of the algorithms and the nullspaces of the related matrix systems is detailed. A full definition and description of linearly generated matrix sequences and their various generators is given first as background. A new classification of all linearly generated matrix sequences is proven to exist. A complete description of the Matrix Berlekamp/ Massey algorithm and its invariants is then given. We describe a new early termination criterion for the algorithm and give a full proof of correctness for the algorithm. Our version and proof of the algorithm removes all rank and dimension constraints present in previous versions in the literature. Next a new variation of the Matrix Berlekamp/Massey algorithm is described. The fraction free Matrix Berlekamp/Massey algorithm performs its operations over integral domains. The divisions performed by the algorithm are exact. A full proof of the algorithm and its exact division is given. Finally, we describe two implementations of the Matrix Berlekamp/Massey algorithm, a Maple implementation and a C++ implementation, and compare the two implementations. The C++ implementation is done in the generic LinBox library for exact linear algebra and modeled after the Standard Template Library. |

Date: | 2009-04-28 |

Degree: | PhD |

Discipline: | Mathematics |

URI: | http://www.lib.ncsu.edu/resolver/1840.16/3825 |

## Files in this item

Files | Size | Format | View |
---|---|---|---|

etd.pdf | 729.6Kb |
View/ |