斯特拉森矩陣乘法：1969年斯特拉森利用分治策略並加上一些處理技巧設計出的一種矩陣乘法。
基本介紹
- 中文名：斯特拉森矩陣乘法
- 發明時間：1969年
- 作者：斯特拉森
- 利用方法：分治策略
簡介,具體算法,
簡介
為了得到兩矩陣相乘的算法：
1、定義一個小問題，並指明那個問題如何進行乘法運算，
2、確定一個大問題，進行劃分，並指明如何對這些小問題進行乘法運算。
這就是用分治方法進行矩陣相乘的思想。
具體算法
設A和B是倆個n x n的矩陣，其中n可以寫成2的冪。將A和B分別等分成4個小矩陣，此時如果把A和B都當成2x2矩陣來看,每個元素就是一個（n/2）x（n/2）矩陣，而A和B的成積就可以寫成
其中 利用斯特拉森方法得到7個小矩陣，分別定義為：
矩陣
可以通過7次矩陣乘法、6次矩陣加法和4次矩陣減法計算得出，前述4個小矩陣
可以由矩陣 通過6次矩陣加法和2次矩陣減法得出，方法如下：
用上述方案解n=2；矩陣乘法；假定施特拉斯矩陣分割方案僅用於n＞=8的矩陣乘法，而對於小於8的矩陣直接利用公式計算；n的值越大，斯拉特森方法更方便；設T(n)表示斯特拉森分治運算法所需時間，因為大的矩陣會被遞歸分成小矩陣直到每個矩陣的大小小於或等於k，所以T(n)的遞歸表達式為T(n)=d(n＜=k)；T(n)=7*t(n/2)+cn2（n平方）（n＞k）,其中cn2表示完成18次（n/2）(n/2)接矩陣的加減法，以及把大小為N的矩陣分割成小矩陣所需的時間；
