Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The Berlekamp-Massey algorithm revisited
Atti N., Diaz–Toca G., Lombardi H. Applicable Algebra in Engineering, Communication and Computing17 (1):75-82,2006.Type:Article
Date Reviewed: Jan 22 2008

The authors of this paper “propose a slight modification of the Berlekamp-Massey algorithm for obtaining the minimal polynomial of a given linearly recurrent sequence.”

After reading the paper several times, I was only able to discover two differences between algorithm one, which is the usual Berlekamp-Massey algorithm, and algorithm two, which is the new one. The first difference is the occurrence of the local variable m, which gets an initial value and does not vary. The second is that the extended Euclidean algorithm is performed, in the first case, for the polynomials x2n and P(x), and in the second case for x2n and x° PP(1/x), where the coefficients of P(x) are members of a linear recursive sequence.

The authors state that both algorithms find the minimal polynomial of the sequence, but I am not convinced that their proof is complete.

Reviewer:  A. Pethö Review #: CR135132 (0811-1095)
Bookmark and Share
 
Computations On Polynomials (F.2.1 ... )
 
 
Linear Systems (Direct And Iterative Methods) (G.1.3 ... )
 
 
Recurrences And Difference Equations (G.2.1 ... )
 
 
Combinatorics (G.2.1 )
 
 
Numerical Linear Algebra (G.1.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Computations On Polynomials": Date
Complexity of sentences over number rings
Tung S. SIAM Journal on Computing 20(1): 126-143, 1991. Type: Article
Sep 1 1991
On zero-testing and interpolation of -sparse multivariate polynomials over finite fields
Clausen M. (ed), Dress A., Grabmeier J., Karpinski M. (ed) Theoretical Computer Science 84(2): 151-164, 1991. Type: Article
Oct 1 1992
Lectures on the complexity of bilinear problems
de Groote H., Springer-Verlag New York, Inc., New York, NY, 1987. Type: Book (9789780387172057)
Mar 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy