稀疏线性方程组的高效求解与并行计算【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

稀疏线性方程组的高效求解与并行计算PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第一章 线性代数预备知识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与ORTHODIR292

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