6

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?

4
  • The product of Toeplitz matrices is not necessarily Toeplitz. How is the output to be represented? Apr 8, 2013 at 23:27
  • As an nxn matrix, seeing as there's no other representation that would display all the relevant data in this case. I'm not asking for an algorithm that runs faster than O(n^2), I am merely wondering if there is a faster algorithm than the standard matrix multiplication routine in this case. Apr 9, 2013 at 2:13
  • Note that the product of two circulant matrices is circulant. I wonder if there's a algorithm faster than O(n^2) to calculate the product of two circulant matrices, both expressed as vectors.
    – nneonneo
    Apr 9, 2013 at 2:55
  • @nneonneo There's an O(n log n)-time algorithm -- multiply the first matrix by one row of the second and take n different rotations. Apr 9, 2013 at 12:25

1 Answer 1

8

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.

4
  • Can you please expand on this? I don't understand what you mean by sliding in lock step, but I do see the pattern you're trying to show.
    – Jonathan
    Oct 13, 2018 at 9:31
  • 1
    @Jonathan I guess another way to say it is that we can multiply the lists pointwise and then the elements of the diagonal are sums of n consecutive elements of the products list. Oct 13, 2018 at 13:25
  • Is there a way to mathematically represent that?
    – Jonathan
    Oct 16, 2018 at 3:08
  • @Jonathan Convolution with an all-ones vector? Oct 18, 2018 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.