Ticket #12177: toom_matrix.py

File toom_matrix.py, 1.2 KB (added by SimonKing, 9 years ago)

Another proof of concept

Line 
1from sage.all import PolynomialRing, MatrixSpace, cached_function
2
3@cached_function
4def toom_matrix(K):
5    d = K.degree()
6    D = 2*d-1
7    k = K.prime_subfield()
8    if k.order()<D:
9        raise ValueError, "The prime field is too small"
10    v = K.variable_name()
11    P = PolynomialRing(k, [v]+[v+repr(i) for i in range(D)])
12    a = P.gen(0)
13    M = MatrixSpace(k, D)(0)
14    p = P.sum([a**n*P.gen(n+1) for n in range(D)])
15    for ev in range(D):
16        # the evaluation points - ranging from -1 to D-2
17        for n in range(D):
18            # get the n-th coefficient
19            M[ev,n] = p.subs({a:k(ev-1)}).coefficient(P.gen(n+1))
20    A = ~M
21    # Now, A describes how the D-fold evalutation translates into
22    # a polynomial of degree D-1. However, in K, we reduce this
23    # to a polynomial of degree d-1. Hence, we do some
24    # modifications, so that eventually we have a d by D matrix
25    minpoly = K.polynomial()
26    P = minpoly.parent()
27    I = P*minpoly
28    a = P.gen()
29    print d,D
30    for n in range(d,D):
31        L = I.reduce(a**n).list()
32        for i,c in enumerate(L):
33            print "current"
34            print A
35            print "i,c",i,c
36            if c:
37                A[i] += c*A[n]
38    return M,A[:K.degree()]
39