★加星zzllrr小樂公眾號(hào)數(shù)學(xué)科普不迷路！

《量子雜志》每周都會(huì)闡釋推動(dòng)現(xiàn)代研究發(fā)展的重要理念之一。本周，計(jì)算機(jī)科學(xué)專欄作家Ben Brubaker將為你解讀計(jì)算機(jī)科學(xué)家為何尋求更好的方法來計(jì)算矩陣乘法。

圖源：量子雜志Quanta Magazine

作者：Ben Brubaker（量子雜志計(jì)算機(jī)科學(xué)專欄作家）2025-6-30

譯者：zzllrr小樂（數(shù)學(xué)科普公眾號(hào)）2025-7-1

1925年夏天，年輕的物理學(xué)家維爾納·海森堡（Werner Heisenberg）前往偏遠(yuǎn)的黑爾戈蘭島，尋求緩解季節(jié)性過敏癥狀。10天后，他帶著一個(gè)方程回來，這個(gè)方程現(xiàn)在是量子物理學(xué)理論的核心。

雖然該方程正確地預(yù)測(cè)了實(shí)驗(yàn)結(jié)果，但只有一個(gè)問題：它涉及操縱數(shù)字表的奇怪規(guī)則。海森堡本人不知道該如何看待數(shù)學(xué)，直到他的導(dǎo)師馬克斯·玻恩（Max Born）將這些表格識(shí)別為當(dāng)時(shí)晦澀難懂的數(shù)學(xué)對(duì)象，稱為矩陣（matrices）。

一百年后，矩陣絕非晦澀難懂。它們?cè)诳茖W(xué)和技術(shù)方面有無數(shù)的應(yīng)用，從基礎(chǔ)物理學(xué)到計(jì)算機(jī)圖形學(xué)再到人工智能。尋找更好的矩陣乘法算法是計(jì)算機(jī)科學(xué)中最具標(biāo)志性的問題之一。

矩陣來自稱為線性代數(shù)（linear algebra）的數(shù)學(xué)分支，它研究涉及多個(gè)變量的簡(jiǎn)單方程。線性代數(shù)中的中心數(shù)學(xué)對(duì)象（稱為向量vector）是描述系統(tǒng)特定性質(zhì)的數(shù)字列表：對(duì)象的空間方向、量子粒子的狀態(tài)，甚至是單詞的含義 https://www.quantamagazine.org/how-embeddings-encode-what-words-mean-sort-of-20240918/ 。

矩陣是二維數(shù)字表，表示將一個(gè)向量轉(zhuǎn)換為另一個(gè)向量的過程。在最簡(jiǎn)單的情況下，矩陣可能表示旋轉(zhuǎn)對(duì)象的特定方式。但矩陣也可以表示更奇特的變換。在物理學(xué)中，它們描述了量子態(tài)如何隨時(shí)間演變。在計(jì)算機(jī)科學(xué)中，它們控制著ChatGPT等AI模型在給定輸入時(shí)如何生成輸出。

如果有兩個(gè)連續(xù)的變換，則需要將相應(yīng)的矩陣相乘，這涉及到以特定組合將它們的元素相加和相乘。但是，當(dāng)應(yīng)用于大型矩陣（如AI模型中使用的矩陣）時(shí)，這種標(biāo)準(zhǔn)方法會(huì)變得非常緩慢。研究人員的目標(biāo)是設(shè)計(jì)更好的矩陣乘法算法，也就是使用更高效的步驟序列獲得與標(biāo)準(zhǔn)方法相同的答案的過程。50多年來，對(duì)更好算法的追求一直是一個(gè)豐富的研究脈絡(luò)。

新增的和值得注意的內(nèi)容

矩陣乘法算法的研究始于1969年，當(dāng)時(shí)數(shù)學(xué)家Volker Strassen發(fā)現(xiàn)了一種計(jì)算2×2矩陣乘積的方法，該方法只需將其元素的特定組合做7次乘法，而標(biāo)準(zhǔn)程序則為8次。

這聽起來可能并不多，但是當(dāng)你反復(fù)將大矩陣切成較小的塊并每次都應(yīng)用Strassen算法時(shí)，乘法步驟就會(huì)減少一個(gè)。Strassen的發(fā)現(xiàn)開啟了長(zhǎng)達(dá)數(shù)十年的尋找最佳算法的序幕，用于非常大的矩陣相乘。

2021年，Kevin Hartnett調(diào)查了矩陣乘法算法的歷史 https://www.quantamagazine.org/mathematicians-inch-closer-to-matrix-multiplication-goal-20210323/ 和最新發(fā)展。去年，Steve Nadis報(bào)告了一種新方法 https://www.quantamagazine.org/new-breakthrough-brings-matrix-multiplication-closer-to-ideal-20240307/ ，該方法產(chǎn)生了十多年來最大的改進(jìn)。

一些研究人員采用不同的方法來搜索矩陣乘法算法。他們不是試圖為大型矩陣尋找最佳算法，而是尋求在較小比例下工作的更好方法，例如4×4或5×5矩陣。2022年，Google DeepMind的研究人員使用一種全新的定性方法為這項(xiàng)工作做出了重大貢獻(xiàn)：

他們訓(xùn)練了一個(gè)名為AlphaTensor的AI系統(tǒng)來自動(dòng)搜索矩陣乘法算法，并發(fā)現(xiàn)了在一些特殊情況下效果更好的算法。在我作為計(jì)算機(jī)科學(xué)記者的第一個(gè)故事 https://www.quantamagazine.org/ai-reveals-new-possibilities-in-matrix-multiplication-20221123/ 中報(bào)道了這個(gè)結(jié)果。量子雜志還制作了一段視頻，探討了AlphaTensor的搜索工作原理 https://www.youtube.com/watch?v=fDAPJ7rvcUw 。

歸根結(jié)底，研究人員研究矩陣乘法，因?yàn)樗墙鉀Q線性代數(shù)問題的成熟方法。但這并不是唯一的方法。

2021年，Hartnett報(bào)告說，在某些情況下，利用隨機(jī)性力量 https://www.linkedin.com/pulse/counterintuitive-power-randomness-quanta-magazine-riaoe/ 的替代方法 https://www.quantamagazine.org/new-algorithm-breaks-speed-limit-for-solving-linear-equations-20210308/ 比最著名的矩陣乘法算法略快。

這可能是一個(gè)小的改進(jìn)，但它說明了矩陣乘法算法的研究仍然充滿驚喜。正如計(jì)算機(jī)科學(xué)家周任飛在接受Nadis采訪時(shí)所說，“人們?nèi)蕴幱诶斫膺@個(gè)古老問題的早期階段。”

計(jì)算機(jī)科學(xué)家周任飛

網(wǎng)絡(luò)上的報(bào)道

來自YouTube頻道3Blue1Brown的這個(gè)視頻系列 https://www.3blue1brown.com/topics/linear-algebra 是對(duì)線性代數(shù)和矩陣的精彩介紹。

數(shù)學(xué)教育家Trefor Bazett發(fā)布了一個(gè)很好的視頻， https://www.youtube.com/watch?v=sZxjuT1kUd0 介紹了Strassen的矩陣乘法算法。

5月，IEEE Spectrum報(bào)告了Google DeepMind推出的一款名為AlphaEvolve的新型通用AI系統(tǒng) https://spectrum.ieee.org/deepmind-alphaevolve ，該系統(tǒng)發(fā)現(xiàn)了比AlphaTensor更好的矩陣乘法算法。

參考資料

https://mailchi.mp/quantamagazine.org/the-mystery-of-the-muon-4866944

https://www.quantamagazine.org/how-embeddings-encode-what-words-mean-sort-of-20240918/

https://www.quantamagazine.org/mathematicians-inch-closer-to-matrix-multiplication-goal-20210323/

https://www.quantamagazine.org/new-breakthrough-brings-matrix-multiplication-closer-to-ideal-20240307/

https://www.quantamagazine.org/ai-reveals-new-possibilities-in-matrix-multiplication-20221123/

https://www.youtube.com/watch?v=fDAPJ7rvcUw

https://www.linkedin.com/pulse/counterintuitive-power-randomness-quanta-magazine-riaoe/

https://www.quantamagazine.org/new-algorithm-breaks-speed-limit-for-solving-linear-equations-20210308/

https://www.3blue1brown.com/topics/linear-algebra

https://www.youtube.com/watch?v=sZxjuT1kUd0

https://spectrum.ieee.org/deepmind-alphaevolve

出版社和作家自薦通道

小樂數(shù)學(xué)科普薦書

小樂數(shù)學(xué)科普近期文章

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數(shù)學(xué)

更加

易學(xué)易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評(píng)論、點(diǎn)贊、在看、在聽

收藏、分享、轉(zhuǎn)載、投稿

查看原始文章出處

點(diǎn)擊zzllrr小樂

公眾號(hào)主頁

加星★

數(shù)學(xué)科普不迷路！