How to speed up multiple vector convolution in MATLAB?

Question

I'm having a problem with finding a faster way to convolve multiple vectors. All the vectors have the same length M, so these vectors can be combined as a matrix (A) with the size (N, M). N is the number of vectors.

Now I am using the below code to convolve all these vectors:

B=1;

for i=1:N

B=conv(B, A(i,:));

end

I found this piece of code becomes a speed-limit step in my program since it is frequently called. My question is, is there a way to make this calculation faster? Consider M is a small number (say 2).

Answer 1

It should be quite a lot faster if you implement your convolution as multiplication in the frequency domain.

Look at the way fftfilt is implemented. You can't get optimal performance using fftfilt, because you want to only convert back to time domain after all convolutions are complete, but it nicely illustrates the method.

Answer 2

Convolution is associative. Combine the small kernels, convolve once with the data.

Test data:

M = 2; N = 5; L = 100;
A = rand(N,M);
Bsrc = rand(1,L);

Reference (convolve each kernel with data):

B = Bsrc;
for i=1:N,
    B=conv(B, A(i,:));
end

Combined kernels:

A0 = 1;
for ii=1:N,
    A0 = conv(A0,A(ii,:));
end
B0 = conv(Bsrc,A0);

Compare:

>> max(abs(B-B0))
ans =
   2.2204e-16

If you perform this convolution often, precompute A0 so you can just do one convolution (B0 = conv(Bsrc,A0);).