程序设计百科

广告

稀疏矩阵快速转置算法3

2012-06-19 10:25:22 本文行家:玻尔特.李

稀疏矩阵的快速转置程序,精确定位的方法。全新的数据结构方法。

 

1善用思考无限美好

二.快速转置程序与精确定位

1.定位函数

目标矩阵:递增序。已知矩阵:矩阵层级结构。

      因此按照目标矩阵的序,就是递增序,从T的行序到M的列序。方法2是按照已知矩阵的序。从MN的对应关系,通过一定的下标计算方法,可知工作游标p,q的对应关系。这个精确计算是一个定位关系,可称为定位函数,使M的元素在T.data[]中建立一个精确定位关系。

定位函数

1)一维数组M.data[]的稀疏矩阵层次结构表示出来,用到辅助存储结构。在三元组表中稀疏矩阵每一行元素有多少个,每一列元素有多少个。2)每一行或每一列第一个非0元素在M.data数组中的位置。3)由矩阵的转置关系,可知M.data[]每一列第一个非0元素在T.data[]中的位置。

稀疏矩阵存储数组与表达式的树结构一样有语义。

定位函数的实现方法。

1)辅助存储结构

num[col],表示矩阵M中,第col列中非0元的个数,等于T.data[]row 行中非0元的个数。

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

 

1
 

       通过求M.data每一列的第一个非0元素的位置,定位T.data[]每一行第一个非0元素的位置。

2)求解:

       for(col=1;col<=M.nu;++col)   num[col]=0;

       for(t=1;t<=M.tu;++t)   ++num[M.data[t].j];  

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

                                                 因此作为另一个数组的下标可以产生有

                               利的应用。可以将列数相同的元素放在同一个数组中。

                                   //获得一个col中的非0元素数目,要遍历整个数组。

                            但在同一个遍历过程中,可实现全部col的非0元数目的计算 

                              这是矩阵元素的相对独立性决定的。

                                       //数组num[col]与一般数组不同,

                                                            num[]的下标表示每一个列,有递增的关系。

          cpot[1]=1;

          for (col=2;col<=M.nu;++col)    cpot[col]=cpot[col-1]+num[col-1]

                            //cpot[col]cpot[col]之间存在计算关系,因为McolTrow,

                       所以cpot[col]=cpot[col-1]+num[col-1],T每一行第一个非0元素在

                            T.data[]中的位置,num[col-1]T.data[]行元素的个数.这些元素

                      是求解目标数组的驱动元素,而在上一个程序中只有一个驱动元素

2.快速转置程序

Status  FastTransposeSMatrix(TSMatrix MTSMatrix &T)

{

     T.mu=M.nu;T.nu=M.nu;T.tu=M.tu;                    

     if(T.tu){                               

     //原子功能1:定位函数

         for(col=1;col<=M.nu;++col)    num[col]=0; 

                                          //MT对应关系,在结构转置中表现

                                    出来。M每一列元素的个数=T每一行元

                                    素的个数。M中每一列第一个非0元素

                                    在数组M.data中的位置,对应T中每一

                                   行第一个非0元素在T.data[]中的位置。

                                       //num[]数组存放每一列非0元个数.使用

                                  数组因为data是一维数组,而且num[]

                                  的下标表示的每一列,有递增关系。

         for(t=1;t<=M.tu;++t)     ++num[M.data[t].j]

                                         //驱动元素是全部列下标,可构成

                                    一个数组。每一个列下标col

                                    数据映射范围是M.data[]数组中

                                    第col列的全部元素。等于T.data[]每一行的元素数目。

                                   驱动元素是一个数组,表示算法主序是多个线索。

                                         //范围定位从矩阵同时到每一列。

        cpot[1]=1;

        for (col=2;col<=M.nu;++col)   

               cpot[col]=cpot[col-1]+num[col-1]  //根据矩阵逻辑结构这几个变量计算相关

       //原子功能2:M-->T,并行p-->q转置

        for(p=1;p<=M.tu;++p){      //M.data的递增序,通过矩阵逻辑结

                                         构辅助数组,使一个方向,变成nu

                                         个方向。相关这nu个方向,所以设

                                          置一个游标qPq间的对应

                                          关系并不是递增关系。

              col=M.data[p].j; q=cpot[col];   //范围定位从矩阵并行到每一

                                                 列。T.data[]M的列分成nu

                                                 个行数组,每个数组的游标

                                                           cpot[col].从三元组可知,p

                                                           M的第col列,到T的第col

                                                 行所在数组,当前元素下标

                                                           cpot[col]。所以当q时,

                                                            T[q]=M[p]

               T.data[q].i=M.data[p].j;        //映射定位,从pq.

               T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;

               ++ cpot[col];           //输出结构,行数组cpot[col]并行递增

                                             // cpot[col]col数组的游标. q每完

                                         成输出元素的一次确定,相应的

                                                 col数组每增长一个元素,

                                                 cpot[col]++。用q代替cpot[1..nu]

                                         中的游标元素。

             }//for                       //快速转置只遍历一次M.data[]

  }//if

  Return Ok;

}//FastTransposeSMatrix

 3.程序分析--算法主序

      一般转置算法,目标矩阵的T.data[]只有一个方向,称为算法线索。快速转置中,T.data[]有多个方向,称为多算法线索。每一个线索是M矩阵的一列。

      矩阵作为一个数学实体结构,有层次和元素顺序两个角度。一般转置算法只用到了矩阵元素的顺序。因此只有一个递增方向。而快速转置算法,用到了矩阵的层次,使目标矩阵每一行都有一个递增的方向,在一次数组遍历中就能实现确定T.data。而每一行的位置和元素个数,是从已知矩阵M中设置的,这是因为MT有对应关系。

      辅助存储结构Num[]cpot[]在存储结构旁边,用来说明矩阵的层次结构。T从辅助存储结构,可知T的矩阵逻辑结构在T.data[]中的反映,这本来是用T的辅助存储结构实现的,但是在转置算法中用M的辅助存储结构就可以知道。因此两个矩阵结构转置的信息可以从M的辅助矩阵中知道,例如每一个逻辑子结构(M的一列,T的一行)元素的个数;M的每一列第一个非0元素的位置,对应T的每一行第一个非0元素在T.data[]中的位置等等。

      在快速转置算法中,使用辅助存储结构,不仅仅知道T.data[]起始元素的驱动作用,还知道T.data[]T矩阵每一行第一个非0元素的驱动作用。由于每一个行的元素个数已知num[col]colM的列),所以T实际上被分成了几个数组,每一个数组都有自己的游标,可以同时递增。然而用一个q可以代表这几个游标,所以可不用游标数组,因为尽管几个行数组是同时增长的,但是for循环每一次只确定一个元素,因此实际上数组的增长是交叉前进的。这与cpu的分时使用是一样的。另外,辅助数组的作用与操作系统文件存储的文件映照类似。

      多算法主序可用“齐头并进”描述,与归并排序的道理一样。因此速度应该比单算法线索快。算法线索在合理的程度上,越多越好。这是衡量程序并行度的一个标准。增加并行算法线索的数量,是提高软件效率的方法之一。

总结:多算法主序表示几个局部并行变成一个整体

4.程序框架

      关键是认识到将稀疏矩阵M数组从整体到nu个列分组,对应到Tnu个行分组。这是矩阵实例逻辑结构之间的对应关系。

5.注意

(1)定位函数

       在快速转置与一般转置中,定位的用法是不一样的。快速转置中,M T有对应关系,使p,q有对应关系,这个对应关系称为转置。用定位函数实现,这个定位称为映射更合适,但是用映射表示定位的很少,所以暂时使用。

      一般转置中,数据处理范围,根据矩阵的结构进行框选,用“截取”能说明一些问题。但是截取并不形象。这方面的理论分析,在论文《程序分析与结构编程》中将进行详细的说明。

(2)输出结构

       输出结构并没有明确。是目标实体的输出结构,还是算法处理数据使用的中间结构,还是输出数据结构的逻辑结构。应进一步阐明。输出方法是中间结构到输出存储结构的转换方法。

(3)快速转置的原子功能结构没有进行详细分析,在论文《程序分析与结构编程》中可见对转置算法的原子功能及程序框架的描述。

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

本文行家向Ta提问

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

行家更新