How to vectorize sum of vector functions

Question

I have a for loop in MATLAB which calculates sum of sine functions as follows:

% preliminary constants, etc.
tTot = 2;
fS = 10000;dt = 1/fS; % total time, sampling rate
Npts = tTot * fS; %number of points
t = dt:dt:tTot;
c1 = 2*pi/tTot;
c2 = pi/fS;    
s = zeros(1,Npts)

% loop to optimize:
for(k=1:Npts/2)
    s = s + sin(c1*k*t - c2*k*(k-1))
end

Basically, a one-liner for loop that becomes really slow as Npts becomes large. The difficulty comes in the fact that I am summing vectors which are defined by a parameter k, over k.

Is there a way to make this more efficient by vectorizing? One approach I've taken so far is defining a matrix and summing out the result, but this gives me an out of memory error for larger vectors:

[K,T] = meshgrid(1:1:Npts,t);
s = sum(sin(c1*K.*T - c2*K.*(K-1)),2);

score 3 · Accepted Answer · edited May 23 '17 at 12:04

3

Approach #1

Using sine of difference formula: sin(A-B) = sin A cos B - cos A sin B that enables us to leverage fast matrix multiplication -

K = 1:Npts/2;
p1  = bsxfun(@times,c1*K(:),t(:).');
p2 = c2*K(:).*(K(:)-1);
s = cos(p2).'*sin(p1) - sin(p2).'*cos(p1);

Approach #2

With bsxfun -

K = 1:Npts/2;
p1  = bsxfun(@times,c1*K(:),t(:).');
p2 = c2*K(:).*(K(:)-1);
s = sum(sin(bsxfun(@minus, p1,p2)),1);

Approach #1 can be modified to bring in a smaller sized loop to accommodate for problems that have large data arrays as shown next -

num_blks = 100;%// Edit this based on how much RAM can handle workspace data
intv_len = Npts/(2*num_blks); %// Interval length based on number of blocks

KP = 1:Npts/2;
P2 = c2*KP(:).*(KP(:)-1);
sin_P2 = sin(P2);
cos_P2 = cos(P2);

s = zeros(1,Npts);
for iter = 1:intv_len:Npts/2
    K = iter:iter+intv_len-1;
    p1  = bsxfun(@times,c1*K(:),t(:).');
    s = s + (cos_P2(K).'*sin(p1) - sin_P2(K).'*cos(p1));
end

edited May 23 '17 at 12:04

Community

1
1

answered Apr 02 '15 at 19:29

Divakar

218,885
19
262
358

Nice, thanks. I still get a memory error with this method, but I'm beginning to suspect that this is a problem with vectorization of large sums. – Orko Apr 02 '15 at 19:46
@Orko Yeah, I think its because your system memory can't handle such large operations in one go. – Divakar Apr 02 '15 at 19:52
1

@Orko Addee a modified version to account for problems with large data arrays, check it out! – Divakar Apr 02 '15 at 21:27
Nice hybrid approach, and clever idea with the trig identity! – Orko Apr 02 '15 at 21:40

How to vectorize sum of vector functions

1 Answers1