MATLAB: How to preallocate a matrix for this loop to make the code more efficient

indexingMATLABmatrixmatrix manipulationoptimizationpreallocation

I have this function code here:
function F = fun(M)
   F = [];
for j = 1:size(M,2)
   F = vertcat(F,[M(j:size(M,1),j) (j:(size(M,1))).' ones(size(M,1) - j + 1,1)*j]);
end
end
What I want it to do is take in a square matrix input M, then produce a new matrix F such that:
  1. The first column of F is an ordered list of the terms in the lower-left half of M (see example below).
  2. The second column of F indicates the row, in M, that the corresponding terms in the first column of F originate from.
  3. The third column of F indictes the column, in M, that the corresponding terms in the first column of F originate from.
For example, given the input:
M = 
     1     2     3     4     5
     6     7     8     9    10
    11    12    13    14    15
    16    17    18    19    20
    21    22    23    24    25
I want the function to output:
ans =
     1     1     1
     6     2     1
    11     3     1
    16     4     1
    21     5     1
     7     2     2
    12     3     2
    17     4     2
    22     5     2
    13     3     3
    18     4     3
    23     5     3
    19     4     4
    24     5     4
    25     5     5
The code I have works, it does what I want it to do, but it's terribly inefficent and somewhat slow for large matrices. The main reason for this inefficency is because it has to generate a new larger matrix for each iteration of the loop, because there is no value of F prealocated. However, since the loop involves matrix concatenation, I don't think I have any way to prealocate a matrix before the loop. Can anyone think of a way to rewrite the code to eliminate this preallocation issue? Additionally, any other advice on how to make this code more efficient would be helpful.

Best Answer

Try this: 
[r,c] = ind2sub(size(M), M(tril(M)>0));
Out = [M(tril(M)>0), c, r]
producing: 
Out =
     1     1     1
     6     2     1
    11     3     1
    16     4     1
    21     5     1
     7     2     2
    12     3     2
    17     4     2
    22     5     2
    13     3     3
    18     4     3
    23     5     3
    19     4     4
    24     5     4
    25     5     5
Related Question