performance - Product of two Toeplitz matrices? -

the o(n log n) algorithm product of toeplitz matrix , vector of correct length well-known: put in circulant matrix, multiply vector (and subsequent zeroes), , return top n elements of product.

i'm finding trouble finding best (time-wise) algorithm multiplying 2 toeplitz matrices of same size.

can give me algorithm this?

here's o(n^2)-time algorithm.

to compute 1 of diagonals of product matrix, need compute dot products on length-n windows of length-(2n-1) lists sliding in lockstep. difference between 2 successive entries can computed in time o(1).

for example, consider product of

e f g h    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 b c d e    j k l m o 

the 1,1 entry eo + fm + gl + hk + ij. 2,2 entry dp + eo + fm + gl + hk, or 1,1 entry minus ij plus dp. 3,3 entry cq + dp + eo + fm + gl, or 2,2 entry minus hk plus cq. 4,4 entry br + cq + dp + eo + fm, etc.

if implement in floating point, mindful of catastrophic cancellation.