论文部分内容阅读
摘要：在《数据结构》课程中，三元组稀疏矩阵的转置算法通常会作为难点来讲解。通过介绍一般数组的矩阵转置的算法以及稀疏矩阵、稀疏矩阵的三元组表示，引出稀疏矩阵的一般算法。本文介绍的稀疏矩阵的算法是一种用C语言编写的转置算法，并通过对两种算法的涉及到的时间以及空间的复杂度进行分析，突出C语言编写的转置算法的优势。
关键词：稀疏矩阵；三元组；数组算法；一般算法
中图分类号：TP312文献标识码：A文章编号：1007-9599 (2013) 05-0000-02
1前言
矩阵作为数值分析问题的数学对象和科学与工程计算的数据对象，是可以通过计算机语法进行处理的。随着计算机科学技术的不断发展，矩阵在现代化科技的各个领域中应用也越来越广泛。矩阵的基本运算之一便是矩阵转置，实际应用时，常常可以采用不同的实现矩阵转置的方法来应对不同的存储方法。
矩阵转置的定义：将m行n列矩阵 转换为n行m列的 矩阵，矩阵转后， 矩阵的第i行行元素与 矩阵对应的第i列列元素相同。
2数组的三元组表示与稀疏矩阵
在实际的科学运算中，往往会遇到一种常见矩阵，其中大部分元素值为0，且没有一定的分布规律，在这种情况下，把矩阵定义为零元素个数远远大于非零元素的个数的稀疏矩阵。如图1给出一个稀疏矩阵和他的转置矩阵。
图1稀疏矩阵及其转置矩阵
从图1中我们可以发现，L矩阵中只有8个非零元素，以此，我们可以对L矩阵的其他零元素进行存储压缩，以节省空间。需要被存储的零元素要同时存储其所在行与列的值。对于非零元素，可以采用三元组来唯一确定。三元组的一般表示方法为（i，j，aij），其中i为非零元素所在行，j为非零元素所在列。图2-1中的L矩阵就可用三元组表示为：{（1，1，1），（1，3，2），（2，2，3），（3，4，8），（3，6，3），（4，1，8），（4，3，2），（5，4，1）}。i和j可确定一个非零元素在矩阵中的具体位置，再加上第三个非零元素的值就可唯一确定所有非零元素的值。如（1，1，1）中第三个数字1就表示L矩阵中第一个行第一列的非零元素为1。
稀疏矩阵有多种压缩存储方法，对应的三元组表也同时存在不同的组织方法。一般情况下，可采用顺序存储结构来表示三元组表，根据对应的非零元素在稀疏矩阵中的位置，按照行优先的顺序存放，进而用三元组来表示稀疏矩阵，这种表示方法就是三元组表示法。这种表示方法可有效减少存储空间，且矩阵越稀疏，这种优势越明显。
3稀疏矩阵的转置算法及其分析
3.1一般矩阵的数组算法
一般矩阵数组算法的设计思想
一般矩阵数组算法首先要建立两个二位空数组，第一个数组为一般矩阵，第二个数组为一般矩阵的转置矩阵。先将第一个空数组赋值，形成一个一般矩阵，然后把一般矩阵数组的元素按照转置矩阵定义将对应的元素赋值给第二个空数组成为一般数组的转置矩阵。例如三维矩阵首先通过调用一个自定义函数通过双重for循环语句对3行3列的空数组进行赋值。输出矩阵则可通过双重for循环语句对一般数组进行输出。下面就是对一般矩阵进行转置，采用一个临时变量temp进行一般矩阵和转置矩阵对应元素之间的变换。
temp=b[i][j]；
b[i][j]=b[j][i]；
b[j][i]=temp；
这种用二位数组进行矩阵转置的算法的时间复杂度与空间复杂度都不太理想。
3.2稀疏矩阵的转置算法
（1）算法设计思想。稀疏矩阵的转置实际上就是将稀疏矩阵的（i，j）位置上的元素变换到（j，i）位置上。根據所学的线性代数知识，一个m*n的矩阵L转置后，就变成一个新的n*m的矩阵H，并且有L（i，j）=H（j，i），得到的矩阵H同样是一个稀疏矩阵。稀疏矩阵的转置要考虑到零元素与非零元素的个数两方面。注意要将稀疏矩阵L的非零元素交换到转置矩阵H的三元组表中对应的正确位置。实际算法中可设置两个数组A[]和B[]，数组A[]用来存放稀疏矩阵L的非零元素的个数，而数组B[]则用来存放稀疏矩阵L中第i列第一个非零元素在转置矩阵H的三元组表中的正确位置。如此一来，计算数组A[i]可通过对已经定义的稀疏矩阵L进行一遍循环扫描，并对其列号为i的元素的对应的A[i]加1，计算B[i]可通过以下公式递推：
得到数组A[]和数组B[]的对应值后，可把稀疏矩阵L中的三元组直接放到转置矩阵H中三元组表的正确位置上，一般情况下可利用数组B[]来实现此步骤：将数组B[i]的初值作为稀疏矩阵L中第i列的第一个非零元素三元组在转置矩阵H中相对应的正确位置，若稀疏矩阵L中的第i列有一个元素需要加入到转置矩阵的三元组表时，对应的B[i]的值也要加1，以达到B[i]中的元素始终指向稀疏矩阵L三元组表第i列中下一个非零元素在转置矩阵H三元组表的正确位置。
（2）稀疏矩阵转置的一般算法。用c语言对上述方法构造算法可通过建立四组循环。四组循环时分别循环了L[0].p、L[0].q、L[0].p-1以及L[0].q次，其中的L[0].q就是上述方法所说的稀疏矩阵L中的非零元素的个数，可假设为n。这种稀疏矩阵转置算法的的平均时间复杂度为T=O（j+n）。这种算法的时间复杂度会随着n的增大而接近T=O（i*j），也就是经典的双重循环的转置算法。但是这种算法的空间复杂度因引入了辅助向量，导致空间复杂度为S=O（2*j），所以存储空间并没有减少，可对其进行进一步的优化。
（3）一般算法的改进。改进算法在对数组B[i]统计的稀疏矩阵的各列的非零元素设置为0后再重新统计，改进算法可增添两个变量a、b记录并计算数组B[]中元素值，并作为稀疏矩阵L的第i列中的第一个非零元素在转置矩阵H中对应的位置：首先，将1赋值给B[1]，其次，用变量a用来暂存第i-1列的非零元素个数，变量b用来暂存第i列的非零元素个数。重复第二步求得全部B[]的值。接下来的步骤就同一般转置方法相同：若稀疏矩阵L中的第i列有一个元素需要加入到转置矩阵的三元组表时，对应的B[i]的值也要加1，以达到B[i]中的元素始终指向稀疏矩阵L三元组表第i列中下一个非零元素在转置矩阵H三元组表的正确位置。
改进方案算法的平均时间复杂度不变，，空间上却可减少一个辅助向量，由原来的 变为 。在不增加时间复杂度的情况下达到了降低空间复杂度的目的，实现了对一般转置算法的优化。
参考文献：
[1]王敏,Wang Min.稀疏矩阵快速转置算法的分析与优化[J].计算机应用与软件,2010,27(8):89-90.
[2]祝伟华,付先珺,ZHU Wei-Hua,FU Xian-Jun.支持OpenCL的GPU加速人工神经网络训练[J].计算机系统应用,2011,20(7):23-24.
[3]王敏.基于压缩存储的稀疏矩阵转置算法研究[J].科学技术与工程,2010,10(4):34-35.
关键词：稀疏矩阵；三元组；数组算法；一般算法
中图分类号：TP312文献标识码：A文章编号：1007-9599 (2013) 05-0000-02
1前言
矩阵作为数值分析问题的数学对象和科学与工程计算的数据对象，是可以通过计算机语法进行处理的。随着计算机科学技术的不断发展，矩阵在现代化科技的各个领域中应用也越来越广泛。矩阵的基本运算之一便是矩阵转置，实际应用时，常常可以采用不同的实现矩阵转置的方法来应对不同的存储方法。
矩阵转置的定义：将m行n列矩阵 转换为n行m列的 矩阵，矩阵转后， 矩阵的第i行行元素与 矩阵对应的第i列列元素相同。
2数组的三元组表示与稀疏矩阵
在实际的科学运算中，往往会遇到一种常见矩阵，其中大部分元素值为0，且没有一定的分布规律，在这种情况下，把矩阵定义为零元素个数远远大于非零元素的个数的稀疏矩阵。如图1给出一个稀疏矩阵和他的转置矩阵。
图1稀疏矩阵及其转置矩阵
从图1中我们可以发现，L矩阵中只有8个非零元素，以此，我们可以对L矩阵的其他零元素进行存储压缩，以节省空间。需要被存储的零元素要同时存储其所在行与列的值。对于非零元素，可以采用三元组来唯一确定。三元组的一般表示方法为（i，j，aij），其中i为非零元素所在行，j为非零元素所在列。图2-1中的L矩阵就可用三元组表示为：{（1，1，1），（1，3，2），（2，2，3），（3，4，8），（3，6，3），（4，1，8），（4，3，2），（5，4，1）}。i和j可确定一个非零元素在矩阵中的具体位置，再加上第三个非零元素的值就可唯一确定所有非零元素的值。如（1，1，1）中第三个数字1就表示L矩阵中第一个行第一列的非零元素为1。
稀疏矩阵有多种压缩存储方法，对应的三元组表也同时存在不同的组织方法。一般情况下，可采用顺序存储结构来表示三元组表，根据对应的非零元素在稀疏矩阵中的位置，按照行优先的顺序存放，进而用三元组来表示稀疏矩阵，这种表示方法就是三元组表示法。这种表示方法可有效减少存储空间，且矩阵越稀疏，这种优势越明显。
3稀疏矩阵的转置算法及其分析
3.1一般矩阵的数组算法
一般矩阵数组算法的设计思想
一般矩阵数组算法首先要建立两个二位空数组，第一个数组为一般矩阵，第二个数组为一般矩阵的转置矩阵。先将第一个空数组赋值，形成一个一般矩阵，然后把一般矩阵数组的元素按照转置矩阵定义将对应的元素赋值给第二个空数组成为一般数组的转置矩阵。例如三维矩阵首先通过调用一个自定义函数通过双重for循环语句对3行3列的空数组进行赋值。输出矩阵则可通过双重for循环语句对一般数组进行输出。下面就是对一般矩阵进行转置，采用一个临时变量temp进行一般矩阵和转置矩阵对应元素之间的变换。
temp=b[i][j]；
b[i][j]=b[j][i]；
b[j][i]=temp；
这种用二位数组进行矩阵转置的算法的时间复杂度与空间复杂度都不太理想。
3.2稀疏矩阵的转置算法
（1）算法设计思想。稀疏矩阵的转置实际上就是将稀疏矩阵的（i，j）位置上的元素变换到（j，i）位置上。根據所学的线性代数知识，一个m*n的矩阵L转置后，就变成一个新的n*m的矩阵H，并且有L（i，j）=H（j，i），得到的矩阵H同样是一个稀疏矩阵。稀疏矩阵的转置要考虑到零元素与非零元素的个数两方面。注意要将稀疏矩阵L的非零元素交换到转置矩阵H的三元组表中对应的正确位置。实际算法中可设置两个数组A[]和B[]，数组A[]用来存放稀疏矩阵L的非零元素的个数，而数组B[]则用来存放稀疏矩阵L中第i列第一个非零元素在转置矩阵H的三元组表中的正确位置。如此一来，计算数组A[i]可通过对已经定义的稀疏矩阵L进行一遍循环扫描，并对其列号为i的元素的对应的A[i]加1，计算B[i]可通过以下公式递推：
得到数组A[]和数组B[]的对应值后，可把稀疏矩阵L中的三元组直接放到转置矩阵H中三元组表的正确位置上，一般情况下可利用数组B[]来实现此步骤：将数组B[i]的初值作为稀疏矩阵L中第i列的第一个非零元素三元组在转置矩阵H中相对应的正确位置，若稀疏矩阵L中的第i列有一个元素需要加入到转置矩阵的三元组表时，对应的B[i]的值也要加1，以达到B[i]中的元素始终指向稀疏矩阵L三元组表第i列中下一个非零元素在转置矩阵H三元组表的正确位置。
（2）稀疏矩阵转置的一般算法。用c语言对上述方法构造算法可通过建立四组循环。四组循环时分别循环了L[0].p、L[0].q、L[0].p-1以及L[0].q次，其中的L[0].q就是上述方法所说的稀疏矩阵L中的非零元素的个数，可假设为n。这种稀疏矩阵转置算法的的平均时间复杂度为T=O（j+n）。这种算法的时间复杂度会随着n的增大而接近T=O（i*j），也就是经典的双重循环的转置算法。但是这种算法的空间复杂度因引入了辅助向量，导致空间复杂度为S=O（2*j），所以存储空间并没有减少，可对其进行进一步的优化。
（3）一般算法的改进。改进算法在对数组B[i]统计的稀疏矩阵的各列的非零元素设置为0后再重新统计，改进算法可增添两个变量a、b记录并计算数组B[]中元素值，并作为稀疏矩阵L的第i列中的第一个非零元素在转置矩阵H中对应的位置：首先，将1赋值给B[1]，其次，用变量a用来暂存第i-1列的非零元素个数，变量b用来暂存第i列的非零元素个数。重复第二步求得全部B[]的值。接下来的步骤就同一般转置方法相同：若稀疏矩阵L中的第i列有一个元素需要加入到转置矩阵的三元组表时，对应的B[i]的值也要加1，以达到B[i]中的元素始终指向稀疏矩阵L三元组表第i列中下一个非零元素在转置矩阵H三元组表的正确位置。
改进方案算法的平均时间复杂度不变，，空间上却可减少一个辅助向量，由原来的 变为 。在不增加时间复杂度的情况下达到了降低空间复杂度的目的，实现了对一般转置算法的优化。
参考文献：
[1]王敏,Wang Min.稀疏矩阵快速转置算法的分析与优化[J].计算机应用与软件,2010,27(8):89-90.
[2]祝伟华,付先珺,ZHU Wei-Hua,FU Xian-Jun.支持OpenCL的GPU加速人工神经网络训练[J].计算机系统应用,2011,20(7):23-24.
[3]王敏.基于压缩存储的稀疏矩阵转置算法研究[J].科学技术与工程,2010,10(4):34-35.