矩阵乘法 02 3005 2000 00 06 04 北京大学信息学院 版权所有,转载或翻印必究 Page 26
北京大学信息学院 ©版权所有，转载或翻印必究 Page 26 矩阵乘法 3 0 0 5 0 -1 0 0 2 0 0 0 0 2 1 0 -2 4 0 0 0 6 -1 0 0 4 =
经典矩阵乘法 A[c1..d1][c3.d3],B[c3..d3][c2.d2] C[c1..d1][c2..d2] d3 C=A×B(C1;=∑ Aik BK) k=c3 for(i=c1; i<=d1; i++) for (j=c2 j<=d2 j++)t sum =0 for (k=c3: k<=d3: k++) sum sum +All, k]*Blk, j Cli, j]=sum 北京大学信息学院 版权所有,转载或翻印必究 Page 27
北京大学信息学院 ©版权所有，转载或翻印必究 Page 27 经典矩阵乘法 ◼ A[c1..d1][ c3..d3]，B[c3..d3][ c2..d2], C[c1..d1][c2..d2]。 ◼ d3 C＝A×B (Cij＝∑Aik ·Bkj) k=c3 ◼ for (i=c1; i<=d1; i++) for (j=c2; j<=d2; j++) { sum = 0; for (k=c3; k<=d3; k++) sum = sum + A[i,k]*B[k,j]; C[i，j] = sum; }
p=d1-c1+1,m=d3-c3+1, n=d2c2+1; A为p×m的矩阵,B为m×n的矩阵, 乘得的结果C为p×n的矩阵 经典矩阵乘法所需要的时间代价为 o(p×m×n 北京大学信息学院 版权所有,转载或翻印必究 Page 28
北京大学信息学院 ©版权所有，转载或翻印必究 Page 28 ◼ p=d1-c1+1，m=d3-c3+1， n=d2-c2+1； ◼ A为p×m的矩阵，B为m×n的矩阵， 乘得的结果C为p×n的矩阵 ◼ 经典矩阵乘法所需要的时间代价为 O(p×m×n)
稀疏矩阵乘法 template <class T> SMatrix <int>*SMatrix<T>: MatrixMutil(SMatrix <int>*left S Matrix<int>*right if(dleft->Getcolnumo!=right->GetRownumo) return nullr//行列不匹配不能相乘 intI=0;//第一个矩阵的行数 int]=0}//第二个矩阵的列数 SMatrix<T>* ResultMatrix= new smatriⅸ<T>0;/结果矩阵 ResultMatrix->MallocMem(left-> GetRownumO right > Getcolnumo//.结果矩阵分配空间 for(I=l;I<=left->GetRownum O;I++) //开始相乘 OLNode<T>* Row Next= ResultMatrix->rowhead[I]; 北京大学信息学院 版权所有,转载或翻印必究 Page 29
北京大学信息学院 ©版权所有，转载或翻印必究 Page 29 稀疏矩阵乘法 template <class T> SMatrix<int>*SMatrix<T>::MatrixMutil(SMatrix<int>*left,S Matrix<int>*right) { if(left->GetColnum()!=right->GetRownum()) return NULL;//行列不匹配不能相乘 int I=0; //第一个矩阵的行数 int J=0; //第二个矩阵的列数 SMatrix<T> *ResultMatrix=new SMatrix<T>();//结果矩阵 ResultMatrix->MallocMem(left->GetRownum(),right- >GetColnum());//为结果矩阵分配空间 for(I=1;I<=left->GetRownum();I++) {//开始相乘 OLNode<T>* RowNext=ResultMatrix->rowhead[I];
for(J=1jj<=right->Getcolnum o;J++) //扫描所有的列 OLNode<T>* ColNext= ResultMatrix->colheadJJ] int result=0 oLNode<int>*『oWs=eft> rowhead工 OLNode<int>* cols=right->colheadpJ if((rows==NULL)I I(cols==NULL)) break//新行没有非零元素 while((rows! =NULL)&&(cols!=NULL)) //所有行列都未非零的元素相乘 if(rows->col<cols->row) rows=rows->right; else if(rows->col>cols->row) cols=cols->down: 北京大学信息学院 版权所有,转载或翻印必究 Page 30
北京大学信息学院 ©版权所有，转载或翻印必究 Page 30 for(J=1;J<=right->GetColnum();J++) {//扫描所有的列 OLNode<T>* ColNext=ResultMatrix->colhead[J]; int result=0; OLNode<int> * rows=left->rowhead[I]; OLNode<int>* cols=right->colhead[J]; if((rows==NULL)||(cols==NULL)) break;//新行没有非零元素 while((rows!=NULL)&&(cols!=NULL)) {//所有行列都未非零的元素相乘 if(rows->col<cols->row) { rows=rows->right; } else if(rows->col>cols->row) { cols=cols->down; }