程序设计百科

广告

稀疏矩阵的乘法算法4

2012-06-19 10:50:11 本文行家:玻尔特.李

程序分析,稀疏矩阵乘法算法 内容提要: (1)稀疏矩阵三元组表数据结构总结 (2)程序详细分析(C语言版数据结构)-->程序功能结构

需要帮助,善用双手需要帮助善用双手

§1.2   乘法算法

      两个稀疏矩阵相乘1

1.稀疏矩阵数据结构相关集

       从矩阵的逻辑结构可知,矩阵有三个层次:矩阵,行或列向量,元素(构成平面数表)。分块矩阵在程序中的应用应该也是有益的。矩阵的结构是位置的排列,也有重组与重构。考虑到对称矩阵,稀疏矩阵等特殊矩阵,结构有具体的不同,描述的内容不一样。稀疏矩阵还有存储数组重组矩阵的方法,这个存储数组并不规则,不能像一般矩阵的数组反应矩阵的逻辑结构,因此需要辅助存储结构。

       矩阵不仅仅是数的集合,而且有位置的排列,称为结构。对矩阵位置排列的描述,使用辅助数组。

       特殊稀疏矩阵的数据结构集

 (1)三元组表

//----稀疏矩阵的有行逻辑链接的三元组顺序表----//

#define   MAXSIZE   12500

#define   MAXRC    1000

Typedef struct{

            int    i,j;             //该非0元的行下标row和列下标col

                                      //有行下标或列下标相同的三元组

           ElemType  e;

}Triple;    //三元组元素

typedef struct{

       Triple data[MAXSIZE+1];   //0元三元组

       int   rpos[MAXRC+1];    //各行第一个非0元的位置表?.

                                      不是可选项

         int   mu,nu,tu;           //矩阵行数,列数和非0元个数

}RLSMatrix; //有行链接信息的三元组表

 把三元组与行位置表存放在一起构成一个记录,而不是辅助数组的方式。

2)辅助存储结构

//----稀疏矩阵的辅助存储数组----//

      int num[nu];

      int cpot[nu];

      num[col]:表示矩阵M中第col列中非0元的个数,从计算公式可知,等于T.data[]col行中非0元的个数。                        

      cpot[col]指示M中第col列的第一个非0元在T.data[]中的恰当位置。有公式: 

2

      cpot[col]等于T的第col行在T.data[]中的第一个非0元的位置。

2.程序分析

1.关键计算

M.data[1..M.tu]中的每个元素(i,k,M(i,k)(1<=i <=m1,1<=k<=n1),找到N.data中所有对应的元素(k,j,N(k,j)) (1<=i<=m2,1<=k<=n2),相乘即可。为此在N.data中找到第k行所有元素。

            //为此通过行逻辑链接在N.data中找到第k行所有元素的上下界

2.程序的框架

一般算法:一行与一列相乘。

稀疏矩阵乘法:

          定位:矩阵M4arow4元素p

                        4             

                                           N的一行:q      

                                                                          

5
                                                       

                图 矩阵乘法数据的定位图

    (1)矩阵M到一行到一个元素与一行到一个矩阵N

    (2)M矩阵数据处理的定位与驱动元素M.data[p]数据映射的范

围:对应M.data[p].j=browN的第brow行。

    (3)输出结构:设置中间存储数组ctemp[],工作游标ccol

    ccol= N.data[q].j

3.算法主序与算法线索

       Q的行序为增长主序。按Q的一行处理。M的行arow,N的行brow。增长序是Q的第arow行,每一个Q行都保存在ctemp中,因此输出循环在arow循环中。

       M的第arow行与矩阵N相乘得到ctempQ的第arow行元素。矩阵N按行与Marow行中的一个元素相乘,是整个矩阵的相乘,因此得到Q的一行。行内增长序是ctemp的增长序。

3.稀疏矩阵乘法程序详细分析

Status MultSMatuix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q){

  

  if(M.nu!=N.mu)  return ERROR;   //列数,行数不同,矩阵乘法非法

  Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;    //Q形的初始化。Q的行数等于M

                                               的行数,Q的列数等于T的列数

  if(M.tu*N.tu!=0){                            //MN不是0矩阵

  for(arow=1;arow<=M.mu;++arow){            //选择M的一行

      ctemp[]=0;                  //当前行各元素累加器清0

                                           []不表示数组长度为1,但

                                       数组长度一般不等于

                                            num[col]ctemp[]的长度=

                                    矩阵N.nu,工作游标

                                            ccol<=N.nu.

    Q.rpos[arow]=Q.tu+1;         //每一个Q.rpos[arow]赋相同

                                        的初值Q.tu+1

    if(arrow<M.mu)  tp=M.rpos[arrow+1];  

        else tp=M.tu+1;        //定位驱动元素M.data[p]的范围。

                                     M每一行在M.data[] 中元素范围

                                     [M.rpos[arrow], M.rpos[arrow+1]],         

                          但是最后一行的范围[M.rpos[arrow]M.tu+1],

                                    M.tutu不同,不是转置运算

     for(p=M.rpos[arow];p<tp;++p){      //遍历M的一行元素,

                                                             [M.rpos[arow]tp]

                                                   驱动元素M.data[p]

         brow=M.data[p].j;             //pq的映射关系:

                                                    p对应元素的列值j,则pN

                                           的第brow行元素对应,

                                            第brow行工作游标q.

         if(brow<N.mu)  t=N.rpos[brow+1];       

                                  //q的范围[N.rpos[brow]{N.rpos[brow+1]N.tu+1}]

         else  t=N.tu+1;

         for(q=N.rpos[brow];q<t;++q){

                                              // M.data[p]的列下标j,与N的第j

                                            元素相乘,将值存储在ctem[]中,

                                        变量ccol=N.data[q].jctemp[ccol]

                                                M的第arow行第M.data[p].j=brow

                                        与N的第brow行第N.data[q].j列元素

                                       相乘的结果。M的这一arow行元素

                                        应与N.data[q].j列相乘得到结果

                                       Q(arow, N.data[q].jq). ctemp[ccol]

                                             只是Q(arow, N.data[q].j)的一个部分值,

                                     应是Q(arow, N.data[q].j)的第arow个部分值。

               ccol=N.data[q].j;    //按行顺序取值,所以M的第arow

                                     也是Q的第arow行。Q的这一行有

                                    Q.nu个元素,并不是每一个ctemp[ccol]都能计算到。

               ctemp[ccol]+=M.data[p].e*N.data[q].e

                                                 // ctemp[ccol]q,p

                                         关系。但不是三元组

                                         的行列下标。p,q

                                                   M,N当前行的工作游标。

          }//for q

                                  //每次M.data[p].e行相乘(NM.data[p].j=brow)得到部分结果

      }//for p, 每次得到Q的第arow行元素

      for(ccol=1;ccol<=Q.nu;++ccol)

           if(ctemp[ccol]){      //ccol以最后一次的对应为

                                     值,不一定是Q.nu

               if(++Q.tu>MAXSIZE)  return ERROR;

               Q.data[Q.tu]=(arow,ccol,ctemp[ccol]);//将非0

                                                      转换到Q.data[]中,

                                                       Q.data[]是递增序。

                                                          Q.tu是下标,注意不是Q.nu.

            }//if

       }//for ccol        //ctemp转换一行到Q.data[]

  }//for  arrow          //Marow 行与矩阵N相乘得到Q

                          的第arow行。Marow中的一个元

                          素M.data[p]N的一行

                                 M.data[p].j=brow相乘。

 }//if

 Return    OK;

}//MultSMatrix

3.注意

1)由于时间的缘故,没有进行驱动元素的分析。ctemp与驱动元素的关系,是不是驱动元素。都没有分析。有疏忽请告知。   

2)程序的原子功能没有分析,可从《掌握数据结构---稀疏矩阵的转置程序的详细分析》中了解原子功能的概念。

 

 

分享:
标签: 自然科学 计算机软件 | 收藏
百科的文章(含所附图片)系由网友上传,如果涉嫌侵权,请与客服联系,我们将按照法律之相关规定及时进行处理。如需转载,请注明来源于www.baike.com

本文行家向Ta提问

玻尔特.李软件专业硕士生,编程,计算机硬件设计,网络。

行家更新