用於乘兩個稀疏矩陣的算法

Question

我在Matlab中工作，我將稀疏矩陣存儲爲具有字段的結構數組：行，列和數據。所以對於兩個矩陣，我將有一個數組集合（行，列，數據）爲每個非零條目。

我想寫一個高效的程序來乘以這種形式的兩個稀疏矩陣，但我有一些困難。

但是，這有問題的數組中有重複的條目，當我真的想要添加它們。

任何幫助，非常感謝。

Answer 1

首先，你可以利用ismember如下廢除了forloops：

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

這會給你loca和locb，分別答案矩陣的行和列索引。你能確定最終的數組中的目的地條目如下：

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

在這裏我們使用基於行唯一的排序得到確保我們不會在最後的矩陣重複的條目。 i索引數組是從初始數據（可能有重複數據）到最終數據（無重複數據）的映射。然後，您可以總結基於使用accumarray這些指標的數據：

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

我們每個人的這些轉換爲太陽能電池陣列，使形成最終的矩陣更容易，因爲你很快就會看到。假如你還沒有，你應該預先分配的最終矩陣：

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

現在，我們可以在最後的矩陣設置的值：

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