Revolving Doors Riddle - Matlab Effective Use of Sparse Matrix

I am running code with many iterations using large sparse matrices. There are three lines in my code that take about 75% of the running time, and I think I can use my sparse matrix's custom structure to shorten this time, but I have not succeeded so far. I will be glad for your help!

Ok, here's the gist of my code:

I = 70;
J = 1000;
A = rand(I);
A = A./repmat(sum(A, 2), 1, I);
S   = kron(A, speye(J));
indj = randi(J,I,1); 
tic
for i = 1:I
    S(:, (i-1)*J+indj(i)) = sum(S(:, (i-1)*J + (1:indj(i))), 2);
end
toc

      

        
        
        
      

    

You can skip next 2 paragraphs

Here's a story to make the example a little more animated. The old man visits sick people in different hospitals. There are 1000 (J) hospitals and each hospital has 70 (I) rooms. Matrix A is a transition matrix that indicates the probability that an old man will move from one room to a hospital to another room in the same hospital. A (i1, i2) is the probability that the old man will move from room i1 to room i2 (so the columns add up to 1). The large S-matrix is ​​a transition probability matrix where the movement from room i1 in hospital j1 to room i2 in hospital j2 is given by the element (J * (i1-1) + j1, J * (i2-1) + j2), Old man does not move from one hospital to another, so the matrix is ​​sparse.

Something magical happens and now all the doors to the room number i in the first indj (i) hospitals lead to the same hospital, the indj (i) hospital. Thus, the old man can now magically move between hospitals. We need to change the S-matrix accordingly. This amounts to two things, increasing the probability of going to room i in hospital indj (i) for all i and setting the probability of going to all rooms lower than indj (i) in hospital i for all i. The latter I can do very efficiently, but the first part took me too long.

Why I think there is a chance to shorten the working time

• Loop . The part between tic and toc can be written without a loop. I did it, but it started it up much slower, perhaps because the length of sub2ind is so long.

• Matrix structure . Please note that we do not need the full amount, we only need to add one item. These loops achieve the same result (but are obviously much slower here):

  for i = 1:I
  for ii = 1:I
  for j = 1:indj(i)-1
      S((ii-1)*J+j, (i-1)*J+indj(i)) = S((ii-1)*J+j, (i-1)*J+indj(i)) + S((ii-1)*J+j, (i-1)*J+j);
  end
  end
  end
  
        
  
          
          
          
        
  
      

This makes me somewhat hopeful that there is a way to make the calculation faster ...

Your help is greatly appreciated!