| Re: computation time for convolution [message #88981 is a reply to message #88966] |
Thu, 10 July 2014 01:47   |
Lajos Foldy
Messages: 176
Registered: December 2011
|
Senior Member |
|
|
On Wednesday, July 9, 2014 10:12:30 AM UTC+2, fraro...@yahoo.it wrote:
> I am a little puzzled about the computation time required by different convolution routines. I need to compute several times the convolution of large arrays and I always used the convolve routine of the astrolib. Since I need to speed up the processing I compared the computation time for array of different size (but using sizes power of 2, which should be the best case for FFT) convolved with different routines. The best result (by far) is obtained with the function convol of the IDL standard library, the worst is convol_fft and convolve is somewhat in the middle. This does not make sense to me, I was sure that the FFT approach is the fastest. What am I missing or doing wrong?
>
>
>
> These are the results:
>
>
>
> 4x 4
>
> convolve: 0.038000107
>
> convol: 0.00000000
>
> convol_fft: 0.00099992752
>
> 8x 8
>
> convolve: 0.00000000
>
> convol: 0.00000000
>
> convol_fft: 0.00000000
>
> 16x 16
>
> convolve: 0.00000000
>
> convol: 0.00000000
>
> convol_fft: 0.00000000
>
> 32x 32
>
> convolve: 0.00000000
>
> convol: 0.00000000
>
> convol_fft: 0.0010001659
>
> 64x 64
>
> convolve: 0.00000000
>
> convol: 0.00000000
>
> convol_fft: 0.0019998550
>
> 128x 128
>
> convolve: 0.00099992752
>
> convol: 0.0010001659
>
> convol_fft: 0.0079998970
>
> 256x 256
>
> convolve: 0.0080001354
>
> convol: 0.0019998550
>
> convol_fft: 0.035000086
>
> 512x 512
>
> convolve: 0.036000013
>
> convol: 0.0069999695
>
> convol_fft: 0.28600001
>
> 1024x 1024
>
> convolve: 0.25300002
>
> convol: 0.026999950
>
> convol_fft: 1.4849999
>
> 2048x 2048
>
> convolve: 1.6410000
>
> convol: 0.11600018
>
> convol_fft: 6.6910000
>
> 4096x 4096
>
> convolve: 7.4190001
>
> convol: 0.43299985
>
> convol_fft: 26.736000
>
>
>
> and this is the code I used for this test:
>
>
>
> for i=2,12 do begin
>
> a=fltarr(2l^i,2l^i)
>
> b=a
>
> time0=systime(1)
>
> c=convolve(a,b)
>
> time1=systime(1)
>
> c=convol(a,b)
>
> time2=systime(1)
>
> c=convol_fft(a,b)
>
> time3=systime(1)
>
> print,2l^i,'x',2l^i
>
> print,'convolve:', time1-time0
>
> print,'convol:', time2-time1
>
> print,'convol_fft:', time3-time2
>
> endfor
You are not testing convol, you are testing a very special case (convol(a,a) calculates the sum in a single position, all other array elements are set to zero).
You should use a more realistic kernel, eg b=dist(2l^(i-1)). With this I got:
1024x 1024
convolve: 2.4647841
convol: 35.345544
convol_fft: 2.8855970
regards,
Lajos
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
