稀疏矩陣并行算法

1、北 京 航 空 學(xué) 院 學(xué) 報(bào)J o u r n a l o f B e i j i n g I n s t i t ut e o A f o n e r a ut i e s a n d A t s o n a r ut i c s一 九八二 年 第 四 期 恤 4 1 9 8 2稀 疏 矩 陣 的 并 行 算 法周 永 法【 摘 要】本文 利 用 圖研 究了 稀疏 矩 陣的三 角狀 分解過(guò) 程, 證明 了關(guān)于 結(jié) 構(gòu) 對(duì) 稱(chēng) 稀 疏

2、 矩 陣的三 角狀 分解過(guò)程 的最長(zhǎng)時(shí) 步分 布定理 ; 并 對(duì)利 用 無(wú) 向圖表示 的矩 陣進(jìn) 行 了討 論 ; 在 固定數(shù) t 處理器 的條件下, 為 了減 少稀疏 矩陣 并行三 角狀 分解 過(guò)程 的機(jī)時(shí), 建 議 了 一個(gè)排列樞 軸節(jié) 點(diǎn)的算 法 ; 給 出 了 算法 舉例 ; 最后 對(duì)本文 的結(jié) 果進(jìn) 行 了討 論。引 古 r 2大家熟 知, 幾乎 所 有的 計(jì)算 機(jī)輔助 分析網(wǎng) 絡(luò)程 序都 包括求解 稀疏 矩陣 的算 法。 求

3、 解稀疏矩陣, 通常 采用 高斯消 元 法 或三 角狀分 解法。 它們所 需 的機(jī)時(shí) 在很 大程度 上 依 櫻于稀疏 矩陣樞 軸 元素的 計(jì)算 次序。 特 別是利 用 選 代 法 求解非 線(xiàn)性 方 程組的過(guò) 程 中, 每一 次迭 代求解 的矩陣結(jié)構(gòu) 完全相 同。 在這 種情 況下, 稀疏矩 陣樞軸 元素 的排 列次 序?qū)η蠼?非線(xiàn)性 方 程組 的機(jī)時(shí)的影響, 尤 為 突 出 ; 選代 次數(shù)愈 多, 影響 愈大。 如果 我們 能求 出這

4、樣 的一 種樞軸 元 素 的 排列, 稱(chēng) 之為 最佳排 列次序, 當(dāng)我 們按照 這 一 次 序求解該 矩陣 時(shí), 所 需 的機(jī)時(shí) 最少, 那 么這 就意味著降 低所用 的 機(jī)時(shí)和設(shè) 計(jì)費(fèi) 用。在 單處理 器的 條件下, 前人 在這 方而 已 作 了不 少工 作 [ 4 」。 但 是, 當(dāng)今 由于 集 成 電路飛 躍發(fā) 展, 帶 多處理 器 的計(jì)算 機(jī)已 提到 日程, 它 的優(yōu)點(diǎn) 是 對(duì)問(wèn)題 可井行 計(jì)算, 從 而提 高 了計(jì)算 速度。

5、如果使用 這 種計(jì)算 機(jī)求 解稀疏 矩陣, 那 么 如何 組織拜 行計(jì) 算, 就 成 為主要 間題。 本文就這 一 問(wèn)題 進(jìn)行 了討 論。 〔 1 ] [ 2 」 的作者曹 討論 過(guò)這 一問(wèn)題, 井 建議 了一個(gè)算 法, 該 算 法是基 于對(duì)每一 可能選 作樞 軸 元素 的主對(duì) 角元比較 其 求解矩 陣所需 的計(jì) 算量 和時(shí)步, 并 依此 來(lái)確 定最 佳樞軸 元素排 列 次 序。 當(dāng) 多處 理器 的 數(shù) 目是 一個(gè) 固定數(shù)量 的 條件下

6、, 為 了綜合 權(quán)衡 計(jì)算量 和時(shí) 步對(duì) 求解矩 陣的 機(jī)時(shí)影 響, 〔1 〕、 「 2 」 文 的作者 采用 了材。 和 M 。 , 計(jì) 算量 的權(quán)和 時(shí)步 的權(quán) 的概念。 亦 即最佳 樞軸 元素排 列次 序主要 依據(jù) C ( j ) (一- 牙。 O ( ] ’) + W 。 L ( ] ’) 為最小 的條件來(lái)確定。 共 中 j— 樞軸 元素 順序號(hào) ; O ( ] ’) 第 j 號(hào) 樞軸 元 素的計(jì)算量 ; L ( ) ] — 第

7、 j號(hào) 樞軸 元素所 產(chǎn)生 的時(shí)步。 這 種算法的不足 之處 不僅 在于, 為 了確定樞 軸 元素排列 次 序, 需 要較 多的DOI: 1 0. 1 37 00 /j . bh. 1 00 1 - 59 65. 1 98 2. 0 4. 00 1則一定但是所 以b ) 如果則一 定但是S 公 萬(wàn) ’ + 2s 沂` 十 2S 丁 丁` < 5 7丁`S 叮` < S 丁 丁 `所以, 無(wú)論 5 7, 和 S 丁` 為何數(shù)值

8、 總是S 乳 < S 甲 ,s 丁 j < s 下`所 以對(duì)第切 個(gè)樞軸元 素, 定理亦 成立。結(jié) 論: 由于 。 是 A 矩陣 的階 數(shù) 為一個(gè) 有限值, 按 照歸 納法, 定理 成立。對(duì)任 意矩陣 月, 可作一 個(gè)無(wú) 向圖 與之相 對(duì)應(yīng)〔 3 〕。 無(wú) 向圖 的作法 如下:( 1 ) A 中的每 一 個(gè)主 對(duì)角 線(xiàn)元素, 在無(wú) 向 圖中, 對(duì)應(yīng)一 個(gè)節(jié) 點(diǎn)。( 2 ) A 中每 一 對(duì)非零 的非 主對(duì) 角線(xiàn) 的元 素 (

9、 af , , 。 , ` ), 在無(wú) 向圖 中, 對(duì) 應(yīng)連 接節(jié) 點(diǎn) `和 j 的一 條無(wú) 向支 路。無(wú) 向圖具有 如下性質(zhì):( D 如果 在無(wú) 向圖中選擇 節(jié)點(diǎn) k 作 為 第 。 個(gè)樞 軸節(jié) 點(diǎn), 它具 有尸 個(gè)支 路 與之相連。 根據(jù)矩陣 的結(jié)構(gòu) 對(duì)稱(chēng)性 以及 公式 ( 1 ) 和 ( 2 ) 可 知, 該 節(jié)點(diǎn) 對(duì)應(yīng) 的總 運(yùn)算數(shù) 目為 尸 ( 尸 + 1 )。( 2 ) 如果 與樞 軸節(jié) 點(diǎn)相 連 的二節(jié)點(diǎn) 間, 無(wú) 支路