Question

Write an algorithm for multiplication of two sparse matrices

Answer 1

Hello Mate,

First off, you can do away with the forloops by utilising ismember as follows:

[lia,locb] = ismember([a.column],[b.row]); loca = find(lia);

This will give you loca and locb, which are row and column indices of the answer matrix respectively. You can determine the destination entries in the final array as follows:

[dest,~,i] = unique([loca',locb'],'rows'); dest_row = num2cell(dest(:,1)); dest_col = num2cell(dest(:,2));

Here we're using the row-based unique sort to get make sure we don't duplicate entries in the final matrix. The i index array is a map from the initial data (which may have duplicates) to the final data (sans duplicates). You can then sum the data based on these indices using accumarray:

dest_data = num2cell(accumarray(i,[a(loca).data].*[b(locb).data]));

We convert each of these to cell arrays to make forming the final matrix easier, as you'll see shortly. Assuming you haven't already, you should preallocate the final matrix:

len = size(dest,1); % number of unique entries in the final matrix c = repmat(struct('row',[],'column',[],'data',[]),len,1);

We can now set the values in the final matrix:

[c.row] = dest_row{:}; [c.column] = dest_col{:}; [c.data] = dest_data{:};

Hope this helps you