[Numpy-discussion] fast matrix vector operations

[Gideon Simpson]

Suppose I have a toeplitz matrix, A.  There is a well known algorithm  
for computing the matrix vector product Ax, in NlogN operations.  An  
exact reference escapes me, but it may be in Golub & van Loan's book.

My question is, how could I best take advantage of this algorithm  
within numpy/scipy?

I could code it python.  However, since python is a high level  
language, it's not clear to me that I'd see an execution time benefit  
over numpy.dot(A,x).  Alternatively, I could write it in a compiled  
language and build python bindings to it.

Thoughts?

-gideon