Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
alternative to conv command

Subject: alternative to conv command

From: Balachander Narasimhan

Date: 29 Apr, 2011 18:16:05

Message: 1 of 8

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

Subject: alternative to conv command

From: Matt J

Date: 29 Apr, 2011 18:24:05

Message: 2 of 8

"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.

Subject: alternative to conv command

From: ImageAnalyst

Date: 29 Apr, 2011 18:30:05

Message: 3 of 8

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

Subject: alternative to conv command

From: Balachander Narasimhan

Date: 29 Apr, 2011 19:08:04

Message: 4 of 8

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.

Subject: alternative to conv command

From: ImageAnalyst

Date: 29 Apr, 2011 19:40:55

Message: 5 of 8

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.

Subject: alternative to conv command

From: Balachander Narasimhan

Date: 29 Apr, 2011 21:27:04

Message: 6 of 8

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.

Subject: alternative to conv command

From: ImageAnalyst

Date: 29 Apr, 2011 23:54:27

Message: 7 of 8

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?

Subject: alternative to conv command

From: Balachander Narasimhan

Date: 30 Apr, 2011 02:18:04

Message: 8 of 8

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?

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us