#### D.4.9.4 BerlekampMassey

Procedure from library `ffmodstd.lib` (see ffmodstd_lib).

Usage:
  BerlekampMassey(L, i[, M]); L list, i int, M list

Return:
  a list Tr where f:=Tr[1] is the minimal polynomial (w.r.t. the i-th variable) generated by the sequence (L[j]), 1<=j<= Tr[2], if the length of the sequence is long enough. In this case, the coefficients c_i of the polynomial f satisfy the relation -L[j+t] = c_0*L[j] + ... + c_{t-1}*L[j+t-1] for all j >=1 where t=deg(f).

Note:
  The procedure applies the Berlekamp/Massey algorithm to the sequence L[j] (elements from the field Q) for j>0 and returns a polynomial f. If the polynomial f splits into linear factors with no multiplicity greater than one, then we say that the length of the sequence L is long enough. If this polynomial does not split into linear factors, an optional parameter M = BerlekampMassey(L',i) can be provided to add more elements to the sequence.

References:
  [1] E. Kaltofen and W.-s. Lee: Early termination in sparse interpolation algorithms. J. Symb. Comput. 36, 365-400 (2003).
  [2] E. Kaltofen, W.-s. Lee and A. A. Lobo: Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm. Proc. ISSAC (ISSAC '00), 192-201 (2000).

Example:

    LIB "ffmodstd.lib";
    ring rr=0,x,dp;
    list L = 150,3204,79272,2245968;
    list Tr = BerlekampMassey(L,1);
    Tr[1];
    ==> 117288/209x2-10662/209x+1
    factorize(Tr[1]); //not linearly factored
    ==> [1]:
    ==>    _[1]=1/209
    ==>    _[2]=117288x2-10662x+209
    ==> [2]:
    ==>    1,1
    list L1 = 70411680, 2352815424, 81496927872;
    Tr = BerlekampMassey(L1,1,Tr); // increase the length of L by size(L1)
    Tr[1];
    ==> x3-66x2+1296x-7776
    factorize(Tr[1]); //linearly factored and has distinct roots
    ==> [1]:
    ==>    _[1]=1
    ==>    _[2]=x-36
    ==>    _[3]=x-18
    ==>    _[4]=x-12
    ==> [2]:
    ==>    1,1,1,1
    Tr[2]; //the length of the sequence required to generate Tr[1]
    ==> 6

User manual for Singular version 4.4.1, 2025, generated by texi2html.