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?
Here's an O(n^2)-time algorithm.
To compute one of the diagonals of the product matrix, we need to compute dot products over length-n windows of length-(2n-1) lists that are sliding in lockstep. The difference between two successive entries can be computed in time O(1).
For example, consider the product of
e f g h i o p q r s
d e f g h m o p q r
c d e f g l m o p q
b c d e f k l m o p
a b c d e j k l m o
The 1,1 entry is eo + fm + gl + hk + ij. The 2,2 entry is dp + eo + fm + gl + hk, or the 1,1 entry minus ij plus dp. The 3,3 entry is cq + dp + eo + fm + gl, or the 2,2 entry minus hk plus cq. The 4,4 entry is br + cq + dp + eo + fm, etc.
If you implement this in floating point, be mindful of catastrophic cancellation.