New Techniques for the Computation of Linear Recurrence Coefficients

✍ Scribed by Victor Y. Pan

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 224 KB
• Volume: 6
• Category: Article
• ISSN: 1071-5797
• DOI: 10.1006/ffta.1999.0267

✦ Synopsis

The n coe$cients of a "xed linear recurrence can be expressed through its m42n terms or, equivalently, the coe$cients of a polynomial of a degree n can be expressed via the power sums of its zeros*by means of a polynomial equation known as the key equation for decoding the BCH error-correcting codes. The same problem arises in sparse multivariate polynomial interpolation and in various fundamental computations with sparse matrices in "nite "elds. Berlekamp's algorithm of 1968 solves the key equation by using order of n operations in a "xed "eld. Several algorithms of 1975}1980 rely on the extended Euclidean algorithm and computing PadeH approximation, which yields a solution in O(n (log n) log log n) operations, though a considerable overhead constant is hidden in the &&O11 notation. We show algorithms (depending on the characteristic c of the ground "eld of the allowed constants) that simplify the solution and lead to further improvements of the latter bound, by factors ranging from order of log n, for c"0 and c'n (in which case the overhead constant drops dramatically), to order of min (c, log n), for 24c4n; the algorithms use Las Vegas type randomization in the case of 2(c4n.