《矩阵相乘的快速算法》由会员分享，可在线阅读，更多相关《矩阵相乘的快速算法（11页珍藏版）》请在金锄头文库上搜索。
1、矩矩阵相乘的快速算法阵相乘的快速算法 算法介绍 矩阵相乘在进行 3D 变换的时候是经常用到的。在应用中常用矩阵相乘的定义算法对其进行计算。这个算法用到了大量的循环和相乘 运算，这使得算法效率不高。而矩阵相乘的计算效率很大程度上的影响了整个程序的运行速度，所以对矩阵相乘算法进行一些改进是 必要的。 这里要介绍的矩阵算法称为斯特拉森方法，它是由 v.斯特拉森在 1969 年提出的一个方法。 我们先讨论二阶矩阵的计算方法。 对于二阶矩阵 a11 a12 b11 b12 A = a21 a22 B = b21 b22 先计算下面 7 个量(1) x1 = (a11 + a22) * (b11 + b2
2、2); x2 = (a21 + a22) * b11; x3 = a11 * (b12 - b22); x4 = a22 * (b21 - b11); x5 = (a11 + a12) * b22; x6 = (a21 - a11) * (b11 + b12); x7 = (a12 - a22) * (b21 + b22); 再设 C = AB。根据矩阵相乘的规则，C 的各元素为(2) c11 = a11 * b11 + a12 * b21 c12 = a11 * b12 + a12 * b22 c21 = a21 * b11 + a22 * b21 c22 = a21 * b12 + a22
3、 * b22 比较(1)(2)，C 的各元素可以表示为(3) c11 = x1 + x4 - x5 + x7 c12 = x3 + x5 c21 = x2 + x4 c22 = x1 + x3 - x2 + x6 根据以上的方法，我们就可以计算 4 阶矩阵了，先将 4 阶矩阵 A 和 B 划分成四块 2 阶矩阵，分别利用公式计算它们的乘积，再使用 (1)(3)来计算出最后结果。 ma11 ma12 mb11 mb12 A4 = ma21 ma22 B4 = mb21 mb22 其中 a11 a12 a13 a14 b11 b12 b13 b14 ma11 = a21 a22 ma12 = a2
4、3 a24 mb11 = b21 b22 mb12 = b23 b24 a31 a32 a33 a34 b31 b32 b33 b34 ma21 = a41 a42 ma22 = a43 a44 mb21 = b41 b42 mb22 = b43 b44 实现 / 计算 2X2 矩阵 void Multiply2X2(float const float x2(f1_21 + f1_22) * f2_11); const float x3(f1_11 * (f2_12 - f2_22); const float x4(f1_22 * (f2_21 - f2_11); const float x5
5、(f1_11 + f1_12) * f2_22); const float x6(f1_21 - f1_11) * (f2_11 + f2_12); const float x7(f1_12 - f1_22) * (f2_21 + f2_22); fOut_11 = x1 + x4 - x5 + x7; fOut_12 = x3 + x5; fOut_21 = x2 + x4; fOut_22 = x1 - x2 + x3 + x6; / 计算 4X4 矩阵 void Multiply(CLAYMATRIX / (ma11 + ma22) * (mb11 + mb22) Multiply2X2
6、(fTmp00, fTmp01, fTmp02, fTmp03, m1._11 + m1._33, m1._12 + m1._34, m1._21 + m1._43, m1._22 + m1._44, m2._11 + m2._33, m2._12 + m2._34, m2._21 + m2._43, m2._22 + m2._44); / (ma21 + ma22) * mb11 Multiply2X2(fTmp10, fTmp11, fTmp12, fTmp13, m1._31 + m1._33, m1._32 + m1._34, m1._41 + m1._43, m1._42 + m1.
7、_44, m2._11, m2._12, m2._21, m2._22); / ma11 * (mb12 - mb22) Multiply2X2(fTmp20, fTmp21, fTmp22, fTmp23, m1._11, m1._12, m1._21, m1._22, m2._13 - m2._33, m2._14 - m2._34, m2._23 - m2._43, m2._24 - m2._44); / ma22 * (mb21 - mb11) Multiply2X2(fTmp30, fTmp31, fTmp32, fTmp33, m1._33, m1._34, m1._43, m1.
8、_44, m2._31 - m2._11, m2._32 - m2._12, m2._41 - m2._21, m2._42 - m2._22); / (ma11 + ma12) * mb22 Multiply2X2(fTmp40, fTmp41, fTmp42, fTmp43, m1._11 + m1._13, m1._12 + m1._14, m1._21 + m1._23, m1._22 + m1._24, m2._33, m2._34, m2._43, m2._44); / (ma21 - ma11) * (mb11 + mb12) Multiply2X2(fTmp50, fTmp51
9、, fTmp52, fTmp53, m1._31 - m1._11, m1._32 - m1._12, m1._41 - m1._21, m1._42 - m1._22, m2._11 + m2._13, m2._12 + m2._14, m2._21 + m2._23, m2._22 + m2._24); / (ma12 - ma22) * (mb21 + mb22) Multiply2X2(fTmp60, fTmp61, fTmp62, fTmp63, m1._13 - m1._33, m1._14 - m1._34, m1._23 - m1._43, m1._24 - m1._44, m
10、2._31 + m2._33, m2._32 + m2._34, m2._41 + m2._43, m2._42 + m2._44); / 第一块 mOut._11 = fTmp00 + fTmp30 - fTmp40 + fTmp60; mOut._12 = fTmp01 + fTmp31 - fTmp41 + fTmp61; mOut._21 = fTmp02 + fTmp32 - fTmp42 + fTmp62; mOut._22 = fTmp03 + fTmp33 - fTmp43 + fTmp63; / 第二块 mOut._13 = fTmp20 + fTmp40; mOut._14
11、 = fTmp21 + fTmp41; mOut._23 = fTmp22 + fTmp42; mOut._24 = fTmp23 + fTmp43; / 第三块 mOut._31 = fTmp10 + fTmp30; mOut._32 = fTmp11 + fTmp31; mOut._41 = fTmp12 + fTmp32; mOut._42 = fTmp13 + fTmp33; / 第四块 mOut._33 = fTmp00 - fTmp10 + fTmp20 + fTmp50; mOut._34 = fTmp01 - fTmp11 + fTmp21 + fTmp51; mOut._43
12、 = fTmp02 - fTmp12 + fTmp22 + fTmp52; mOut._44 = fTmp03 - fTmp13 + fTmp23 + fTmp53; 比较 在标准的定义算法中我们需要进行 n * n * n 次乘法运算，新算法中我们需要进行 7log2n 次乘法，对于最常用的 4 阶矩阵： 原算法 新算法 加法次数 48 72(48 次加法，24 次减法) 乘法次数 64 49 需要额外空间 16 * sizeof(float) 28 * sizeof(float) 新算法要比原算法多了 24 次减法运算，少了 15 次乘法。但因为浮点乘法的运算速度要远远慢于加/减法运算，所
13、以新算法的整体速 度有所提高。一、两个矩阵相乘的经典算法一、两个矩阵相乘的经典算法:若设 Q=M*N 其中，M 是 m1*n1 矩阵，N 是 m2*n2 矩阵。当 n1=m2 时有：for (i=1;ifor ( j=1; j=n2; +j)Qij=0;for(k=1; k=n1; +k) Qij+=Mik*Nkj; 此算法的时间复杂度是 O(m1*n1*n2)。二、斯特拉森算法斯特拉森方法，是由 v.斯特拉森在 1969 年提出的一个方法。我们先讨论二阶矩阵的计算方法。 对于二阶矩阵 a11 a12 b11 b12 A = a21 a22 B = b21 b22 先计算下面 7 个量(1)
14、x1 = (a11 + a22) * (b11 + b22); x2 = (a21 + a22) * b11; x3 = a11 * (b12 - b22); x4 = a22 * (b21 - b11); x5 = (a11 + a12) * b22; x6 = (a21 - a11) * (b11 + b12); x7 = (a12 - a22) * (b21 + b22); 再设 C = AB。根据矩阵相乘的规则，C 的各元素为(2) c11 = a11 * b11 + a12 * b21 c12 = a11 * b12 + a12 * b22 c21 = a21 * b11 + a22
15、 * b21 c22 = a21 * b12 + a22 * b22 比较(1)(2)，C 的各元素可以表示为(3) c11 = x1 + x4 - x5 + x7 c12 = x3 + x5 c21 = x2 + x4 c22 = x1 + x3 - x2 + x6 根据以上的方法，我们就可以计算 4 阶矩阵了，先将 4 阶矩阵 A 和 B 划分成四块 2 阶矩阵，分别利用公式计算它们的乘积，再使用(1)(3)来计算出最后结果。 ma11 ma12 mb11 mb12 A4 = ma21 ma22 B4 = mb21 mb22 其中 a11 a12 a13 a14 b11 b12 b13 b14 ma11 = a21 a22 ma12 = a23 a24 mb11 = b21 b22 mb12 = b23 b24 a31 a32 a
