Thread Subject:

alternative to conv command

Hi,

I have a long sequence to be convolved with a filter. The conv command is too slow for this. What is the alternative here?

thanks

"Balachander Narasimhan" <balxxxxxchand@whatever.com> wrote in message <ipev95$rkb$1@fred.mathworks.com>...
> Hi,
>
> I have a long sequence to be convolved with a filter. The conv command is too slow for this. What is the alternative here?


Do an FFT-based convolution?

Failing that, why do you think that there should be a better alternative to conv? Is there some structure in this filter/sequence that can be exploited?

If the sequence is long, it may not be CONV that is failing. You simply have a large computation to perform.

On Apr 29, 2:16 pm, "Balachander Narasimhan"
<balxxxxxch...@whatever.com> wrote:
> Hi,
>
> I have a long sequence to be convolved with a filter. The conv command is too slow for this. What is the alternative here?
>
> thanks
-------------------------------------------------------------------------------------------------
Balachander Narasimhan:
The conv() function is highly optimized (or it should be, since how to
optimize this algorithm is a very well known algorithm, so I would
really really doubt it if it weren't). If your data is very long
(tens of millions of elements) and conv takes considerable time, then
you can try it in the Fourier domain using the well known Fourier
filtering method. See this page:
http://en.wikipedia.org/wiki/Convolution_theorem

I'm not sure where the break even point is in terms of time vs. number
of elements, so just try it and see which way is faster.
ImageAnalyst

Hi,

thanks for the reply. I am quite sure it is conv command. I step through the code and it takes 1min and 14s for a sequence of length 2048e3 in a 1.2 GHz cpu. Do you think this is resonable?

"Matt J" wrote in message <ipevo5$7p1$1@fred.mathworks.com>...
> "Balachander Narasimhan" <balxxxxxchand@whatever.com> wrote in message <ipev95$rkb$1@fred.mathworks.com>...
> > Hi,
> >
> > I have a long sequence to be convolved with a filter. The conv command is too slow for this. What is the alternative here?
>
>
> Do an FFT-based convolution?
>
> Failing that, why do you think that there should be a better alternative to conv? Is there some structure in this filter/sequence that can be exploited?
>
> If the sequence is long, it may not be CONV that is failing. You simply have a large computation to perform.

On Apr 29, 3:08 pm, "Balachander Narasimhan"
<balxxxxxch...@whatever.com> wrote:
> Hi,
>
> thanks for the reply. I am quite sure it is conv command. I step through the code and it takes 1min and 14s for a sequence of length 2048e3 in a 1.2 GHz cpu. Do you think this is resonable?
-------------------------------------------------------------------
Here's what I get when running it several times on this not-
particularly-large array:
data = rand(1,2048000);
tic
smoothedData = conv(data, ones(3,1)/3);
toc


Elapsed time is 0.044840 seconds.
Elapsed time is 0.054861 seconds.
Elapsed time is 0.048844 seconds.
Elapsed time is 0.046158 seconds.
or about 2000 times faster than what you're getting. What exactly are
you doing such it it's so slow?
Elapsed time is 0.063725 seconds.
Elapsed time is 0.048575 seconds.
Elapsed time is 0.042594 seconds.

Hi,

thanks for your reply. your filter length is 3 whereas mine is 2048. I think thats the problem.

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <8261b8bb-1abe-415f-ba09-0acc595aaa00@z13g2000yqg.googlegroups.com>...
> On Apr 29, 3:08 pm, "Balachander Narasimhan"
> <balxxxxxch...@whatever.com> wrote:
> > Hi,
> >
> > thanks for the reply. I am quite sure it is conv command. I step through the code and it takes 1min and 14s for a sequence of length 2048e3 in a 1.2 GHz cpu. Do you think this is resonable?
> -------------------------------------------------------------------
> Here's what I get when running it several times on this not-
> particularly-large array:
> data = rand(1,2048000);
> tic
> smoothedData = conv(data, ones(3,1)/3);
> toc
>
>
> Elapsed time is 0.044840 seconds.
> Elapsed time is 0.054861 seconds.
> Elapsed time is 0.048844 seconds.
> Elapsed time is 0.046158 seconds.
> or about 2000 times faster than what you're getting. What exactly are
> you doing such it it's so slow?
> Elapsed time is 0.063725 seconds.
> Elapsed time is 0.048575 seconds.
> Elapsed time is 0.042594 seconds.

So you're filtering a signal that's "2048e3" (that's 2048000) long
with a kernel that's 2048 long? That's a big kernel. But it's still
fast. Look:

clc;
data = rand(1,2048000);
tic
smoothedData = conv(data, ones(2049,1)/3);
toc

Elapsed time is 1.541351 seconds.

I made the kernel an odd number of elements (as is normally done) just
to make sure it's symmetric.


So did you try the Fourier method like I suggested?

Hi,

thanks for your interest in my problem. You should try the complex case. In my computer, the real case took 8 secs and the complex case of the same size took 79 seconds. But when I use the fft method, the complex case took only about 4 seconds. this is huge savings!!

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <0b2c972e-1705-47f7-a138-2a26dcca2a91@n10g2000yqf.googlegroups.com>...
> So you're filtering a signal that's "2048e3" (that's 2048000) long
> with a kernel that's 2048 long? That's a big kernel. But it's still
> fast. Look:
>
> clc;
> data = rand(1,2048000);
> tic
> smoothedData = conv(data, ones(2049,1)/3);
> toc
>
> Elapsed time is 1.541351 seconds.
>
> I made the kernel an odd number of elements (as is normally done) just
> to make sure it's symmetric.
>
>
> So did you try the Fourier method like I suggested?