Strassen算法-介绍
- 格式：docx
- 大小：161.74 KB
- 文档页数：5
Strassen算法
在了解Strassen算法之前，先来了解一下矩阵乘法：
矩阵乘法的c语言程序：
#include"stdio.h"
float main()
{
float a[100][100],b[100][100],c[100][100]; //定义三个数组分别储存三个矩阵A,B,C
int m1,n1,m2,n2,i1,j1,i2,j2,i3,j3,i4,j4,k;
float s[100][100]={0}; //初始化数组s
printf("请输入矩阵A的行数m1和列数n1:");
scanf("%d%d",&m1,&n1);
printf("请输入矩阵B的行数m2和列数n2:");
scanf("%d%d",&m2,&n2);
printf(">>>>>>>>>>>>>>>>>>>>>>>>>>>\n"); //便于观看结果，将结果与输入分开
if(n1!=m2) printf("不可以相乘！！！\n\n");
if(m1>100||n1>100||m2>100||n2>100) printf("数目过多，溢出！！！\n\n");
else{ for(i2=1;i2<=m2;i2++)
for(j2=1;j2<=n2;j2++)
{
printf("A[%d][%d]=",i2,j2); scanf("%f",&a[i2][j2]); } //输入矩阵A的元素
printf(">>>>>>>>>>>>>>>>>>>>>>\n");
for(i2=1;i2<=m2;i2++)
{ for(j2=1;j2<=n2;j2++)
{
printf("B[%d][%d]=",i2,j2);
scanf("%f",&b[i2][j2]); } //输入矩阵B的元素
}
}
printf("矩阵A\n\n"); //打印矩阵A便于观看与检查
for(i3=1;i3<=m1;i3++)
{
for(j3=1;j3<=n1;j3++)
{printf("%f\t",a[i3][j3]); if(j3==n1)printf("\n");}
}
printf(">>>>>>>>>>>>>>>>>>>>>>>>>\n\n矩阵B：
"); //与矩阵B的打印隔开，便于观看
for(i4=1;i4<=m2;i4++)
{
for(j4=1;j4<=n2;j4++)
{printf("%f\t",b[i4][j4]);
if(j4==n2)printf("\n"); }}
printf(">>>>>>>>>>>>>>>>>>>>>>>>>\n\n矩阵C=A*B= \n");
for(i4=1;i4<=m1;i4++)
{ for(j4=1;j4<=n2;j4++)
{for(k=1;k<=n1;k++)
{s[i4][j4]=s[i4][j4]+a[i4][k]*b[k][j4]; }//定义矩阵的乘法，相乘时，有一个指标是一样的，都用k
c[i4][j4]=s[i4][j4];}
printf("矩阵C是： \n");
for(i4=1;i4<=m1;i4++)
{
for(j4=1;j4<=n2;j4++)
{printf("%f\t",c[i4][j4]);if(j4==n2)printf("\n");}
}
return 0;
}}
设甲，乙两个方阵通过环
ŕ。我们要计算的矩阵产品Ç
如果2型Ñ ×2 矩阵甲，乙，ň我们填零丢失的行和列。我们分区甲，乙，Ç成大小相等的块矩阵
【Let A, B be two square matrices over aring R. We want to calculate the matrix product C as
If the matrices A, B are not of type 2n x 2n we fill the missing rows and columns with zeros.
We partition A, B and C into equally sizedblock matrices】
The left column represents 2x2 matrix multiplication. Naïve matrix multiplication requires one multiplication
for each "1" of the left column. Each of the other columns represents a single one of the 7 multiplications in
the algorithm, and the sum of the columns gives the full matrix multiplication on the left. 【左边的列表示的2x2 矩阵乘法。朴素的矩阵乘法，需要为每一个“1”的左边的列的一个乘法。7乘法算法的其他列中的每一个都代表一个单一的一个，并在左侧的列的总和给出了完整的矩阵乘法。】
with
Then
采用这种结构，我们并没有减少乘法的次数。我们还需要8次乘法计算C[I,J]矩阵，我们需要的时候使用标准的矩阵乘法相同数量的乘法。
现在来的重要组成部分。我们定义新的矩阵
只使用7的乘法（每个M k个 之一）而不是8。现在我们就可以在M K 表示C[i.j]是这样的
[We may now express the C i,j in terms of M k , like this:]
【We iterate this division process n times (recursively) until the submatrices degenerate into numbers (elements of
the ring R). The resulting product will be padded with zeroes just like A and B, and should be stripped of the
corresponding rows and columns.
Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small
enough submatrices, for which those algorithms are more efficient. The particular crossover point for which
Strassen's algorithm is more efficient depends on the specific implementation and hardware. Earlier authors had
estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized
implementations.[1] However, it has been observed that this crossover point has been increasing in recent years, and
a 2010 study found that even a single step of Strassen's algorithm is often not beneficial on current architectures,
compared to a highly optimized traditional multiplication, until matrix sizes exceed 1000 or more, and even for
matrix sizes of several thousand the benefit is typically marginal at best (around 10% or less).[2]
】
我们本的分裂过程Ň次（递归）重复，直到子矩阵退化成号（环ŕ的元素）。将所得的产物将被填充零就像甲和乙，并应被剥离的相应的行和列。
实用的Strassen算法开关矩阵乘法的足够小的子矩阵的标准方法的实现，这些算法是更有效的。取决于具体的实现和硬件的特定的交叉点的Strassen算法是更有效的。此前笔者曾预计，Strassen重的算法是更快的矩阵与宽度从32到128优化的实现。[ 1 ]然而，它已被观察到，这个交叉点已被越来越多，近年来，和一个2010年的研究发现，即使一个单步骤的Strassen重的算法是不利于对当前的体系结构中，一个高度优化的传统乘法相比，直到矩阵大小超过1000个或更多，和甚至为矩阵大小几千的好处是通常边际充其量（约10％或更少的）[ 2 ]
渐近复杂性(Asymptotic complexity)
标准的矩阵乘法大约需要2 ñ 3（Ň = 2 Ň）算术运算（加法和乘法）的渐近复杂度为O（Ñ 3）。
Strassen算法所需的加法和乘法的数目可以计算如下：让f （）的操作的数量为2 Ñ ×2 n的矩阵。然后通过递归应用Strassen算法，我们看到，f （ n ）的= 7 f（Ñ -1）+ 14正 ，对于某个常数，在每个应用程序的算法进行的加法的数目取决于。因此，f（Ñ）=（7 + O（1））Ñ，即乘以矩阵大小Ň = 2 n的Strassen算法的渐近复杂性
然而，算术运算的数目的减少在一个有所减少的数值稳定性的价格，并且该算法也需要天真算法相比显着更多的内存。必须具有它们的尺寸扩展到在存储多达四次一样多的元素的下一个2的幂，从而导致这两个初始矩阵，和七个辅助矩阵的每一个包含在扩大的四分之一的元素
