文档介绍：并行计算
中国科学技术大学计算机科学与技术系
国家高性能计算中心(合肥)
2003年9月
2017/11/10
1
现代密码学理论与实践之五
第三篇并行数值算法 第八章基本通讯操作 第九章稠密矩阵运算 第十章线性方程组的求解 第十一章快速傅里叶变换
2017/11/10
2
现代密码学理论与实践之五
第十章线性方程组的求解 三角形方程组的求解 三对角方程组的求解 稠密线性方程组的求解 稀疏线性方程组的求解
2017/11/10
3
现代密码学理论与实践之五
三角形方程组的求解 基本术语 上三角方程组的求解
2017/11/10
4
现代密码学理论与实践之五
基本术语
线性方程组的定义和符号
a1,1x1 + a1,2x2 + …+ a1,nxn = b1
a2,1x1 + a2,1x2 + …+ a2,nxn = b2
an,1x1 + an,1x2 + …+ an,nxn = bn
记为 AX=b
2017/11/10
5
现代密码学理论与实践之五
三角形方程组的求解 基本术语 上三角方程组的求解
2017/11/10
6
现代密码学理论与实践之五
上三角方程组的求解
上三角方程组的回代解法并行化
(1)SISD上的回代算法
Begin
(1)for i=n downto 1 do
()xi=bi/aii
()for j=1 to i-1 do
bj=bj-ajixi
aji=0
endfor
endfor
End
可并行化
2017/11/10
7
现代密码学理论与实践之五
上三角方程组的求解
上三角方程组的回代解法并行化
(2)SIMD-CREW上的并行回代算法
- 划分: p个处理器行循环带状划分
- 算法
Begin
for i=n downto 1 do
xi=bi/aii
for all Pj, where 1≤j≤p do
for k=j to i-1 step p do
bk=bk-akixi
aki=0
endfor
endfor
endfor
End // p(n)=n, t(n)=n
2017/11/10
8
现代密码学理论与实践之五
第十章线性方程组的求解 三角形方程组的求解 三对角方程组的求解 稠密线性方程组的求解 稀疏线性方程组的求解
2017/11/10
9
现代密码学理论与实践之五
三对角方程组的求解 直接求解法 奇偶规约法
2017/11/10
10
现代密码学理论与实践之五