斯特拉森的矩陣乘法在哪裏有用？

Question

Strassen的矩陣乘法算法只比傳統的O(N^3)算法略有改善。它具有較高的常數因子，實施起來要困難得多。考慮到這些缺點，strassens算法實際上是否有用，它是否在任何用於矩陣乘法的庫中實現？而且，圖書館如何實施矩陣乘法？

Answer 1

由於以下原因，Strassen的方法一般不適用於實際應用。

1. 斯特拉森方法中使用的常數很高，對於典型應用，樸素方法效果更好。
2. 對於稀疏矩陣，有更好的方法爲他們特別設計 。
3. 遞歸中的子矩陣需要額外的空間。
4. 因爲 非整數值計算機算法的精度有限的，更大的誤差在施特拉森的算法 積累比天真方法。

Answer 2

因此，斯特拉森算法的思想是它更快（漸近地說）。如果你正在處理巨大的矩陣或者大量的矩陣乘法，這可能會產生很大的影響。然而，僅僅因爲它漸近地漸近並不能使它成爲最有效的算法。有各種各樣的實現考慮因素，如緩存和架構特定的怪癖。也有平行性考慮。

我認爲你最好的選擇是看看共同的圖書館，看看他們在做什麼。例如，看看BLAS。我認爲Matlab使用MAGMA。

Answer 3

• 邊際改進：確實如此，但隨着矩陣規模的增長而增長。
• 更高的常數因子：Strassen算法的實際實現對於特定尺寸以下的塊使用常規n^3，所以這並不重要。
• 難以執行：無論如何。

至於什麼在實踐中使用：首先，你必須明白，乘以2個極大的相稠密矩陣是異常。更經常的是，它們中的一個或兩個都是稀疏對稱或上三角或其他模式，這意味着有相當多的專用工具對於有效的大型矩陣乘法工具箱是必不可少的。對此，對於巨型密集矩陣，Strassen的解決方案。

Answer 4

在合適的時機停下來非常重要。

使用1,000 x 1,000矩陣，您可以通過執行7個500 x 500產品以及幾個附加項將它們相乘。這可能很有用。也許500 x 500。 10×10矩陣，很可能不是。你只需要在什麼時候停止做一些實驗。

但是當行數增長32倍時，Strassen算法只保存一個因子2（最好），係數數量增加1,024，總時間增長16,807倍而不是32,768。在實踐中，這是一個「不變的因素」。我想說，通過首先調換第二個矩陣，您可以獲得更多收益，這樣您就可以逐行乘以行，然後仔細查看緩存大小，儘可能進行矢量化，然後分配到不相互影響的多個內核。