基于三元組表表示的稀疏矩陣的快速轉置算法及其改進

摘 要：介紹基于三元組表表示的稀疏矩陣的快速轉置算法，此算法在轉置前需要先確定原矩陣中各列第一個非零元在轉置矩陣中的位置，在此使用2個數(shù)組作為輔助空間，為了減少算法所需的輔助空間，通過引入2個簡單變量提出一種改進算法。該改進算法在時間復雜度保持不變的情況下，空間復雜度比原算法節(jié)省一半。

關鍵詞：稀疏矩陣；壓縮存儲；三元組表；快速轉置；時間復雜度；空間復雜度

中圖分類號：TP311.12文獻標識碼：B

文章編號：1004-373X(2008)22-078-02

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

WANG Rong1，2

(1.Xidian University，Xi′an，710071，China;2.Weinan Teachers University，Weinan，714000，China)

Abstract：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.

Keywords：sparse matrix;compression memory；triple list;fast transposition;time complexity;space complexity

矩陣作為許多科學與工程計算的數(shù)據(jù)對象，必然是計算機處理的數(shù)據(jù)對象之一。在實際應用中，常會遇到一些階數(shù)很高，同時又有許多值相同的元素或零元素的矩陣，在這類矩陣中，如果值相同的元素或零元素在矩陣中的分配沒有規(guī)律，則稱之為稀疏矩陣。

為了節(jié)省存儲空間，常對稀疏矩陣進行壓縮存儲。壓縮存儲的基本思想就是：對多個值相同的元素只分配1個存儲空間，對零元素不分配存儲空間。換句話說，就是只存儲稀疏矩陣中的非零元素。

稀疏矩陣可以采取不同的壓縮存儲方法，對于不同的壓縮存儲方法，矩陣運算的實現(xiàn)也就不同。

1稀疏矩陣的三元組表表示法

根據(jù)壓縮存儲的基本思想，這里只存儲稀疏矩陣中的非零元素，因此，除了存儲非零元的值以外，還必須同時記下它所在行和列的位置(i，j)，即矩陣中的1個非零元a_ij由1個三元組(i，j，a_ij)惟一確定。由此可知，稀疏矩陣可由表示非零元的三元組表及其行列數(shù)惟一確定。

對于稀疏矩陣的三元組表采取不同的組織方法即可得到稀疏矩陣的不同壓縮存儲方法，用三元組數(shù)組（三元組順序表）來表示稀疏矩陣即為稀疏矩陣的三元組表表示法。三元組數(shù)組中的元素按照三元組對應的矩陣元素在原矩陣中的位置，以行優(yōu)先的順序依次存放。

三元組表的類型說明如下：

＃define MAXSIZE 1000/*非零元素的個數(shù)最多為1000*/

typedef struct

{

introw，col; /*該非零元素的行下標和列下標*/

ElementType e；/*該非零元素的值*/

}Triple;

typedef struct

{

Tripledata［MAXSIZE+1］;/* 非零元素的三元組表，data［0］未用*/

int m，n，len;/*矩陣的行數(shù)、 列數(shù)和非零元素的個數(shù)*/

}TSMatrix；

2 稀疏矩陣的快速轉置算法

待轉置矩陣source和轉置后矩陣dest分別用三元組表A和B表示，依次按三元組表A中三元組的次序進行轉置，轉置后直接放到三元組表B的正確位置上。這種轉置算法稱為快速轉置算法。

為了能將待轉置三元組表A中元素一次定位到三元組表B的正確位置上，需要預先計算以下數(shù)據(jù)：

(1)待轉置矩陣source每一列中非零元素的個數(shù)（即轉置后矩陣dest每一行中非零元素的個數(shù)）。

(2)待轉置矩陣source每一列中第一個非零元素在三元組表B中的正確位置（即轉置后矩陣dest每一行中第一個非零元素在三元組表B中的正確位置)。

為此，需要設2個數(shù)組num［］和position［］，其中num［col］用來存放矩陣source中第col列中非零元素個數(shù)（轉置后矩陣dest中第col行非零元素的個數(shù)）；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［ ］數(shù)組；

(2)求num［ ］數(shù)組各元素的值；

(3)求position［ ］數(shù)組各元素的值；

(4)將三元組表A中所有的非零元素直接放到三元組表B中正確位置上。

快速轉置算法的時間主要耗費在4個并列的單循環(huán)上，這4個并列的單循環(huán)分別執(zhí)行了A.n，A.len，A.n-1，A.len次，因而總的時間復雜度為O(A.n)+O(A.len)+O(A.n)+O(A.len)，即為O（A.n+A.len）。當待轉置矩陣source中非零元素個數(shù)接近于A.m×A.n時，其時間復雜度接近于經(jīng)典算法的時間復雜度O(A.m×A.n)。

快速轉置算法在空間耗費上除三元組表所占用的空間外，還需2個輔助向量空間，即num［1..A.n］，position［1..A.n］。可見，算法在時間上的節(jié)省，是以更多的存儲空間為代價的。

可見，稀疏矩陣的三元組表表示法雖然節(jié)約了存儲空間， 但比起矩陣的正常存儲方式來講，其實現(xiàn)相同操作要耗費較多的時間，同時也增加了算法的難度，即以耗費更多時間為代價來換取空間的節(jié)省。

3 稀疏矩陣的快速轉置算法的改進

在稀疏矩陣的快速轉置算法中引入2個輔助向量空間num［］和position［］，在下面的改進算法中只保留num［］，另外引入2個變量k1和k2。num［col］起初用來存放矩陣source中第col列中非零元素個數(shù)（轉置后矩陣dest中第col行非零元素的個數(shù)），然后通過修改num［col］中各元素的值，用num［col］ 存放轉置矩陣source中第col列（轉置后矩陣dest中第col行）中第一個非零元素在三元組表B中的正確位置。修改num［col］中各元素的值的操作實現(xiàn)如下：

(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［ ］數(shù)組；求num［ ］數(shù)組各元素的值；修改num［ ］數(shù)組各元素的值；將三元組表A中所有的非零元素直接放到三元組表B中正確位置上。

顯然，上述改進算法的時間復雜度與原算法相同，在空間復雜度上除了三元組表所占用的空間外，只需要1個輔助向量空間num［1..A.n］和2個簡單變量，而算法的空間復雜度僅考慮算法所需的輔助空間，因此，改進算法的空間復雜度比原算法節(jié)約一半。

參考文獻

［1］耿國華.數(shù)據(jù)結構C語言描述［M］.西安：西安電子科技大學出版社，2002.

［2］嚴蔚敏，吳偉民.數(shù)據(jù)結構（C語言版）［M］.北京：清華大學出版社，1997.

［3］殷人昆，陶永雷，謝若陽，等.數(shù)據(jù)結構(用面向對象方法與C++描述).北京：清華大學出版社，1999.

［4］ 朱戰(zhàn)立.數(shù)據(jù)結構使用C++語言.西安：西安電子科技大學出版社，2001.

［5］謝應科，張濤，韓承德.實時SAR成像中矩陣轉置的設計與實現(xiàn).計算機研究與發(fā)展，2003，40(1):6-11.

［6］江帆，劉光平，周志敏.多計算機上分布式矩陣轉置.微處理機，2002(2):34-37.

作者簡介 王 榮 女，1972年出生，陜西華陰人，渭南師范學院計算機科學系講師，西安電子科技大學碩士研究生。