Q

任意矩陣乘法的複雜性

2012-03-09 120 views 2 likes

2

我有一個關於矩陣乘法實現的簡單問題。我知道有相同大小（n×n）的矩陣的算法，其複雜度爲O（n^2.xxx）。但是如果我有兩個不同大小的矩陣A和B（p x q，q x r），到目前爲止實現的最小複雜度是多少？我猜想這是O（pqr），因爲我會用p，q和r迭代實現一個3個嵌套循環的乘法運算。特別是，現在有沒有人Eigen庫實現乘法？任意矩陣乘法的複雜性

2012-03-09 alfa

+2

你看過特徵源代碼嗎？ – andand 2012-03-09 17:36:31

+1

是的，我不明白。我不是一個偉大的數學家。 :( – alfa 2012-03-09 18:22:50

A

回答

3

一種常見的技術是填充大小爲（p * q，q * r）的矩陣，以使它們的大小變爲（n * n）。然後，您可以應用Strassen的算法。

2012-03-10 12:41:14

+0

有沒有關於這方面的任何出版物，或者是否有任何使用這種技術的庫？ – alfa 2012-03-11 10:26:54

+0

嗯，Strassen的算法是關於遞歸分割成大小相等的，所以二進制搜索是一種快速二進制搜索的方式。二是做第一步決定哪個功率的兩個大小的剩餘塊搜索，然後做有效的二進制搜索精確的二分之一。我希望有一個類似的概念爲斯特拉森工作;在那裏你沒有得到一個整潔的分區，做一個醜陋的分區，在這個大的二進制塊上做Strassen，然後把strassen和fixup應用到剩下的東西上。（四叉樹非常成功地做了這樣的事情）。 – 2012-05-19 16:22:19

2

由於您陳述的原因，您對O（pqr）是正確的。

我不知道本徵如何實現它，但是有很多的方法來優化矩陣乘法算法，如tiling優化緩存性能和意識到的你正在使用的語言是row major or column major（你想要的內循環以儘可能小的步驟訪問內存以防止緩存未命中）。其他一些優化技術詳述如下here。

2012-03-09 17:50:15 cjm

2

正如Yu-Had Lyu提到你可以用零填充它們，但是除非p，q和r接近，複雜性退化（執行填充的時間）。

要獲得關於本徵如何實現它的其他問題：

NUMERICS包實現矩陣乘法的方式通常是通過使用典型的O（PQR）的算法，但在'非數學」方式大量優化：堵（SIMD等）

一些軟件包（MATLAB，Octave，ublas）使用兩個名爲BLAS和LAPACK的庫，它們提供了以這種方式大量優化的線性代數基元（如矩陣乘法）（有時使用硬件特定的優化）。

AFAIK，Eigen只是使用阻塞和SIMD指令。

幾個常見的數字庫（包括Eigen）使用Strassen Algorithm。其原因實際上非常有趣：雖然複雜性更好（O（n ^（log2 7））），但由於執行了所有的添加，大哦背後的隱藏常量非常大 - 換句話說，該算法只是有用的在實踐中爲非常大矩陣。

注：有一個更有效（在漸進複雜性方面）算法比施特拉森的算法：Coppersmith–Winograd algorithm與O（N ^（2.3727）），但該常數是如此之大，這是它不可能在實踐中被使用。事實上相信存在一個以O（n^2）運算的算法（這是一個平凡的下界，因爲任何算法都需要至少讀取矩陣的n^2個元素）。

2012-05-19 16:13:51 cristicbz

相關問題