How to generate big nxn-matrices?

How do I generate a nxn matrix where each row contains k ones at random positions and all other elements are zero? k<<n so the matrix will be sparse. n will be very large so the algoritm should hopefully be effective.

[reen2015]

try this

mat_sparse=zeroes(n,n);

for i=1:n

for j=1:k

   position=randi(n,1,1);

    mat_sparse(n,position)=1;

end

end

[John D'Errico]

@raina2015:

NO NO NO NO NO! You are posing flat out terrible advice. Learn to use sparse matrices. NEVER stuff a sparse matrix one element at a time. Never stuff a sparse matrix even one row at a time!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

(Oh, by the way, the solution that you posed is also wrong, since randi can generate replicate columns in any given row. In that case, you will not have exactly k non-zeros in that row.)

[matamm]

Thanks!

Answer 1

[John D'Errico]

LEARN TO USE SPARSE MATRICES.

The basic tool to generate sparse random matrices is sprand. Beyond that, use thee sparse function in general.

Here of course, there is a more specific goal, i.e., to generate a matrix with a fixed number of random ones in each row.

The simple solution is to generate the locations of those elements in advance, then just call sparse.

n = 1e6; % size of array
k = 20; % number of elements per row

rind = repmat((1:n)',1,k);
cind = zeros(n,k);
for i = 1:n
  cind(i,:) = randperm(n,k);
end
M = sparse(rind,cind,1,n,n);

See that there are exactly k=20 non-zero elements in each row, all of which are 1.

sum(M(1,:))
ans =
   (1,1)       20

I can probably come up with another way to generate the column indices that is more efficient, but since cind is preallocated, that loop is reasonably efficient anyway.

As it turns out, with n = 1e6 and k = 20, the above solution took about 7 seconds on my CPU. So not terrible, but I can surely do better. The looped calls to randperm were simply too expensive.

tic
n = 1e6; % size of array
k = 20; % number of elements per row

rind = repmat((1:n)',1,k);
cind = randi(n,[n k]);
m = find(any(diff(sort(cind,2),[],2) <= 0,2));
for i = m'
  cind(i,:) = randperm(n,k);
end
toc
M = sparse(rind,cind,1,n,n);
toc

Elapsed time is 1.061419 seconds.
Elapsed time is 4.440370 seconds.

This version took 4.4 seconds to generate the array, of which 3.4 seconds were in the final call to sparse.