n階矩陣乘法最優解的時間複雜度再次被突破，達到了O(n^2.3728596)。
按定義直接算的話，時間複雜度是O(n³)。
光這麼說可能不太直觀，從圖上可以看出，n足夠大時優化後的算法就開始表現出明顯優勢。
矩陣乘法在深度學習中有着廣泛的應用，像卷積神經網絡(CNN)中最耗時間的卷積計算，就經常被映射成矩陣乘法。
△圖源：DOI 10.3390/electronics8010065
雖然在具體實現上還有很多障礙，但矩陣相乘底層算法的優化，至少在理論上爲深度學習節省時間提供了可能性。
而科學家們努力的目標，是使n階矩陣乘法的時間複雜度儘可能接近理論上的最快速度O(n²)。
本次研究共同作者是一對師徒。
△左：Alman 右：Vassilevska Williams
Josh Alman目前是哈佛大學的博士後研究員，主要研究方向是算法設計和複雜度理論。
Virginia Vassilevska Williams是他在MIT讀博士期間的導師，研究方向是組合數學和圖論在計算領域的應用。
Strassen：用加法替代乘法
矩陣乘法的時間複雜度直到1969年才第一次被Volker Strassen降至O(n³)以下。
看過《算法導論》的同學應該很熟悉Strassen算法。
以2階矩陣相乘爲例，總共需要進行2³=8次乘法，而2ⁿ的高階矩陣相乘可以用分塊法不斷迭代細分解成若干個2階子矩陣相乘。
Strassen巧妙地通過構造7箇中間變量，用增加14次加法爲代價省去了一次乘法。
對於
定義
則有
像這樣，在M₁-M₇的計算中只有7次乘法操作。
由於矩陣乘法計算中乘法的複雜度是O(n³)，而加法的複雜度只有O(n²)，n越大時此方法的收益就越大。
且分塊後每個子矩陣相乘都可以省去一次乘法操作，最終把時間複雜度降低到O(n^2.807)。
這麼繞的算法到底怎麼想出來的？可惜Strassen在論文中並沒有說明這一點。
Strassen算法在實際應用時受到很大限制，如運行時會創建大量的臨時變量，在n不夠大時反倒更耗費時間。
還有隻適用於稠密矩陣，針對稀疏矩陣有更快的專門算法。
但最重要的是，Strassen的辦法讓學界意識到，原來矩陣乘法問題還有優化空間啊！
激光法：用張量替代矩陣
20世紀70年代末期,科學家們找到了解決問題的新思路，將矩陣計算轉換爲張量計算。
1981年，Schonhage將此方法優化到O(n^2.522)後，Strassen把這個方法命名爲「激光法(Laser Method)」，因爲和正交偏振激光有相似之處。
在後來的幾十年中，矩陣乘法的每次優化都來自激光法的優化，即如何更有效地把矩陣問題轉換成張量問題。
Alman和Williams的優化算法只比14年LeGall的O(n^2.3728639)減少了4e^(-6)。
從歷次優化的幅度來看，似乎已逼近激光法的極限。
能算得更快了嗎？
激光法很少在實際中應用，因爲它只在n足夠大，大到現代計算機硬件幾乎無法處理的時候才能提供優勢。
這樣的算法被稱作「銀河算法(Galatic Algorithm)」。
在業界使用最多的還是通過分塊法和並行處理控制矩陣的規模。當n不大時，再通過循環展開，內存佈局優化等辦法針對直覺算法的優化。
還有一點，現實中由於浮點數精度的限制，Strassen法和激光法在計算大規模矩陣時都會產生不小的誤差。
△圖源：DOI 10.1109/ICPADS.2011.130
矩陣乘法的加速，看來還沒那麼容易。
論文鏈接
https://arxiv.org/abs/2010.05846
參考鏈接：
[1]https://www.quantamagazine.org/mathematicians-inch-closer-to-matrix-multiplication-goal-20210323
[2]https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm
[3]https://www.researchgate.net/publication/330315719_A_Uniform_Architecture_Design_for_Accelerating_2D_and_3D_CNNs_on_FPGAs
[4]http://www.theoryofcomputing.org/articles/gs005/gs005.pdf
[5]https://www.youtube.com/watch?v=J5LK1SChxGs
[6]http://www.cs.toronto.edu/~yuvalf/AmbFilLeG14.pdf
—完—
@量子位 · 追蹤AI技術和產品新動態