Improving performance of a complex for loop

I have a Matrix of size (300000X4). This is getting generated from a simulator that is running 200 particles for 1500 timesteps, hence producing 300000 rows of data. So, each of these 200 rows represents one timestep worth of data for one particle. The 4 columns are position and velocity components (Px, Py, Vx, Vy).

Now I am trying to create a new matrix that will be of dimension (3000000,10) where the columns will be the velocity values of the 5 nearest neighbors of a particle (at a particular timestep). The number of columns is 10 because I am going for 5 enighbours (i.e., Vx and Vy components of 5 nearest neighbors).

Currently, I can do it with for loops (pseudocode below), but I was wondering if it can be vectorized to speed up the computation. Any help or pointers (vectorizing or improving the approach) are much appreciated.

ROWS = 300000;                                      %no of data rows
PARTICLES = 200;                                    %no of particles
myData = rand(ROWS, PARTICLES);                     %matrix that holds my initial data from simulator, using dummy here
neighbors = 5;

neighborVelocity = zeros(ROWS,neighbors*2);         %Allocating space for the final matrix to be generated

for t = 1:1500 %for each timestep
    start = (t-1)*PARTICLES+1;
    finish = (start-1)+PARTICLES;
    currData = myData(start:finish,:);              %Data for current timestep
    temp = zeros(PARTICLES,neighbors*2);            %For saving the processed data for current timestep
    for m = 1:200 %for each particle
        particle = currData(m,1:2);
        allParticlePos = currData(:,1:2);
        particleVelocity = currData(m,3:4);
        allParticleVel = currData(:,3:4);
        [Idx,~] = knnsearch(allParticlePos,particle,'K',neighbors);
        
        nearest = allParticleVel(Idx,:);            %The Velocities of the nearest neighbors are stored 
        
        %Some reshaping to save the nearest velocities in a intended format
        nearest = reshape(nearest.',1,[]);
        temp(m,:) = nearest;
    end
    neighborVelocity(start:finish,:) = temp;          %Storing the particula timestep data
    
end

[Walter Roberson]

knnsearch can search all items simultaneously, and is more efficient that way.

[Rafi]

Hi Walter, can you please elaborate on "all items simultaneiously"? This might help me improve the loop. Thanks!

Answer 1

[Pravin Jagtap]

Hello Rafi,

From your code and data structure used it is clear that there are two for loops:

• Outside for loops iterates over the time which is not vectorizable because of data dependency involved
• Inside for loop iterates over 200 particles and from your explanation, the nature of computations for each of those 200 particles is the same. If it is so you can consider rewriting code in such a way that it can be vectorized or ‘parfor’ can be used from parallel computing toolbox. But you must make sure that operations(computations) involved in the inside for loop are independent.

I would recommend the following to improve the performance:

• Using MATLAB profiler find out the bottlenecks (most time-consuming segments) present in the code.
• Use the ‘Run and Time’ tool available under EDITOR section. (Check the attached PNG file) Refer https://www.mathworks.com/help/matlab/matlab_prog/profiling-for-improving-performance.html

• Focus on optimizing the bottlenecks (‘knnsearch’ is the bottleneck in your code)
• Consider the vectorization/parallel computing toolbox or GPU coder toolbox for accelerating the code considering the data dependency involved and the availability of hardware.

[Rafi]

Hi Pravin, thanks for the advice regarding checking bottlenecks. The execution time has significantly improved as I changed the knnsearch function to a custom one.