Convolve/Filter Implimentation

[Old posts from the commercial version of ArrayFire] Discussion of ArrayFire using CUDA or OpenCL.

Moderator: pavanky

Convolve/Filter Implimentation

Postby neuralPanther » Mon Sep 08, 2014 12:48 pm

Hi All,

Do either the convolve or the filter function use an FFT-based implementation?

For the system I'm building I need a convolution function that is NOT FFT-based.

I did not find it explicitly spelled out in the documentation or in the forums.

Thank you!
neuralPanther
 
Posts: 25
Joined: Fri Feb 14, 2014 8:03 pm

Re: Convolve/Filter Implimentation

Postby pavanky » Mon Sep 08, 2014 1:19 pm

Hi,

convolve uses FFT after a certain size. Can you tell me what sizes and the types of operations you are looking at ?

If you are using convolve to perform difference operations, we have other specialized functions listed below that may be helpful:

grad: http://www.arrayfire.com/docs/group__ma ... __grad.htm
diff: http://www.arrayfire.com/docs/group__im ... __diff.htm
Pavan Yalamanchili,
ArrayFire
--
~ If it is not broken, you have not tried hard enough ~
User avatar
pavanky
Site Admin
 
Posts: 1123
Joined: Mon Mar 15, 2010 7:39 pm
Location: Atlanta, GA

Re: Convolve/Filter Implimentation

Postby neuralPanther » Mon Sep 08, 2014 1:38 pm

Hi,

We're doing 1 dimensional Convolutions - greater than 8 million points.
Edit: This is not for difference operations - it's for filtering operations ...

At what vector size does it become FFT Based?

Given that it's 1 dimensional I think this implies that I need to either use a gfor or possibly write a kernel - thoughts?

Thank you,

~ NP
neuralPanther
 
Posts: 25
Joined: Fri Feb 14, 2014 8:03 pm

Re: Convolve/Filter Implimentation

Postby pavanky » Mon Sep 08, 2014 1:41 pm

Hi,

The signal size does not matter. I was asking what the size of the kernel is.

Are you saying you are convolving two signals of size 8 million elements each ?
Pavan Yalamanchili,
ArrayFire
--
~ If it is not broken, you have not tried hard enough ~
User avatar
pavanky
Site Admin
 
Posts: 1123
Joined: Mon Mar 15, 2010 7:39 pm
Location: Atlanta, GA

Re: Convolve/Filter Implimentation

Postby neuralPanther » Mon Sep 08, 2014 1:59 pm

Hi,

Sorry - the filter is small in comparison to the signal - less than 100 elements.
The signal being filtered is 8 million elements.

~ NP
neuralPanther
 
Posts: 25
Joined: Fri Feb 14, 2014 8:03 pm

Re: Convolve/Filter Implimentation

Postby pavanky » Mon Sep 08, 2014 2:04 pm

Currently the switch from regular kernel to an FFT based one happens at a filter size of 32 elements (for float) and 16 elements (for double).

Any reason FFT is discouraged for your algorithm ?
Pavan Yalamanchili,
ArrayFire
--
~ If it is not broken, you have not tried hard enough ~
User avatar
pavanky
Site Admin
 
Posts: 1123
Joined: Mon Mar 15, 2010 7:39 pm
Location: Atlanta, GA

Re: Convolve/Filter Implimentation

Postby neuralPanther » Mon Sep 08, 2014 3:07 pm

We have to do more work to the data after an FFT-based convolution to adjust for transients and alignment.

It sounds like I'll need to either work around it or do the extra work :)

Thanks,

~NP
neuralPanther
 
Posts: 25
Joined: Fri Feb 14, 2014 8:03 pm

Re: Convolve/Filter Implimentation

Postby pavanky » Mon Sep 08, 2014 4:45 pm

Hi,

The behavior of our FFT based convolutions and regular convolutions is the same. We take care of alignment issues internally. So you need not worry about them.

I am a bit unfamilar with transients so if you can elaborate a bit more, perhaps we can provide you with a workaround.
Pavan Yalamanchili,
ArrayFire
--
~ If it is not broken, you have not tried hard enough ~
User avatar
pavanky
Site Admin
 
Posts: 1123
Joined: Mon Mar 15, 2010 7:39 pm
Location: Atlanta, GA

Re: Convolve/Filter Implimentation

Postby neuralPanther » Mon Sep 29, 2014 8:17 pm

Hi There,

Sorry it's taken me some time to work through this a bit more thoroughly.

In general if a fast convolution (i.e. FFT based) is used the result is a circular convolution, which can affect the result. Take the following small (MATLAB) example:

Code: Select all
     a = [1:6]
     b = [1, 2, 1]
     ifft(fft(a,6).*fft(b,6)) % zero extend to the length of the input signal (6)
% Result:
    % 18    10     8    12    16    20
% Now zeros extend to length(a) + length(b) - 1 (or 8)
     ifft(fft(a,8).*fft(b,8))
% Result
    %1.0000    4.0000    8.0000   12.0000   16.0000   20.0000   17.0000    6.0000  % Note the difference in the first 2 points - this is because there's no wrapping from the effects of the circular FFT
% now a non-FFT-based convolve
conv(a,b)
% Result
     % 1     4     8    12    16    20    17     6 %note that it's the same as the N+h-1 zero padding


After the convolve resulting in a vector of length: N+M-1 - I would normally adjust for the FIR filter transients by removing the extra samples on either side of the sequence.
However with the arrayfire convolve and FIR functions it's not clear:

1. What is the zero extension? (is it just to N, or to N+M-1)
2. Because it results in a sequence of length N, are samples thrown away, or are we only zero extending to N samples?
3. What are the differences between the FIR function and the Convolve function?
4. What alignment is being performed?
neuralPanther
 
Posts: 25
Joined: Fri Feb 14, 2014 8:03 pm

Re: Convolve/Filter Implimentation

Postby neuralPanther » Thu Oct 09, 2014 2:14 pm

Ok -

I figured this one out -

There are no issues with the convolve/fir functions as long as the extend option is used. Otherwise the resulting array contains the transients (the first h outputs, where h is the kernel length) instead of the steady state response which begins after the first h outputs.

At least for 1 dimensional convolutions, the non-extended version should probably provide the middle set of outputs instead of the initial set. This through me off for a while, but once I figured out what was going on I used the extended version of the functions and then truncated it myself.

Thanks,

~ NP
neuralPanther
 
Posts: 25
Joined: Fri Feb 14, 2014 8:03 pm


Return to [archive-commercial] Programming & Development with ArrayFire

cron