用稀疏矩陣乘二次形式矩陣的算法

我正在優化很大程度上依賴於自定義矩陣庫的代碼（它不會從項目中排除，因爲它無處不在，這並不好，但這是事實。 ..）許多計算10〜20行和列的矩陣做，很多的計算包括二次形式像用稀疏矩陣乘二次形式矩陣的算法

C = A*B*A'

我意識到，往往是稀疏的，我想利用這個事實。所以我正在尋找一種能夠處理這種情況的算法。數值穩定性很重要。有什麼我可以使用的嗎？由於「我們的」簡單的O（n^3）乘法方法比特徵3執行速度快，所以我不知道是否有任何我應該考慮的缺陷？

目標平臺，因爲我需要數值穩定性和矩陣不是很大，我猜Strassen的算法以及Coppersmith-Winograd算法不是我所期待的。相反，它只是一種方式的二次型乘法，可以讓我輕鬆地檢查A中的零。

感謝您的任何建議！

來源

2011-12-15 Philipp

我只是想知道是誰投了這個「關」嗎？我覺得這個問題完全有效並且與編程有關。 – nacho4d 2011-12-15 09:27:37

我不確定你會從小型矩陣中利用稀疏性獲得很多好處。 – 2011-12-15 10:57:22

存在this論文，處理快速稀疏矩陣乘法。所開發的算法將稀疏矩陣分爲兩部分：密集和稀疏，並在其上應用快速乘法算法。所以對我來說，它看起來並不取決於矩陣的大小，就像你提到斯特拉森一樣，但是它是稀疏的。

來源

2011-12-15 09:00:42

有許多方法可以用比稠密矩陣更稠密的方式實現稀疏矩陣。我做到這一點是如下的一種方法：

[0 0 0 0 0] 
[0 1 2 0 9] 
[0 0 0 2 0] 
[0 1 0 0 0]

變爲非零元素

typedef struct { 
    int row; 
    int col; 
    double entry; 
} Element; 

typedef SparseMatrix Element*;

所以矩陣現在有O（n）的空間複雜度的代替鄰的線性陣列（對於A * B，其中A和B是矩陣，您只需遍歷每個數組以匹配元素（即a-> row == b-> col & & a-> col == b->行），並可能添加幾個（內部產品）。這個算法的複雜度是O（n^2），而不是O（n^3）。這是因爲您可以跳過採用可能導致零的內部產品的輕微操作。

來源

2012-01-09 22:02:40 Ataraxia

檢出Highly Parallel Sparse Matrix-Matrix Multiplication algorothm

來源

2012-03-01 06:28:18

用稀疏矩陣乘二次形式矩陣的算法

回答

相關問題