基于三元组表表示的稀疏矩阵的快速转置算法及其改进

Improvement on Fast Transposition Algorithm to Sparse Matrix Expressed by Triple List

介绍基于三元组表表示的稀疏矩阵的快速转置算法,此算法在转置前需要先确定原矩阵中各列第一个非零元在转置矩阵中的位置,在此使用2个数组作为辅助空间,为了减少算法所需的辅助空间,通过引入2个简单变量提出一种改进算法。该改进算法在时间复杂度保持不变的情况下,空间复杂度比原算法节省一半。

The fast transposition algorithm to sparse matrix expressed by triple list is introduced. This algorithm needs to determine the position in the transposed matrix position of the first element which is not equal to zero in the original matrix each row,it uses two arrays as auxiliary space. In order to reduce the auxiliary space which the algorithm needed,an improvement is made through introducing two simple variables. The improved algorithm saves a half auxiliary space compared to the original algorithm at the same time complexity.