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

關(guān)鍵詞：稀疏矩陣；壓縮存儲(chǔ)；三元組表；快速轉(zhuǎn)置；時(shí)間復(fù)雜度；空間復(fù)雜度

中圖分類號(hào)：TP311.12文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：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

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

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

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

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

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

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

三元組表的類型說(shuō)明如下：

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

typedef struct

{

introw，col; /*該非零元素的行下標(biāo)和列下標(biāo)*/

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

}Triple;

typedef struct

{

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

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

}TSMatrix；

2 稀疏矩陣的快速轉(zhuǎn)置算法

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

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

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

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

為此，需要設(shè)2個(gè)數(shù)組num［］和position［］，其中num［col］用來(lái)存放矩陣source中第col列中非零元素個(gè)數(shù)（轉(zhuǎn)置后矩陣dest中第col行非零元素的個(gè)數(shù)）；position［col］用來(lái)存放轉(zhuǎn)置矩陣source中第col列（轉(zhuǎn)置后矩陣dest中第col行）中第一個(gè)非零元素在三元組表B中的正確位置。

num［col］的計(jì)算方法：將三元組表A掃描一遍，對(duì)于其中列號(hào)為k的元素，給相應(yīng)的num［k］加1。

position［col］的計(jì)算方法：

position［1］=1

position［col］=position［col-1］+num［col-1］ （其中2≤col≤A.n）

將三元組表A中所有的非零元素直接放到三元組表B中正確位置上的方法是：position［col］的初值為三元組表A中列號(hào)為col（三元組表B的行號(hào)為col）的第1個(gè)非零元素的正確位置，當(dāng)三元組表A中列號(hào)為col的1個(gè)元素加入到三元組表B時(shí)，則position［col］=position［col］+1，即：使position［col］始終指向三元組表A中列號(hào)為col的下一個(gè)非零元素在三元組表B中的正確位置。

稀疏矩陣的快速轉(zhuǎn)置算法如下：

(1)初始化num［ ］數(shù)組；

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

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

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

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

快速轉(zhuǎn)置算法在空間耗費(fèi)上除三元組表所占用的空間外，還需2個(gè)輔助向量空間，即num［1..A.n］，position［1..A.n］?？梢?jiàn)，算法在時(shí)間上的節(jié)省，是以更多的存儲(chǔ)空間為代價(jià)的。

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

3 稀疏矩陣的快速轉(zhuǎn)置算法的改進(jìn)

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

(1)令k1=num［1］;num［1］=1;

(2)對(duì)于col=2…A.n依次做：

k2= num［col］

num［col］=k1+num［col-1］;

k1=k2;

在轉(zhuǎn)置過(guò)程中，當(dāng)三元組表A中列號(hào)為col的1個(gè)元素加入到三元組表B時(shí)，則num［col］=num［col］+1，即：使num［col］始終指向三元組表A中列號(hào)為col的下一個(gè)非零元素在三元組表B中的正確位置。

改進(jìn)的快速轉(zhuǎn)置算法如下：初始化num［ ］數(shù)組；求num［ ］數(shù)組各元素的值；修改num［ ］數(shù)組各元素的值；將三元組表A中所有的非零元素直接放到三元組表B中正確位置上。

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

參考文獻(xiàn)

［1］耿國(guó)華.數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述［M］.西安：西安電子科技大學(xué)出版社，2002.

［2］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）［M］.北京：清華大學(xué)出版社，1997.

［3］殷人昆，陶永雷，謝若陽(yáng)，等.數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC++描述).北京：清華大學(xué)出版社，1999.

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

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

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

作者簡(jiǎn)介 王 榮 女，1972年出生，陜西華陰人，渭南師范學(xué)院計(jì)算機(jī)科學(xué)系講師，西安電子科技大學(xué)碩士研究生。