ToeplitzMatrix.py

from numpy.fft import fft,ifft

def multiplyVectors(v0,v1):
 n=len(v0)
 return [v0[i]*v1[i] for i in range(n)]

def pointMultiply(v0,v1):
 return sum(multiplyVectors(v0,v1))

def multiply(m,v):
 n=len(v)
 if n!=len(m) or n!=len(m[0]): return None
 return [pointMultiply(row,v) for row in m]

def convolve(tr,v):
 ttr=fft(tr)
 zeroPadding=[0 for i in range(len(tr)-len(v))]
 tv=fft(vector+zeroPadding)
 return ifft(multiplyVectors(ttr,tv))

toeplitz=[[1,0,3],[2,1,0],[-1,2,1]]
t=[3,0,1,2,-1]
vector=[10,20,30]

m=multiply(toeplitz,vector)
print('Matrix multiplication in O(n^2): ',m)

c=convolve(t,vector)
print('Convolution in O(n*log(n)): ',c)