超大规模稀疏矩阵计算方法PDF电子书下载

序言 1

第一章 稀疏矩阵、基本类型和存贮方式 1

1.1 稀疏矩阵及其应用领域 1

1.2 稀疏矩阵基本类型 2

1.3 覆盖存贮法 8

1.4 拼凑存贮法 8

1.5 数组、列表、堆栈和排队存贮法 9

1.6 整数表存贮法 10

1.7 图的表示和存贮 12

1.8 等带宽存贮法 14

1.9 变带宽存贮法 15

1.10 大型变带状矩阵分段内外存结合存贮方案 16

1.11 大型阶梯矩阵分档内外存结合存贮方案 18

1.12 连接稀疏矩阵存贮方案 20

1.13 稀疏矩阵行格式存贮方法 22

1.14 稀疏矩阵有序和无序表示 23

1.15 Sherman s压缩存贮方案 25

1.16 矩阵分块存贮方案 26

1.17 符号处理和动态存贮方案 27

1.18 合并整型稀疏表及多重开关技术 28

1.19 利用扩展实累加器作稀疏向量加法 29

1.20 借助扩展指标整型数组，作稀疏向量加法 31

1.21 借助指标数组作两个稀疏向量乘积 31

第二章 稀疏矩阵基本解法 33

2.1 某些定义和性质 33

2.2 列高斯消去法 38

2.3 行高斯消去法 40

2.4 高斯-若当消去法 41

2.5 Crout和Doolittle三角因子分解 44

2.6 对称正定矩阵的Cholesky因子分解 49

2.7 修改主元的三角因子分解法 57

2.8 Householde及其改进算法 63

2.9 Givens及其改进算法 66

2.10 数值解的精度改善 73

第三章 稀疏矩阵特征值问题 78

3.1 引言 78

3.2 Rayleigh商迭代法 79

3.3 特征值的界 80

3.4 计算特征值的二分法 81

3.5 一般矩阵的简化 82

3.6 对Givens方法简化对称带状矩阵为三对角形式 83

3.7 三对角和Hessenberg矩阵的特征分析 85

3.8 直接迭代法和逆迭代法 85

3.9 子空间和不变子空间 87

3.10 同步迭代法 89

3.11 Lanczos算法 91

3.12 Lanczos算法的实际考虑 94

3.13 块Lanczos和带Lanczos算法 95

3.14 轨迹极小化 96

3.15 埃尔米特矩阵的特征分析 97

3.16 不对称特征问题 97

第四章 稀疏矩阵计算中的误差分析 99

4.1 非零元素分布表示、矩阵分解的运算量和存贮量 99

4.2 稀疏矩阵三角因子分解的误差分析 101

4.3 稀疏三角形矩阵方程的求解误差分析 105

4.4 稀疏矩阵消去法的误差分析 110

4.5 稀疏矩阵计算的数值误差控制 112

第五章 大型矩阵的逐行、逐列和分块解法 117

第一部分 大型带状矩阵的逐行分解法 117

5.1 存贮方案 117

5.2 一维公式 117

5.3 平移定理 118

5.4 带状矩阵结构分析 119

5.6 运算次数和内外存交换次数的估计 121

5.5 数值解的迭代改善 121

5.7 算法思想的描述 122

5.8 算法程序实现方案 124

5.9 程序功能、算例和程序 126

第二部分 大型阶梯矩阵的逐列分解法 135

5.10 快速计算公式 135

5.11 矩阵结构分析 136

5.12 算法思想的描述 137

5.13 运算次数及内外存交换次数的估计 138

5.14 算法程序实现方案 139

5.15 程序功能、算例和程序 140

第三部分 大型阶梯矩阵的分块分解新算法 144

5.16 存贮方式 144

5.17 快速计算公式和运算次数的估计 145

5.18 算法思想的描述 149

5.19 算法程序实现方案 149

第四部分 大型稀疏矩阵的三角因子分解法 150

5.20 存贮方式 151

5.21 三角因子分解公式 151

5.22 算法思想的描述及其程序实现方案 153

5.23 程序功能、算例和程序 157

第六章 超大型稀疏单重分区结构矩阵分块解法 163

第一部分 稀疏单重分区结构矩阵的分块分解法 163

6.1 单重分区结构矩阵方程及其分块分解法 163

6.2 单重分区结构矩阵分析 165

6.3 存贮方案 170

6.4 算法思想的描述 170

6.5 算法程序实现方案 174

6.6 单重分区结构矩阵方程和直接分解计算公式 177

第二部分 稀疏单重分区结构矩阵的直接分解法 177

6.7 单重分区结构矩阵分析 182

6.8 存贮方式 182

6.9 算法思想的描述 183

6.10 算法程序实现方案 186

第七章 超大规模稀疏多重分区结构矩阵分块解法 188

第一部分 超大规模稀疏二重分区结构矩阵分块解法 188

7.1 二重分区结构矩阵问题 188

7.2 计算公式推导 192

7.3 二重分区结构矩阵分析 204

7.4 存贮方案 207

7.5 计算方案 208

7.6 算法程序实现方案 211

7.7 运算工作量的估计与某些简单的比较 213

第二部分 超大规模稀疏反向三重分区结构矩阵分块解法 215

7.8 问题的提法 215

7.9 计算公式 216

7.10 计算方案 218

8.1 带状矩阵的求逆算法 221

第八章 超大规模稀疏矩阵的逆阵计算 221

8.2 大型三对角块矩阵求逆算法 224

8.3 超大型单重分区结构矩阵求逆算法 228

8.4 超大规模稀疏二重分区结构矩阵的部分逆阵元素算法 234

8.5 反向单重分区结构矩阵的逆阵算法 245

8.6 反向二重分区结构矩阵的逆阵算法 247

第一部分 对称矩阵高斯消去法排序 251

9.1 引言 251

第九章 稀疏矩阵排序技术 251

9.2 图论基本概念 252

9.3 宽度优先搜索法相邻等级结构 255

9.4 找出图中的伪边周顶点和狭窄等级结构 256

9.5 减少对称矩阵带宽 257

9.6 减少对称矩阵的轮廓 258

9.7 对称高斯消去法的图论背景 259

9.8 最小度算法 261

9.9 一个对称稀疏矩阵的树分割 263

9.10 嵌套剖分 266

9.11 有限元问题的一维剖分和矩阵元素装配 269

9.12 大地平差问题的一维剖分和矩阵元素装配 272

9.13 大地平差问题的二维剖分法 277

9.14 无向图的深度优先搜索法 279

第二部分 不对称矩阵高斯消去法排序 282

9.15 关于不对称矩阵的图论 282

9.16 图的强构件 283

9.17 有向图的深度优先搜索法 284

9.18 有向图的宽度优先搜索法和有向图相邻等级结构 287

9.19 在非周期有向图中找出不相交路径顶点的最大集合 288

9.20 找出横截的Hall算法 289

9.21 找出横截的Hopcroft和Karp算法 290

第十章 超大规模稀疏最小二乘大地平差问题 295

10.1 误差方程式和法化方程式的组成原理 295

10.2 块正交化法 299

10.3 块Oholesky分解法 305

10.4 五万点平差算例 316

10.5 结论 324

10.6 附录 325

参考文献 341