Berlekamp/Massey Algorithms for Linearly Generated Matrix Sequences

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.

Author dc:creator

• Yuhasz, George Louis

Advisors dc:contributor.advisor

• Dr. Agnes Szanto, Committee Member
• Dr. Michael Singer, Committee Member
• Dr. Ilse Ipsen, Committee Member
• Dr. Erich Kaltofen, Committee Chair

• exact linear algebra
• linear recurrances
• generic programming

Statement dc:rights

• I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dis sertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to NC State University or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report.

Dc Identifier Other

etd-03242009-100736

OAI record oai:identifier

https://repository.lib.ncsu.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Arepository.lib.ncsu.edu%3A1840.16%2F3825