Product of two Toeplitz matrices?

Question

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?

Answer 1

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.