A fraction free Matrix Berlekamp/Massey algorithm

作者：Kaltofen Erich; Yuhasz George^*

来源：Linear Algebra and Its Applications, 2013, 439(9): 2515-2526.

DOI：10.1016/j.laa.2013.06.016

• Exact division
• Linear recurrences
• Matrix recurrences
• Block Hankel systems
• Block Toeplitz systems
• Integer sequences

We describe a fraction free version of the Matrix Berlekamp/Massey algorithm. The algorithm computes a minimal matrix generator of linearly generated square matrix sequences in an integral domain. The algorithm performs all operations in the integral domain, so all divisions performed are exact. For scalar sequences, the matrix algorithm specializes to a different algorithm than the algorithm currently in the literature. This new scalar algorithm has smaller intermediate values than the known fraction free Berlekamp/Massey algorithm.

• 出版日期2013-11-1