矩陣乘法計(jì)算速度再次突破極限，我煉丹能更快了嗎？| 哈佛、MIT

夢晨 2021-03-26 13:20:38 來源：量子位

夢晨 發(fā)自 凹非寺
量子位 報(bào)道 | 公眾號 QbitAI

n階矩陣乘法最優(yōu)解的時(shí)間復(fù)雜度再次被突破，達(dá)到了O(n^2.3728596)。

按定義直接算的話，時(shí)間復(fù)雜度是O(n3)。

光這么說可能不太直觀，從圖上可以看出，n足夠大時(shí)優(yōu)化后的算法就開始表現(xiàn)出明顯優(yōu)勢。

矩陣乘法在深度學(xué)習(xí)中有著廣泛的應(yīng)用，像卷積神經(jīng)網(wǎng)絡(luò)(CNN)中最耗時(shí)間的卷積計(jì)算，就經(jīng)常被映射成矩陣乘法。

△圖源：DOI 10.3390/electronics8010065

雖然在具體實(shí)現(xiàn)上還有很多障礙，但矩陣相乘底層算法的優(yōu)化，至少在理論上為深度學(xué)習(xí)節(jié)省時(shí)間提供了可能性。

而科學(xué)家們努力的目標(biāo)，是使n階矩陣乘法的時(shí)間復(fù)雜度盡可能接近理論上的最快速度O(n2)。

本次研究共同作者是一對師徒。

△左：Alman 右：Vassilevska Williams

Josh Alman目前是哈佛大學(xué)的博士后研究員，主要研究方向是算法設(shè)計(jì)和復(fù)雜度理論。

Virginia Vassilevska Williams是他在MIT讀博士期間的導(dǎo)師，研究方向是組合數(shù)學(xué)和圖論在計(jì)算領(lǐng)域的應(yīng)用。

Strassen：用加法替代乘法

矩陣乘法的時(shí)間復(fù)雜度直到1969年才第一次被Volker Strassen降至O(n3)以下。

看過《算法導(dǎo)論》的同學(xué)應(yīng)該很熟悉Strassen算法。

以2階矩陣相乘為例，總共需要進(jìn)行23=8次乘法，而2?的高階矩陣相乘可以用分塊法不斷迭代細(xì)分解成若干個(gè)2階子矩陣相乘。

Strassen巧妙地通過構(gòu)造7個(gè)中間變量，用增加14次加法為代價(jià)省去了一次乘法。

對于

定義

則有

像這樣，在M?-M?的計(jì)算中只有7次乘法操作。由于矩陣乘法計(jì)算中乘法的復(fù)雜度是O(n3)，而加法的復(fù)雜度只有O(n2)，n越大時(shí)此方法的收益就越大。

且分塊后每個(gè)子矩陣相乘都可以省去一次乘法操作，最終把時(shí)間復(fù)雜度降低到O(n^2.807)。

這么繞的算法到底怎么想出來的？可惜Strassen在論文中并沒有說明這一點(diǎn)。

Strassen算法在實(shí)際應(yīng)用時(shí)受到很大限制，如運(yùn)行時(shí)會創(chuàng)建大量的臨時(shí)變量，在n不夠大時(shí)反倒更耗費(fèi)時(shí)間。

還有只適用于稠密矩陣，針對稀疏矩陣有更快的專門算法。

但最重要的是，Strassen的辦法讓學(xué)界意識到，原來矩陣乘法問題還有優(yōu)化空間??！

激光法：用張量替代矩陣

20世紀(jì)70年代末期,科學(xué)家們找到了解決問題的新思路，將矩陣計(jì)算轉(zhuǎn)換為張量計(jì)算。

1981年，Schonhage將此方法優(yōu)化到O(n^2.522)后，Strassen把這個(gè)方法命名為“激光法(Laser Method)”，因?yàn)楹驼黄窦す庥邢嗨浦帯?/p>

在后來的幾十年中，矩陣乘法的每次優(yōu)化都來自激光法的優(yōu)化，即如何更有效地把矩陣問題轉(zhuǎn)換成張量問題。

Alman和Williams的優(yōu)化算法只比14年LeGall的O(n^2.3728639)減少了4e^(-6)。

從歷次優(yōu)化的幅度來看，似乎已逼近激光法的極限。

能算得更快了嗎？

激光法很少在實(shí)際中應(yīng)用，因?yàn)樗辉趎足夠大，大到現(xiàn)代計(jì)算機(jī)硬件幾乎無法處理的時(shí)候才能提供優(yōu)勢。

這樣的算法被稱作“銀河算法(Galatic Algorithm)”。

在業(yè)界使用最多的還是通過分塊法和并行處理控制矩陣的規(guī)模。當(dāng)n不大時(shí)，再通過循環(huán)展開，內(nèi)存布局優(yōu)化等辦法針對直覺算法的優(yōu)化。

還有一點(diǎn)，現(xiàn)實(shí)中由于浮點(diǎn)數(shù)精度的限制，Strassen法和激光法在計(jì)算大規(guī)模矩陣時(shí)都會產(chǎn)生不小的誤差。

△圖源：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