基于三元组表表示的稀疏矩阵的快速转置算法及其改进
摘 要:介绍基于三元组表表示的稀疏矩阵的快速转置算法,此算法在转置前需要先确定原矩阵中各列第一个非零元在转置矩阵中的位置,在此使用2个数组作为辅助空间,为了减少算法所需的辅助空间,通过引入2个简单变量提出一种改进算法。该改进算法在时间复杂度保持不变的情况下,空间复杂度比原算法节省一半。
需求分析： 矩阵作为许多科学与工程计算的数据对象,必然是计算机处理的数据对象之
一。在实际应用中,常会遇到一些阶数很高,同时又有许多值相同的元素或零元素的矩阵,在这类矩阵中,如果值相同的元素或零元素在矩阵中的分配没有规律,则称之为稀疏矩阵。为了节省存储空间,常对稀疏矩阵进行压缩存储。压缩存储的基本思想就是:对多个值相同的元素只分配1个存储空间,对零元素不分配存储空间。换句话说,就是只存储稀疏矩阵中的非零元素。 稀疏矩阵可以采取不同的压缩存储方法,对于不同的压缩存储方法,矩阵运算的实现也就不同。
1．稀疏矩阵的三元组表表示法
根据压缩存储的基本思想,这里只存储稀疏矩阵中的非零元素,因此,除了存储非零元的值以外,还必须同时记下它所在行和列的位置(i,j),即矩阵中的1个非零元aij由1个三元组(i,j,aij)惟一确定。由此可知,稀疏矩阵可由表示非零元的三元组表及其行列数惟一确定。对于稀疏矩阵的三元组表采取不同的组织方法即可得到稀疏矩阵的不同压缩存储方法,用三元组数组 (三元组顺序表)来表示稀疏矩阵即为稀疏矩阵的三元组表表示法。三元组数组中的元素按照三元组对应的矩阵元素在原矩阵中的位置,以行优先的顺序依次存放。
三元组表的类型说明如下:
# define MAXSIZE 1000 /*非零元素的个数最多为
1000*/
typedef struct
{
int row,col; /*该非零元素的行下标和列下标*/
ElementType e; /*该非零元素的值*/
}Triple;
typedef struct
{
Triple data[MAXSIZE+1]; /*非零元素的三元组表,
data[0]未用*/
int m,n,len; /*矩阵的行数、列数和非零元素的个数*/
}TSMatrix;
2． 稀疏矩阵的快速转置算法
待转置矩阵source和转置后矩阵dest分别用三元组表A和B表示,依次按三元组表A中三元组的次序进行转置,转置后直接放到三元组表B的正确位置上。这种转置算法称为快速转置算法。为了能将待转置三元组表A中元素一次定位到三元组表B的正确位置上,需要预先计算以下数据:
1) 待转置矩阵source每一列中非零元素的个数(即转置后矩阵dest每一行中非零元素的个
数)。
2) 待转置矩阵source每一列中第一个非零元素在三元组表B中的正确位置(即转置后矩阵
dest每一行中第一个非零元素在三元组表B中的正确位置)。
为此,需要设2个数组num[]和position[],其中num[col]用来存放矩阵source中第col列中非零元素个数(转置后矩阵dest中第col行非零元素的个数);position[col]用来存放转置矩阵source中第col列(转置后矩阵dest中第col行)中第一个非零元素在三元组表B中的正确位置。
num[col]的计算方法:将三元组表A扫描一遍,对于其中列号为k的元素,给相应的num[k]加1。
position[col]的计算方法:
position[1]=1
position[col]=position[col-1]+num[col-1]
(其中2[col[A.n)
将三元组表A中所有的非零元素直接放到三元组表B中正确位置上的方法是:position[col]的初值为三元组表A中列号为col(三元组表B的行号为col)的第1个非零元素的正确位置,当三元组表A中列号为col的1个元素加入到三元组表B时,则position[col]=position[col]+1,即:使position[col]始终指向三元组表A中列号为col的下一个非零元素在三元组表B 中的正确位置。
稀疏矩阵的快速转置算法如下:
(1)初始化num[ ]数组;
(2)求num[ ]数组各元素的值;
(3)求position[ ]数组各元素的值;
(4)将三元组表A中所有的非零元素直接放到三元组表B中正确位置上。
快速转置算法的时间主要耗费在4个并列的单循环上,这4个并列的单循环分别执行了
于经典算法的时间复杂度O(A.m*A.n)。
快速转置算法在空间耗费上除三元组表所占用的空间外,还需2个辅助向量空间,即num[1..A.n],position[1..A.n]。可见,算法在时间上的节省,是以更多的存储空间为代价的。 可见,稀疏矩阵的三元组表表示法虽然节约了存储空间,但比起矩阵的正常存储方式来讲,其实现相同操作要耗费较多的时间,同时也增加了算法的难度,即以
耗费更多时间为代价来换取空间的节省。
3. 稀疏矩阵的快速转置算法的改进
在稀疏矩阵的快速转置算法中引入2个辅助向量空间num[]和position[],在下面的改进算法中只保留num[],另外引入2个变量k1和k2。num[col]起初用来存放矩阵source中第col列中非零元素个数(转置后矩阵dest中第col行非零元素的个数),然后通过修改num[col]中各元素的值,用num[col]存放转置矩阵source中第col列(转置后矩阵dest中第col行)中第一个非零元素在三元组表B中的正确位置。修改num[col]中各元素的值的操作实现如下:
(1)令k1=num[1];num[1]=1;
(2)对于col=2,A.n依次做:
k2= num[col]
num[col]=k1+num[col-1];
k1=k2;
在转置过程中,当三元组表A中列号为col的1个元素加入到三元组表B时,则num[col]=num[col]+1,即:使num[col]始终指向三元组表A中列号为col的下一个非零元素在
三元组表B中的正确位置。
改进的快速转置算法如下:初始化num[ ]数组;求num[ ]数组各元素的值;修改num[ ]数组各元素的值;将三元组表A中所有的非零元素直接放到三元组表B中正确位置上。
显然,上述改进算法的时间复杂度与原算法相同,在空间复杂度上除了三元组表所占用的空间外,只需要1个辅助向量空间num[1..A.n]和2个简单变量,而算法的空间复杂度仅考虑算法所需的辅助空间,因此,改进算法的空间复杂度比原算法节约一半。
基于三元组表表示的稀疏矩阵的快速转置算法及其改进
摘 要:介绍基于三元组表表示的稀疏矩阵的快速转置算法,此算法在转置前需要先确定原矩阵中各列第一个非零元在转置矩阵中的位置,在此使用2个数组作为辅助空间,为了减少算法所需的辅助空间,通过引入2个简单变量提出一种改进算法。该改进算法在时间复杂度保持不变的情况下,空间复杂度比原算法节省一半。
需求分析： 矩阵作为许多科学与工程计算的数据对象,必然是计算机处理的数据对象之
一。在实际应用中,常会遇到一些阶数很高,同时又有许多值相同的元素或零元素的矩阵,在这类矩阵中,如果值相同的元素或零元素在矩阵中的分配没有规律,则称之为稀疏矩阵。为了节省存储空间,常对稀疏矩阵进行压缩存储。压缩存储的基本思想就是:对多个值相同的元素只分配1个存储空间,对零元素不分配存储空间。换句话说,就是只存储稀疏矩阵中的非零元素。 稀疏矩阵可以采取不同的压缩存储方法,对于不同的压缩存储方法,矩阵运算的实现也就不同。
1．稀疏矩阵的三元组表表示法
根据压缩存储的基本思想,这里只存储稀疏矩阵中的非零元素,因此,除了存储非零元的值以外,还必须同时记下它所在行和列的位置(i,j),即矩阵中的1个非零元aij由1个三元组(i,j,aij)惟一确定。由此可知,稀疏矩阵可由表示非零元的三元组表及其行列数惟一确定。对于稀疏矩阵的三元组表采取不同的组织方法即可得到稀疏矩阵的不同压缩存储方法,用三元组数组 (三元组顺序表)来表示稀疏矩阵即为稀疏矩阵的三元组表表示法。三元组数组中的元素按照三元组对应的矩阵元素在原矩阵中的位置,以行优先的顺序依次存放。
三元组表的类型说明如下:
# define MAXSIZE 1000 /*非零元素的个数最多为
1000*/
typedef struct
{
int row,col; /*该非零元素的行下标和列下标*/
ElementType e; /*该非零元素的值*/
}Triple;
typedef struct
{
Triple data[MAXSIZE+1]; /*非零元素的三元组表,
data[0]未用*/
int m,n,len; /*矩阵的行数、列数和非零元素的个数*/
}TSMatrix;
2． 稀疏矩阵的快速转置算法
待转置矩阵source和转置后矩阵dest分别用三元组表A和B表示,依次按三元组表A中三元组的次序进行转置,转置后直接放到三元组表B的正确位置上。这种转置算法称为快速转置算法。为了能将待转置三元组表A中元素一次定位到三元组表B的正确位置上,需要预先计算以下数据:
1) 待转置矩阵source每一列中非零元素的个数(即转置后矩阵dest每一行中非零元素的个
数)。
2) 待转置矩阵source每一列中第一个非零元素在三元组表B中的正确位置(即转置后矩阵
dest每一行中第一个非零元素在三元组表B中的正确位置)。
为此,需要设2个数组num[]和position[],其中num[col]用来存放矩阵source中第col列中非零元素个数(转置后矩阵dest中第col行非零元素的个数);position[col]用来存放转置矩阵source中第col列(转置后矩阵dest中第col行)中第一个非零元素在三元组表B中的正确位置。
num[col]的计算方法:将三元组表A扫描一遍,对于其中列号为k的元素,给相应的num[k]加1。
position[col]的计算方法:
position[1]=1
position[col]=position[col-1]+num[col-1]
(其中2[col[A.n)
将三元组表A中所有的非零元素直接放到三元组表B中正确位置上的方法是:position[col]的初值为三元组表A中列号为col(三元组表B的行号为col)的第1个非零元素的正确位置,当三元组表A中列号为col的1个元素加入到三元组表B时,则position[col]=position[col]+1,即:使position[col]始终指向三元组表A中列号为col的下一个非零元素在三元组表B 中的正确位置。
稀疏矩阵的快速转置算法如下:
(1)初始化num[ ]数组;
(2)求num[ ]数组各元素的值;
(3)求position[ ]数组各元素的值;
(4)将三元组表A中所有的非零元素直接放到三元组表B中正确位置上。
快速转置算法的时间主要耗费在4个并列的单循环上,这4个并列的单循环分别执行了
于经典算法的时间复杂度O(A.m*A.n)。
快速转置算法在空间耗费上除三元组表所占用的空间外,还需2个辅助向量空间,即num[1..A.n],position[1..A.n]。可见,算法在时间上的节省,是以更多的存储空间为代价的。 可见,稀疏矩阵的三元组表表示法虽然节约了存储空间,但比起矩阵的正常存储方式来讲,其实现相同操作要耗费较多的时间,同时也增加了算法的难度,即以
耗费更多时间为代价来换取空间的节省。
3. 稀疏矩阵的快速转置算法的改进
在稀疏矩阵的快速转置算法中引入2个辅助向量空间num[]和position[],在下面的改进算法中只保留num[],另外引入2个变量k1和k2。num[col]起初用来存放矩阵source中第col列中非零元素个数(转置后矩阵dest中第col行非零元素的个数),然后通过修改num[col]中各元素的值,用num[col]存放转置矩阵source中第col列(转置后矩阵dest中第col行)中第一个非零元素在三元组表B中的正确位置。修改num[col]中各元素的值的操作实现如下:
(1)令k1=num[1];num[1]=1;
(2)对于col=2,A.n依次做:
k2= num[col]
num[col]=k1+num[col-1];
k1=k2;
在转置过程中,当三元组表A中列号为col的1个元素加入到三元组表B时,则num[col]=num[col]+1,即:使num[col]始终指向三元组表A中列号为col的下一个非零元素在
三元组表B中的正确位置。
改进的快速转置算法如下:初始化num[ ]数组;求num[ ]数组各元素的值;修改num[ ]数组各元素的值;将三元组表A中所有的非零元素直接放到三元组表B中正确位置上。
显然,上述改进算法的时间复杂度与原算法相同,在空间复杂度上除了三元组表所占用的空间外,只需要1个辅助向量空间num[1..A.n]和2个简单变量,而算法的空间复杂度仅考虑算法所需的辅助空间,因此,改进算法的空间复杂度比原算法节约一半。