施特拉森演算法

施特拉森演算法(英語:Strassen algorithm)是一個計算矩陣乘法演算法,時間複雜度為

簡介

編輯
 
矩陣乘法演算法的演進。

施特拉森演算法在1969年由沃爾克·施特拉森所提出,是第一個時間複雜度低於 矩陣乘法演算法。由於演算法簡單理解,且為第一個被提出來的特性,常被演算法教材拿來當作主定理(英語:Master theorem)計算時間複雜度的例子。

另外,因為施特拉森演算法證明了矩陣乘法存在時間複雜度低於 的演算法,使得更多學者投入研究,尋找更快的演算法。

算法

編輯

定義

編輯

   上的方矩陣。求兩者的積 。一般矩陣可以填0的方法計算令它成為 矩陣

 

計算

編輯

A, B, C分成相等大小的方塊矩陣:

 

 

於是

 
 
 
 

引入新矩陣

 
 
 
 
 
 
 

可得:

 
 
 
 

其中 的計算也是使用施特拉森演算法求得。

評論

編輯

一般矩陣乘法的時間複雜度為 ,施特拉森演算法因為只有每次的分治法(英語:Divide and conquer algorithm)只有七個矩陣乘法運算,所以依照主定理(英語:Master theorem)可以得出時間複雜度為 。但Strassen演算法的數值穩定性較差。

現時時間複雜度最低的矩陣乘法演算法是Coppersmith-Winograd方法的一種擴展方法,其算法複雜度為 )。[1]

相關連結

編輯

參考來源

編輯
  1. ^ Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd (PDF). [2014-01-14]. (原始內容存檔 (PDF)於2013-10-08). 而1990年Coppersmith-Winograd方法提出時的算法複雜度為