# Fast(er) computation of dot product of two convolutions?

Let $a,b,c,d\in\mathbb{R}^n$. Is it possible to compute $$\langle a*b,c*d\rangle$$ faster than 6 FFTs?

I can do it with 6 FFTs by doing normal convolutions, 3 FFTs each.

In my application I know $b, d$ upfront and can do preprocessing, so the cost is actually 4 FFTs. Can I do better than this?

The reason I believe that this might be possible is because FFTs are unitary, so maybe there's a way to omit the inverse FFTs in the convolutions.

[EDIT] where convolution is defined by: $$(a*b)_i=\sum_{j=1}^i a_jb_{n+j-i}$$

• You can get the acylic convolution by means of zero padding before doing an FFT based circular convolution. Aug 30 '16 at 23:25
• @Brian: Right, that's how I solve the problem with 6(/4) FFTs. I don't see how to stay in the frequency domain if I zero padded the vectors. Aug 31 '16 at 5:44
• I think the indexing in the sum above is wrong. The sum must run to some maximum size, not to the index $i$ that also appears on the right. Sep 5 '16 at 21:11
• @Wolfgang Bangerth: the indexing is the right one. Think of the convolution with $b$ as a filter on a stream: at time $i$ we only know the first $i$ coordinates of $a$, so $b$ multiplies only with them. For example taking $b$ to be the vector $(0,...,0,B)$, convolution (in the above sense) multiplies vectors by B. Sep 6 '16 at 5:47
• But it doesn't match the definition on the wikipedia page you linked to from my answer in a comment. There, the sum always has the same number of terms, independent of the index $i$ of the result vector. Sep 6 '16 at 21:41

Parseval's theorem tells you that the dot product between two vectors equals the dot product of the Fourier transforms, possibly up to a constant. Consequently, you do not need to transform back the result of $a\ast b$ and $c \ast d$ and should be able to do the overall operation with just 4 FFTs.
• I don't know about the acyclic convolution. It's the first time I hear about it. As for having to transform it back -- the result of the product $\left<a \ast b, c \ast d\right>$ is a scalar number. There is nothing to transform. Aug 31 '16 at 0:14