user2913990
user2913990

Reputation: 107

matlab: Sparse Function for any matrix

I am trying to write a sparse function code for any matrix size. For example if i have a matrix:

A = [ 0   0   0   5
      0   2   0   0
      1   3   0   0
      0   0   4   0];
  a=size(A);
  b=size(A);
  c=0;
  position=0;
  for i=1:a for j=1:b if A(i,j) ~=0
              c=c+1;
              position=position+1;
              S(c,:)=[position,i,j,A(i,j)];
          end
      end
  end
S

S --> is the storage matrix for all the non zero elements for A matrix. In addition to this information(Index,Row Number, Column Number, Value) how do I include two more columns in the matrix which shows the next element in row & the next element in column.

Upvotes: 0

Views: 961

Answers (2)

user2913990
user2913990

Reputation: 107

A = [ -1   0  -2   0   0
       2   8   0   1   0
       0   0   3   0  -2
       0  -3   2   0   0
       1   2   0   0  -4];

  a=size(A);
  b=size(A);
  c=0;
  position=0;
  for i=1:a 
      for j=1:b 
          if A(i,j) ~=0
              c=c+1;
              position=position+1;
              S(c,:)=[position,i,j,A(i,j)];
          end
      end
  end

  index=size(S,1);
  NIR = [];
for i = 1:index
    for j = 1:index
        if i ~= j
            if S(i,2) == S(j,2)if S(i,3) < S(j,3)if length(NIR) < i
                        NIR(i,1) = S(j,1);
                    end
                end
            end
        end
    end
    if length(NIR) < i
        NIR(i,1) = 0;
    end
end

%finding NIC
NIC = [];
for i = 1:index
    for j = 1:index
        if i ~= j
            if S(i,3) == S(j,3)if S(i,2) < S(j,2)if length(NIC) < i
                        NIC(i,1) = S(j,1);
                    end
                end
            end
        end
    end
    if length(NIC) < i
        NIC(i,1) = 0;
    end
end

Sprs=[S,NIR,NIC]

n=nnz(A);
r=size(A);
m=r(1,1);
position=zeros(n,1);
t=1;
FIR= zeros(m,1);
FIC= zeros(m,1);
for i= 1: n
    position(i,1)= i;
end

for i= 1: m
    for j= 1: m
        if (A(i,j)~= 0)
            value(var,1)= A(i,j);
            row(var,1)= i;
            col(var,1)= j;
            var= var+ 1;
        end
    end
end
for j= 1: m
    for i= t: n
        if row(i,1)== j
            FIR(j,1)= position(i,1);
            t= i+1;
            break;
        end
    end
end
for k= 1: m
for l= 1: n
    if (col(l,1)== k)
        FIC(k,1)= position(l,1);
        break;
    end
end
end

S1=[FIR, FIC]

Upvotes: 0

Rody Oldenhuis
Rody Oldenhuis

Reputation: 38052

Here's the fruits of some academic masturbation :)

1) It uses an array-growth scheme that is a lot more efficient than growing the array at each iteration 2) It optimizes memory footprint/usage by using the minimum necessary data class for the indices

K      = 1.1;
inds   = zeros(10,2, 'uint8');
values = zeros(10,1, class(A));

count = 1;
for ii = 1:numel(A)    
    if A(ii)

        %// grow arrays and/or change type when necessary
        if count > size(inds,1)

            %// Re-cast datatype of inds
            if count > intmax(class(inds))
                switch class(inds)
                    case 'uint8'
                        inds = uint8(inds);
                    case 'uint16'
                        inds = uint32(inds);
                    case 'uint32'
                        inds = uint64(inds);
                    case 'uint64'
                        error('There are too many non-zero elements.');
                    otherwise
                        error('...huh?!');
                end
            end

            %// now grow the arrays
            inds   = [inds;   zeros(ceil((K-1)*count), 2, class(inds))  ]; %#ok<AGROW>
            values = [values; zeros(ceil((K-1)*count), 1, class(values))]; %#ok<AGROW>

        end

        %// assign the indices and values
        inds(count,:) = [mod(ii-1,size(A,1))+1; ceil(ii/size(A,1))];
        values(count) = A(ii);
        count = count + 1;

    end
end

%// chop-off any remaining zeros
inds   = inds  (1:count-1,:);
values = values(1:count-1,:);

Aside from some relatively minor optimizations you could still do, this is about as efficient as you can make it in MATLAB.

Testing this implementation vs. the built-in sparse for A = rand(500); A(A<0.5) = 0; gives:

Elapsed time is 1.802105 seconds.  %// implementation above
Elapsed time is 0.006877 seconds.  %// sparse

So about 250 times slower. All of this just proves one thing:

DON'T DO THIS SORT OF THING IN MATLAB!

Upvotes: 2

Related Questions