稀疏矩陣并行算法

1、北 京 航 空 學(xué) 院 學(xué) 報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ān)于 結(jié) 構(gòu) 對 稱 稀 疏

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

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

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

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

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

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

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

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