[R] Fast linear convolution with R

[Philip Wette]

Hello,

i am trying to compute the linear convolution of two vectors of length 
1e7 each.
The code i am using is
a = vector(length=1e7)
b = vector(length=1e7)
#fill a and b with data...
c = convolve(a, rev(b), type="o")

Unfortunately, this computation goes on now for a very long time 
(currently 15h and counting).


Does it make sense to wait a couple of hours more or do i only waste my 
time and resources because it will take ages?
Is there maybe a better way to compute the convolution?

Or are there specific vector lengths that speed up the computation of 
the convolution? I for example found out that convolving vectors of 
length 1e5 takes 3 times longer than convolving vectors of size 4e6...

 > b = vector(length=4e6)
 > a = vector(length=4e6)
 > system.time( convolve(a, b, type="o") )
    user  system elapsed
123.796   0.196 124.132
 > a = vector(length=1e5)
 > b = vector(length=1e5)
 > system.time( convolve(a, b, type="o") )
    user  system elapsed
303.129   0.099 303.635



Best,

Philip


-- 
Philip Wette, M.Sc.             E-Mail: wette at mail.upb.de
University of Paderborn         Tel.:   05251 / 60-1716
Department of Computer Science
Computer Networks Group         http://wwwcs.upb.de/cs/ag-karl
Warburger Straße 100            Room:   O3.152
33098 Paderborn