並行科學計算

第 1 章 計算機體系結構 ······························································.1
1.1 不同類型的並行 ·······························································.1
1.1.1 重疊、並發和並行 ·····················································.1
1.1.2 算術邏輯單元中的空間並行與時間並行 ··························.3
1.1.3 並行與內存······························································.5
1.2 存儲設備體系結構 ····························································.5
1.2.1 多體交錯式內存 ························································.6
1.2.2 多級存儲·································································.7
1.2.3 分布式存儲·····························································.11
1.3 混合體系結構 ··································································12
1.3.1 GPU 加速器 ·····························································12
1.3.2 混合計算機······························································13
第 2 章 並行化與編程模型 ···························································15
2.1 並行化 ···········································································15
2.2 性能指標 ········································································17
2.2.1 並行度····································································17
2.2.2 負載平衡·································································18
2.2.3 粒度·······································································19
2.2.4 可擴展性·································································19
2.3 數據並行 ········································································20
2.3.1 循環·······································································20
2.3.2 依賴性····································································21
2.3.3 依賴性示例······························································22
2.3.4 歸約運算·································································24
2.3.5 嵌套循環·································································25
2.3.6 OpenMP ··································································29
2.4 案例分析：向量化 ····························································31
2.4.1 向量計算機和向量化 ··················································31
2.4.2 依賴性····································································32
2.4.3 歸約運算·································································33
2.4.4 流水線運算······························································34
2.5 消息傳遞 ········································································36
2.5.1 消息傳遞編程 ···························································36
2.5.2 並行環境管理 ···························································36
2.5.3 點對點通信······························································37
2.5.4 聚合通信·································································38
第 3 章 並行算法概念 ·································································41
3.1 並行循環算法 ··································································41
3.1.1 歸約算法的基本原理 ··················································41
3.1.2 歸約算法的開銷和穩定性 ············································42
3.1.3 循環歸約·································································44
3.2 矩陣乘法的數據分布 ·························································45
3.2.1 行算法和列算法 ························································45
3.2.2 分塊算法·································································47
3.2.3 分布式算法······························································50
3.2.4 算法實現·································································51
第 4 章 矩陣計算基礎 ·································································55
4.1 線性代數回顧 ··································································55
4.1.1 向量空間、點積、正交投影 ·········································55
4.1.2 線性映射與矩陣 ························································58
4.2 矩陣性質 ········································································61
4.2.1 特殊矩陣、特征值、特征向量 ······································61
4.2.2 矩陣範數·································································63
4.2.3 基變換····································································65
4.2.4 矩陣的條件數 ···························································66
第 5 章 稀疏矩陣 ·······································································71
5.1 稀疏矩陣的起源 ·······························································71
5.2 稀疏矩陣的並行構建：共享存儲···········································75
5.3 稀疏矩陣的分塊並行構建：分布式存儲 ··································75
第 6 章 用 LU 分解法求解線性方程組·············································78
6.1 線性方程組求解 ·······························································78
6.1.1 直接法····································································78
6.1.2 疊代法····································································79
6.2 LU 分解的原理 ·································································81
6.3 高斯消元法 ·····································································84
6.4 高斯-若爾當消元法 ···························································86
6.5 對稱矩陣的 Crout 分解和楚列斯基分解 ··································91
第 7 章 稠密矩陣 LU 分解的並行化················································94
7.1 分塊分解 ········································································94
7.2 在 MPI 編程環境中實現分塊分解 ··········································98
7.3 前向-後向替換法的並行化 ···············································.102
第 8 章 稀疏矩陣的 LU 分解 ······················································.104
8.1 分解後的矩陣結構 ·························································.104
8.2 符號分解與重新編號 ······················································.107
8.3 消去樹 ········································································.110
8.4 消去樹與依賴性 ····························································.115
8.5 嵌套剖分 ·····································································.116
8.6 前向-後向替換 ······························································.120
第 9 章 對稱正定矩陣的 Krylov 法·············································.123
9.1 Krylov 子空間基礎 ·························································.123
9.1.1 Krylov 子空間························································.123
9.1.2 Arnoldi 基的構建····················································.125
9.2 對稱矩陣 Lanczos 基的構建 ·············································.127
9.3 Lanczos 法 ··································································.128
9.4 共軛梯度法 ··································································.132
9.5 與梯度法的對比 ····························································.136
9.6 對稱正定矩陣的預處理 ···················································.138
第 10 章 任意矩陣的正交化方法 ················································.141
10.1 GMRES 法 ·································································.141
10.2 面向對稱矩陣的 MINRES 法 ···········································.148
10.3 ORTHODIR 法 ····························································.151
10.4 非對稱矩陣的預處理 ·····················································.152
第 11 章 非對稱矩陣的雙正交化方法··········································.154
11.1 非對稱矩陣雙正交基的構建 ············································.154
11.2 非對稱 Lanczos 法 ·······················································.158
11.3 雙共軛梯度法 ······························································.159
11.4 準極小殘量法 ······························································.163
11.5 穩定雙共軛梯度法 ························································.167
第 12 章 Krylov 法的並行化 ·····················································.173
12.1 稠密矩陣-向量乘法的並行化 ··········································.173
12.2 稀疏矩陣-向量乘法：按頂點劃分·····································.174
12.3 稀疏矩陣-向量乘法：按元素劃分·····································.176
12.3.1 區域分解原理概述 ················································.176
12.3.2 矩陣-向量乘法 ·····················································.177
12.3.3 數據通信 ····························································.178
12.4 點積的並行化······························································.179
12.5 Krylov 法的並行化小結··················································.180
第 13 章 並行預處理方法 ·························································.182
13.1 不完全分解法······························································.182
13.1.1 原理 ··································································.182
13.1.2 並行化 ·······························································.184
13.2 舒爾補法····································································.186
13.2.1 局部最優預處理 ···················································.186
13.2.2 舒爾補法的原理 ···················································.187
13.2.3 舒爾補法的性質 ···················································.189
13.3 代數多重網格······························································.191
13.3.1 基於投影的預處理 ················································.191
13.3.2 粗糙網格的代數構建 ·············································.193
13.3.3 代數多重網格法 ···················································.195
13.4 加性施瓦茨預處理法 ·····················································.196
13.4.1 重疊原理 ····························································.196
13.4.2 乘性方法與加性方法 ·············································.198
13.4.3 加性 Schwarz 預處理法···········································.198
結語························································································.201