《超大规模稀疏矩阵计算方法》求取 ⇩

序言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