本 文 所 採用 的 方法 為 通用 稀疏 矩陣 法 中 的 克雷斯基 解法 及 消去樹 的 架構 下 的 多波前法 以 求解 稀疏 矩陣 。 利用 稀疏 矩陣 之 結點 重排 ， 以 求 在 減少 記憶體 之 儲存量 的 考量 下 ， 使 其 消去樹 於 分解 後 ， 利於 分散式 之 計算 。 另外 對於 工作量 的 分配 ， 則 採用 經驗 法則 ， 以 求 達到 自動 分配 的 功能 。 １‧４ 本 文 架構 。 本 文 共 分 六 章 ： 第一 章 簡單 的 說明 本 文 的 研究 動機 及 目的 。 第二 章 簡單 的 介紹 有限 元素 分析 法 中 的 大型 稀疏 矩陣 之 解法 與 基本 概念 。 第三 章 針對 考慮 分散式 處理 的 大型 稀疏 矩陣 解法 及 結點 重排 ， 討論 相關 問題 。 第四 章 針對 消去樹 之 分割 與 工作量 分配 、 實際 幾何 位置 的 關係 ， 並 討論 相關 問題 。 第五 章 以 實際 結構 工程 上 的 例子 測試 本 文 所 提 之 方法 ， 並 加以 討論 。 第六 章 對 本 文 所 得 的 結果 做 一 討論 。 第三 章 稀疏 矩陣 之 重 排 。 ３‧１ 簡介 。 在 前 一 章 中 曾 提到 ， 大型 稀疏 矩陣 之 解法 ， 一般 被 廣泛 使用 的 方法 ， 主要 有 兩 種 ， 帶寬法 以及 通用 稀疏 矩陣 法 。 其中 的 帶寬法 是 利用 只 記錄 矩陣 中 的 非零外框 ， 以 求 減少 記憶體 之 儲存量 ， 但是 通常 在 外框 之內 還是 有 很多 的 零 存在 。 所以 記憶體 之 儲存量 並 非 最 省 的 ， 另外 在 前面 已經 提 過 了 此 類 之 方法 因 其 演算法 上 的 特性 ， 並 不 適用 於 平行式 或 分散式 之 計算 。 其 原因 主要 是 因 其 在 求解 的 過程 中 ， 高斯 消去法 為 循序 消去 ， 不 適合 拆開成 獨立 的 部份 做 平行式 或 分散式 消去 。 而 相對於 帶寬法 ， 通用 稀疏 矩陣 法則 只 儲存 非 零 的 位置 ， 以及 在 求解 的 過程 中 會 變為 零 的 位置 （ 亦 稱為 填入 ， ｆｉｌｌ — ｉｎ ） ， 而且 此 方法 在 求解 的 過程 中 ， 可以 利用 多波前法 作 平行式 或 分散式 之 計算 。 其中 稀疏 矩陣 之 重排 便 是 解 稀疏 矩陣 的 第一 個 步驟 ， 一 個 完美 的 重排 ， 也 就 是 轉換 矩陣 Ｐ↑ ， 不僅 可以 使 填入 的 位置 減少 ， 亦 可以 使 解 稀疏 矩陣 的 計算量 減少 ， 可見得 其 重要性 。 所以 在 下 一 節 中 介紹 一些 較 好 的 稀疏 矩陣 排法 。 ３‧２ 稀疏 矩陣 之 排法 。 如 在 前面 已經 提 過 的 ， 稀疏 矩陣 之 排法 的 目的 主要 在 減少 記憶體 之 儲存量 ， 所以 在 此 討論 幾 種 主要 的 方法 ： １ ． 傳統 帶寬法 中 的 Ｒｅｖｅｒｓｅ Ｃｕｔｈｉｌｌ — ＭｃＫｅｅ ａｌｇｏｒｉｔｈｍ 。 ２ ． 通用 稀疏 矩陣 法 中 的 最 小 度數 排法 。 ３ ． 通用 稀疏 矩陣 法 中 的 平行 消去法 。 ４ ． 通用 稀疏 矩陣 法 中 的 考慮 最 小 高度 的 最 小 排度法 。 ３‧２‧１ ↑Ｒｅｖｅｒｓｅ Ｃｕｔｈｉｌｌ — ＭｃＫｅｅ ａｌｇｏｒｉｔｈｍ 。 此 方法 的 目的 在於 減少 帶寬法 的 帶寬 ， 也 就是 使 非 零 處 集中 於 對角線 附近 ， 如 圖例 （３） ， 其 主要 之 演算法 如 下 。 如果 以 圖例 來 說明 ， 較 容易 明瞭 其 原理 。 原 結構圖 與 勁度 矩陣 的 樣子 如 圖 ， 經過 上面 步驟 一 與 二 後 ， 產生 如 圖 （ ４ — ｂ ） 的 等級圖 ， 然後 經過 上面 步驟 三 與 四 後 ， 產生 如 圖 （ ４ — ｃ ） 的 排 號 方式 。 其 矩陣圖 如 圖例 （３） 。 ３‧２‧２ 最 小 度數 排法 。 事實 上 ， 想要 找出 一 種 排法 Ｐ 使得 ＰＡＰＴ 的 填入 數目 為 最少 ， 已經 被 證實為 在 有效 時間 內 不可能 完成 的 （ ＮＰ ↑ｃｏｍｐｌｅｔｅ ｐｒｏｂｌｅｍ ， ， 所以 一般 最 常 採用 的 經驗 法則 為 最 小 度數 排法 ， 此 種 方法 只 要求 在 第 Ｋ 階段 時 為 局部 最 小 。 其 演算法 如 下 ： 其中 以 第三 步驟 花 的 時間 最 長 ， 因此 便 有 許多 ｈｅｕｒｉｓｔｉｃ ｆｕｎｃｔｉｏｎ 提出 ， 用以 提高 其 執行 的 速度 。 其中 以 Ｌｉｕ 所 提 的 方法 較 佳 ， 其 以 相連 集合 找出 所謂 的 不可 分開 的 結點 ， 亦 稱 超結點 ， 進行 消去 ， 並 使用 商圖 的 表示法 ， 使 演算法 簡化 ， 降低 程式 的 記憶體 用量 。 其 演算法