[R] Fast linear convolution with R

Philip Wette wette at mail.upb.de
Thu Feb 27 11:31:47 CET 2014


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



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

More information about the R-help mailing list