Discrete Fourier transforms using Sagemath

Here are some Sagemath examples for DFTs, DCTs, and DST’s. You can try copying and pasting them into the Sagemath cloud, for example.

The Sagemath dft command applies to a sequence S indexed by a set J computes the un-normalized DFT: (in Python)

[sum([S[i]*chi(zeta**(i*j)) for i in J]) for j in J]Here are some examples which explain the syntax:

sage: J = range(6)
sage: A = [ZZ(1) for i in J]
sage: s = IndexedSequence(A,J)
sage: s.dft(lambda x:x^2)
   Indexed sequence: [6, 0, 0, 6, 0, 0]
   indexed by [0, 1, 2, 3, 4, 5]
sage: s.dft()
   Indexed sequence: [6, 0, 0, 0, 0, 0]
   indexed by [0, 1, 2, 3, 4, 5]
sage: G = SymmetricGroup(3)
sage: J = G.conjugacy_classes_representatives()
sage: s = IndexedSequence([1,2,3],J) # 1,2,3 are the values of a class fcn on G
sage: s.dft()   # the "scalar-valued Fourier transform" of this class fcn
    Indexed sequence: [8, 2, 2]
    indexed by [(), (1,2), (1,2,3)]
sage: J = AbelianGroup(2,[2,3],names='ab')
sage: s = IndexedSequence([1,2,3,4,5,6],J)
sage: s.dft()   # the precision of output is somewhat random and arch. dependent.
    Indexed sequence: [21.0000000000000, -2.99999999999997 - 1.73205080756885*I, -2.99999999999999 + 1.73205080756888*I, -9.00000000000000 + 0.0000000000000485744257349999*I, -0.00000000000000976996261670137 - 0.0000000000000159872115546022*I, -0.00000000000000621724893790087 - 0.0000000000000106581410364015*I]                
     indexed by Multiplicative Abelian Group isomorphic to C2 x C3
sage: J = CyclicPermutationGroup(6)
sage: s = IndexedSequence([1,2,3,4,5,6],J)
sage: s.dft()   # the precision of output is somewhat random and arch. dependent.
    Indexed sequence: [21.0000000000000, -2.99999999999997 - 1.73205080756885*I, -2.99999999999999 + 1.73205080756888*I, -9.00000000000000 + 0.0000000000000485744257349999*I, -0.00000000000000976996261670137 - 0.0000000000000159872115546022*I, -0.00000000000000621724893790087 - 0.0000000000000106581410364015*I]
     indexed by Cyclic group of order 6 as a permutation group
sage: p = 7; J = range(p); A = [kronecker_symbol(j,p) for j in J]
age: s = IndexedSequence(A,J)
sage: Fs = s.dft()
sage: c = Fs.list()[1]; [x/c for x in Fs.list()]; s.list()
     [0, 1, 1, -1, 1, -1, -1]
     [0, 1, 1, -1, 1, -1, -1]

 

The DFT of the values of the quadratic residue symbol is itself, up to a constant factor (denoted c on the last line above).

Here is a 2nd example:

sage: J = range(5)
sage: A = [ZZ(1) for i in J]
sage: s = IndexedSequence(A,J)
sage: fs = s.dft(); fs
  Indexed sequence: [5, 0, 0, 0, 0]
   indexed by [0, 1, 2, 3, 4]
sage: it = fs.idft(); it
  Indexed sequence: [1, 1, 1, 1, 1]
   indexed by [0, 1, 2, 3, 4]
age: it == s
True
sage: t = IndexedSequence(B,J)
sage: s.convolution(t)
 [1, 2, 3, 4, 5, 4, 3, 2, 1]

Here is a 3rd example:

sage: J = range(5)
sage: A = [exp(-2*pi*i*I/5) for i in J]
sage: s = IndexedSequence(A,J)
sage: s.dct()    # discrete cosine
   Indexed sequence: [2.50000000000011 + 0.00000000000000582867087928207*I, 2.50000000000011 + 0.00000000000000582867087928207*I, 2.50000000000011 + 0.00000000000000582867087928207*I, 2.50000000000011 + 0.00000000000000582867087928207*I, 2.50000000000011 + 0.00000000000000582867087928207*I]
    indexed by [0, 1, 2, 3, 4]
sage: s.dst()        # discrete sine
  Indexed sequence: [0.0000000000000171529457304586 - 2.49999999999915*I, 0.0000000000000171529457304586 - 2.49999999999915*I, 0.0000000000000171529457304586 - 2.49999999999915*I, 0.0000000000000171529457304586 - 2.49999999999915*I, 0.0000000000000171529457304586 - 2.49999999999915*I]
   indexed by [0, 1, 2, 3, 4]

Here is a 4th example:

sage: I = range(3)
sage: A = [ZZ(i^2)+1 for i in I]
sage: s = IndexedSequence(A,I)
sage: P1 = s.plot()
sage: P2 = s.plot_histogram()

P1 and P2 are displayed below:

The plots of P1

The plot of P1

The plot of P2

The plot of P2

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s