第一章 线性代数预备知识 1
1.1 矩阵与向量 1
1.2 方阵的基本类型 2
1.3 向量的内积与范数 3
1.4 Hermite矩阵 5
1.5 矩阵范数 7
1.6 线性无关向量组的正交化 12
1.7 圆盘定理与矩阵特征值估计 15
1.8 对角占优矩阵 16
1.9 非负矩阵 18
1.10 L矩阵、M矩阵与H矩阵 20
第二章 线性方程组直接求解的基本方法 23
2.1 Gauss消去法 23
一、基本方法 23
二、矩阵的LU分解 26
三、主元选取策略 29
四、Gauss消去法的性质 30
2.2 对称矩阵的LDLT分解 32
一、对称矩阵的LDLT分解 32
三、对称正定矩阵的Cholesky分解 34
二、LDLT分解中的主元选取 34
2.3 对称矩阵的Aasen分解 35
2.4 矩阵的UL分解 38
2.5 用正交变换求解线性方程组 39
2.6 解的扰动理论与改进措施 41
第三章 稀疏矩阵 43
3.1 简介 43
3.2 稀疏矩阵的邻接图 44
一、图与稀疏矩阵的关系 44
二、对称置换与邻接图的关系 44
3.3 稀疏向量 45
三、对称置换与矩阵的性质 45
一、稀疏向量的加法 46
二、稀疏向量的内积 47
3.4 稀疏矩阵的存储与分解 47
一、稀疏矩阵分解中的非零元填充 47
二、对角线存储法 48
三、对称矩阵的变带宽存储法 50
四、坐标存储法及其改进方法 50
五、Ellpack-Itpack存储法 52
六、CSR存储法 52
七、Sherman's存储法 53
八、超矩阵存储法 54
九、符号分解与动态存储方案 55
3.5 线性方程组直接求解中的主元修正技术 55
一、逆矩阵的秩1修正公式 56
二、线性方程组直接求解中的主元修正技术 56
3.6 稀疏矩阵与稠密向量的乘积 58
3.7 稀疏线性方程组的应用 58
第四章 带状线性方程组的直接解法及其并行算法 60
4.1 带状线性方程组的直接解法 60
一、一阶线性递推的倍增法 61
4.2 线性递推关系的并行算法 61
二、一阶线性递推的分段法 63
三、分段法与倍增法的结合 64
四、高阶线性递推的并行计算 65
4.3 利用线性递推并行求解三对角线性方程组 67
4.4 并行求解带状线性方程组的多重特解法 68
4.5 并行求解带状线性方程组的循环约化法 70
一、三对角线性方程组的循环约化法 70
二、三对角线性方程组循环约化法的一个变种 72
三、五对角线性方程组的变种循环约化法 74
四、一般带状线性方程组的变种循环约化法 76
4.6 利用孪生分解并行求解带状线性方程组 77
4.7 带状线性方程组的并行分裂法 79
一、并行求解三对角线性方程组的Wang分裂法 79
二、利用计算顺序的重新安排改进Wang分裂法 81
三、使负载充分平衡的数据分布方式 84
四、一般带状线性方程组的分裂法 85
五、分裂法的矩阵形式 88
六、分裂法的一般化 90
第五章 对称结构稀疏矩阵的三角分解技术与并行计算 92
5.1 简介 92
5.2 无向图的基本概念 93
5.3 广度搜索与邻接层次结构 96
5.4 大偏心距顶点的计算 98
一、窄层次结构与伪直径端点 98
二、计算大偏心距顶点的谱方法 99
5.5 带宽缩减算法 99
一、CM算法与RCM算法 100
二、GPS算法 102
三、Rosen算法 103
5.6 外形缩减算法 104
一、Sch？nauer算法 104
二、AU算法 105
三、King算法与Gibbs-King算法 106
四、Sloan算法 107
五、Hager算法 109
六、谱方法 112
七、多层算法的应用 116
5.7 对称Gauss消去法的图论解释 119
5.8 最小度排序 122
一、基本方法 122
二、最小度算法的几个改进措施 123
5.9 对称稀疏矩阵的树型分割 124
5.10 无向图的分割 125
一、利用嵌套二分得到p路分割 126
二、利用图中顶点的坐标进行二分 128
三、惯性二分 128
四、几何分割 129
五、一般无向图中顶点虚拟坐标的计算 131
六、利用层次结构对图进行分割 131
七、KL算法 133
八、谱二分算法 135
九、谱四分与谱八分 136
十、多层分割法 138
十一、利用二分图中的匹配技术缩小分割子 139
5.11 嵌套排序 142
一、基本思想 142
二、长方网格上的嵌套排序 144
三、一般无向图嵌套排序时分解因子的非零元与计算量估计 146
四、一路嵌套排序 147
5.12 无向图的深度搜索 150
5.13 无向图的字典顺序搜索 152
5.14 利用独立集进行并行计算 154
一、有限元中的波前法 156
5.15 波前法与多波前法 156
二、将波前法推广到结构对称的稀疏线性方程组 158
三、多波前法 160
四、多波前法的并行计算 163
五、消去树高度的缩减 168
第六章 一般稀疏矩阵的三角分解技术与并行计算 171
6.1 简介 171
6.2 结构不对称的稀疏矩阵的图论解释 171
6.3 有向图的强连通部件 173
6.4 有向图的搜索方法 175
一、深度搜索 175
二、广度搜索与邻接层次结构 177
6.5 强连通部件的分离 178
一、Sargent＆Westerberg算法 178
二、Tarjan算法 179
6.6 利用非对称置换增大矩阵的对角元 182
一、在无回路图中寻找没有公共顶点的路径极大集 183
二、Hall算法 184
三、Hopcroft＆Harp算法 186
四、利用截线最大化算法将绝对值较大的元素置换到对角线上 189
五、利用非对称置换使得对角元绝对值之积最大 190
六、利用非对称置换使得对角元绝对值之和最大 193
七、利用非对称置换使对角元绝对值的最小值最大 194
6.7 利用行列比例化技术进一步增大对角元 195
6.8 三角分解时减少填入元的主元策略 196
一、Markowitz策略及其改进方法 196
二、利用对称结构的排序算法求解一般稀疏线性方程组 198
三、延迟分解法 200
6.9 Gauss消去法的EDAG模型 200
一、稀疏下三角线性方程组的DAG模型 201
二、Gauss消去法的EDAG模型 201
三、符号分解 203
四、三角线性方程组的并行求解 204
6.10 利用分块技术进行大粒度并行计算 209
一、对角块为长方矩阵的块三角分割形式 209
二、化矩阵为带边界的块三角形式 212
6.11 稀疏矩阵的逐列分解法 215
6.12 一般稀疏矩阵LU分解的波前法与多波前法 216
一、一般稀疏矩阵LU分解的波前法 216
二、基于对称结构消去树的多波前法 218
三、基于列消去树的多波前法 219
四、基于EDAG的多波前法 221
7.1 迭代法概述 223
第七章 经典迭代法及其并行计算 223
7.2 基本迭代法 225
一、Jacobi迭代 225
二、SOR与Gauss-Seidel迭代 226
三、性质A与相容次序 228
四、SSOR迭代 231
7.3 AOR迭代 233
7.4 迭代法中基本操作的并行实现 236
一、内积的并行计算 237
二、块三对角矩阵与稠密向量乘法的并行计算 237
四、将一次迭代内所有操作一起并行计算时的考虑 238
三、一般稀疏矩阵与稠密向量乘法的并行计算 238
7.5 红黑排序与多色排序 239
一、红黑排序 239
二、多色排序 241
7.6 外推技术与多项式加速 242
一、外推技术 242
二、Chebyshev多项式加速 243
7.7 交替方向隐式方法 245
7.8 多分裂迭代法 249
一、基本多分裂迭代法 249
二、一个特殊形式的多分裂迭代 251
三、松弛型多分裂迭代 253
四、二级多分裂迭代 253
7.9 异步迭代 254
一、对称正定线性方程组的混乱松弛法 254
二、一般异步迭代法 255
第八章 投影方法及其并行计算 257
8.1 一般投影算法 257
一、一般投影法的矩阵表示 257
二、投影方法的最优性 258
三、投影方法的误差界 259
四、最速下降法 260
五、MR迭代 262
六、残量最速下降法 263
七、加型与乘型投影法 263
8.2 Krylov子空间 264
一、Krylov子空间的基本性质 264
二、计算Krylov子空间正交基的Arnoldi方法 265
三、标准正交基的并行构造 268
8.3 基于正交化的误差投影型Krylov子空间方法 269
一、完全正交化方法 269
三、IOM与DIOM方法 270
二、重启型FOM方法 270
8.4 对称情形的误差投影型Krylov子空间方法 272
一、Lanczos方法 272
二、基本CG法 273
三、利用CG法中的参数估计特征值 274
四、CG法的收敛性分析 275
五、预条件CG法 277
六、三项递推形式的CG法 278
七、对预条件CG法的步骤重新安排以便并行计算 280
八、多搜索方向CG法 280
一、GMRES方法 282
8.5 基于正交化的残量投影型Krylov子空间方法 282
二、最小二乘问题的求解 283
三、FOM与GMRES之间的关系 285
四、GMRES的收敛性 287
五、重启型GMRES方法 288
六、QGMRES与DQGMRES方法 289
七、对称情形下的残量投影算法 291
八、GCR，ORTHOMIN与ORTHODIR 292
8.6 多右端项时的Krylov子空间方法 293
一、块Arnoldi方法 293
二、块FOM方法 294
三、块GMRES方法 295
8.7 Lanczos双正交化算法 296
一、Lanczos双正交化算法 296
二、处理崩溃的重启与前瞻技术 297
8.8 基于双正交化的误差投影型Krylov子空间方法 300
一、BiCG方法 300
二、CGS方法 301
三、BICGSTAB方法 302
四、BICGSTAB2方法 304
五、GPBICG方法 306
六、BICGSTAB(1)方法 307
8.9 基于双正交化的准残量最小化方法 311
一、QMR方法 311
二、TFQMR方法 312
三、QMRCGSTAB方法 314
8.10 与正规方程组有关的投影型方法 316
一、NE-SOR与NR-SOR方法 316
二、Cimmino方法 317
三、CGNR方法 317
五、鞍点问题 318
四、CGNE方法 318
第九章 一般稀疏线性方程组的预条件技术与并行计算 320
9.1 引言 320
9.2 基于经典迭代的预条件技术 321
9.3 一般稀疏线性方程组的不完全分解预条件 323
一、不完全LU分解的一般理论 323
二、无填充不完全LU分解预条件 325
三、多层填充的不完全LU分解预条件 326
四、ILUT预条件及其改进技术 327
五、不完全LU分解的对角元修正 330
六、对不完全LU分解质量的衡量 331
9.4 对称稀疏线性方程组的不完全分解预条件 332
一、对称稀疏线性方程组的不完全UTDU分解 332
二、双门槛不完全Cholesky分解及其改进措施 333
三、不完全UTDU分解的对角元修正技术 335
四、CIMGS预条件 335
五、非零元结构的C性质与应用 338
六、位移不完全Cholesky分解 342
七、对角元补偿技术 343
9.5 利用排序改善不完全分解的质量与并行性 343
一、排序对不完全分解质量的影响 343
二、利用多色排序构造并行预条件 344
三、利用极大独立集构造并行不完全分解预条件 346
四、区域分解与相关并行技术 346
五、利用多波前法构造并行不完全分解预条件 348
六、化一般矩阵为块三对角形式 348
9.6 截断级数在预条件构造中的应用 349
一、多项式预条件 349
二、有理近似预条件 350
9.7 稀疏近似逆预条件技术 352
一、利用全局迭代计算稀疏近似逆 352
三、为稀疏近似逆确定非零元结构的先验方法 353
二、逐列计算稀疏近似逆 353
四、利用一维优化动态计算稀疏近似逆 355
五、利用全局优化动态计算稀疏近似逆 357
六、利用最小二乘计算分解型稀疏近似逆 359
七、利用元素比较计算分解型稀疏近似逆 360
八、利用双共轭过程计算分解型稀疏近似逆 361
九、排序对稀疏近似逆的影响 363
第十章 块三对角线性方程组的预条件技术与并行计算 366
10.1 按对角线方式进行填充的不完全分解 366
一、二维椭圆型方程五点差分离散矩阵的IC(ξ，η)预条件 366
二、三维椭圆型方程七点差分离散矩阵的IC(0)预条件 368
10.2 利用拟消去迭代构造预条件 369
10.3 块不完全分解预条件 370
一、基本方法 370
二、对角元修正型块不完全分解 372
三、预条件迭代中无逆矩阵操作的块不完全分解变种 373
四、构造过程中无逆矩阵操作的块不完全分解变种 374
10.4 局部块不完全分解预条件 376
一、块三对角矩阵的局部块分解预条件 376
二、局部块分解预条件的实现 378
三、对角元修正型局部块分解 380
四、三维问题的局部块分解 381
五、局部块分解预条件的并行计算 385
10.5 块三对角矩阵块不完全分解的松弛技术 391
10.6 块三对角矩阵预条件的并行化技术 392
一、多分裂并行化技术 392
二、伪重叠并行化技术 394
三、局部分解并行化技术 396
10.7 块三对角矩阵的并行预条件技术 398
一、经典迭代对误差的光滑 400
11.1 几何多重网格简介 400
第十一章 代数多重网格技术 400
二、传递算子 401
三、多重网格法 402
四、光滑算子的选取 404
五、混合基多重网格法 404
11.2 经典代数多重网格法 406
一、代数多重网格法产生的背景 406
二、代数光滑 408
三、两层代数多重网格的收敛性 408
四、插值算子 409
五、粗网格构造的经典技术与对应的插值算子 412
六、粗网格的并行构造 414
七、基于F/C排序的准代数多重网格法 416
11.3 基于F松弛的代数多重网格法 418
11.4 聚集型代数多重网格法 419
一、基本思想 419
二、聚集的构造 420
三、收敛性差的原因分析 421
四、利用对Galerkin算子进行调节来改进收敛性 422
五、利用对校正过程进行光滑来改进收敛性 423
七、利用测试向量构造光滑的插值算子 424
六、利用对插值算子进行光滑改进收敛性 424
11.5 ILU型代数多重网格法 426
一、混合基多重网格与ILU的关系 426
二、不完全分解多层图算法 427
三、多层不完全分解 429
四、嵌套网格不完全LU分解 436
11.6 嵌套块消去技术 437
一、基于块消去的类多重网格法 437
二、近似块循环约化法 438
三、F点子矩阵的近似对代数多重网格有效性的影响 441
参考文献 445