The O(n log n)
algorithm for the product of a Toeplitz matrix and a vector of the correct length is well-known: put it in a circulant matrix, multiply it by the vector (and subsequent zeroes), and return the top n
elements of the product.
I'm finding trouble finding the best (time-wise) algorithm for multiplying two Toeplitz matrices of the same size.
Can anyone give me an algorithm for this?
O(n^2)
, I am merely wondering if there is a faster algorithm than the standard matrix multiplication routine in this case.