Ticket #12177: toom_matrix.py

from sage.all import PolynomialRing, MatrixSpace, cached_function

@cached_function
def toom_matrix(K):
    d = K.degree()
    D = 2*d-1
    k = K.prime_subfield()
    if k.order()<D:
        raise ValueError, "The prime field is too small"
    v = K.variable_name()
    P = PolynomialRing(k, [v]+[v+repr(i) for i in range(D)])
    a = P.gen(0)
    M = MatrixSpace(k, D)(0)
    p = P.sum([a**n*P.gen(n+1) for n in range(D)])
    for ev in range(D):
        # the evaluation points - ranging from -1 to D-2
        for n in range(D):
            # get the n-th coefficient
            M[ev,n] = p.subs({a:k(ev-1)}).coefficient(P.gen(n+1))
    A = ~M
    # Now, A describes how the D-fold evalutation translates into
    # a polynomial of degree D-1. However, in K, we reduce this
    # to a polynomial of degree d-1. Hence, we do some
    # modifications, so that eventually we have a d by D matrix 
    minpoly = K.polynomial()
    P = minpoly.parent()
    I = P*minpoly
    a = P.gen()
    print d,D
    for n in range(d,D):
        L = I.reduce(a**n).list()
        for i,c in enumerate(L):
            print "current"
            print A
            print "i,c",i,c
            if c:
                A[i] += c*A[n]
    return M,A[:K.degree()]