向量算法与并行算法PDF电子书下载

第一章 引言 1

1.1 并行计算机简介 1

1.1.1 阵列式处理机 1

目录 1

1.4.1 外积算法 1

1.1.2 流水线处理机 3

1.1.3 多处理机 4

1.2 并行算法的评价标准 5

1.2.1 加速 5

1.2.2 效率 6

1.2.3 冗余度 6

1.3 内积运算的并行复杂性和误差分析 7

1.3.1 并行复杂性 8

1.3.2 误差分析 9

1.4.2 对角线乘法 11

1.4 矩阵与向量的乘积 11

1.5 三角形方程组的并行解法 12

1.5.1 列扫描法 13

1.5.2 S—B方法 14

第二章 线性代数方程组的向量解法 19

2.1 向量消去法 19

2.1.1 算法描述 19

2.1.2 计算公式 20

2.1.3 讨论 22

2.2 广义Householder方法 22

2.2.1 Housekolder矩阵乘积的WY表示 23

2.2.2 广义Householder矩阵 24

2.3.1 双曲Cholesky（乔莱斯基）分解 26

2.3 双曲旋转变换 26

2.3.2 矩阵Q的显式表示 31

2.3.3 方程组解的公式 35

2.4 并行l重Jacobi（雅可比）迭代法 37

2.5 交替方向法 41

2.6 多色SOR（超松弛迭代）方法 44

第三章 并行预处理共轭斜量法 47

3.1 PCG算法 47

3.2 截断级数预处理 49

3.2.1 矩阵M？是对称正定矩阵的条件 49

3.2.2 P步SSOR（对称超松弛）迭代 51

3.2.3 P与条件数的关系 53

3.3 不完全Cholesky分解的向量化处理 53

3.3.1 ICCG方法的向量化处理 54

3.3.2 截断级数引起的影响 55

3.4 不完全块Cholesky分解 56

3.4.1 块Cholesky分解 56

3.4.2 不完全块Cholesky分解 59

3.4.3 向量化处理 63

3.4.4 不求逆的块预处理 66

3.5 不完全块奇偶约化法 68

3.5.1 块奇偶约化算法 68

3.5.2 不完全块奇偶约化算法 70

3.6 H—矩阵的不完全分解 73

3.6.1 H—矩阵的定义和性质 73

3.6.2 分解定理 75

4.1 求解特殊方程组的并行算法 77

4.1.1 分块消去法 77

第四章 任务的分配与调度 77

4.1.2 DAC方法 80

4.1.3 并行波前法 84

4.1.4 带形方程组 86

4.1.5 块三对角方程组 90

4.2 直接法的任务系统和并行效率 95

4.2.1 高斯消去法 96

4.2.2 快速Givens（吉文斯）变换方法 100

4.2.3 镜像映射法 105

4.3 最优调度策略 107

4.3.1 标号与下界 108

4.3.2 最优算法 110

第五章 异步迭代法 115

5.1 异步牛顿法 116

5.2.1 CR方法 118

5.2 CR方法和BCR方法 118

5.2.2 BCR方法 120

5.3 求解线性方程组的异步迭代法 122

5.3.1 定义 122

5.3.2 收敛性定理 124

5.4 异步块迭代法 130

5.4.1 数学模式 130

5.4.2 收敛的充分条件 131

5.4.3 等价条件 132

第六章 多分裂迭代法 134

6.1 多分裂迭代法的定义及收敛性 134

6.1.1 多分裂迭代法的定义 134

6.1.2 收敛定理 135

6.2.1 M—矩阵的三个多分裂方法与收敛速度的估计 137

6.2 特殊矩阵的多分裂方法 137

6.2.2 带形M—矩阵的多分裂方法 143

6.2.3 对称正定矩阵的多分裂方法 146

6.3 关于权矩阵的讨论 151

6.4 多分裂迭代法的混乱模式 155

6.4.1 混乱模式A 156

6.4.2 混乱模式B 159

第七章 矩阵特征值问题 163

7.1 对称三对角矩阵特征值的完全并行算法 163

7.1.1 秩1分裂 163

7.1.2 秩1修正矩阵特征值的计算 165

7.1.3 收缩 166

7.1.4 精确度 168

7.2.1 并行Jacobi方法 172

7.2 并行Jacobi方法与加速 172

7.2.2 加速 174

7.3 计算实矩阵特征值的WZ分解法 177

7.3.1 算法 177

7.3.2 收敛性 179

第八章 方程求根与非线性递推计算 181

8.1 求多项式单根的并行算法 181

8.1.1 预备定理 181

8.1.2 迭代公式与收敛性分析 183

8.2 函数方程的并行寻根法 185

8.2.1 定义 185

8.2.2 用逆拉格朗日插值的求根法 187

8.2.3 用逆埃尔米特插值的求根法 195

8.3 非线性递推计算并行性的分析 197

参考文献 202