if(i+p)and(i≠q)then (ib, P=aip]col+ai, q* sil (ii)b[i, g=-alip*sil+ ali, q]"col end if end for (1. 6for i=/ to n do forj=l to n de q[/=b end for end while (2)for i=l to Eigenvalue=a[i, i] end for End 122雅可比法求对称矩阵特征值的并行算法 串行雅可比算法逐次寻找非主对角元绝对值最大的元素的方法并不适合于并行计算。因 此,在并行处理中,我们每次并不寻找绝对值最大的非主对角元消去,而是按一定的顺序将 A中的所有上三角元素全部消去一遍,这样的过程称为一轮。由于对称性,在一轮中,A的 下三角元素也同时被消去一遍。经过若干轮,可使A的非主对角元的绝对值减少,收敛于 个对角方阵。具体算法如下 设处理器个数为p,对矩阵A按行划分为2p块,每块含有连续的m/2行向量,记 m=「n/p1,这些行块依次记为A4,…Ayp,并将A2与A2+存放与标号为i的处理器中 每轮计算开始,各处理器首先对其局部存储器中所存的两个行块的所有行两两配对进行 旋转变换,消去相应的非对角线元素。然后按图21.1所示规律将数据块在不同处理器之间 传送,以消去其它非主对角元素。 开始:(0,1)(2,3)(4,5)(6,7) 七步: 图11p=4时的雅可比算法求对称矩阵特征值的数据交换图if((i ≠ p) and (i ≠ q)) then (i)b[i, p]= a[i,p]*co1+ a[i,q]*si1 (ii)b[i, q]= - a[i,p]*si1+ a[i,q]*co1 end if end for (1.6)for i=1 to n do for j=1 to n do a[i,j]=b[i,j] end for end for end while (2)for i=1 to n do Eigenvalue[i]= a[i, i] end for End 1.2.2 雅可比法求对称矩阵特征值的并行算法 串行雅可比算法逐次寻找非主对角元绝对值最大的元素的方法并不适合于并行计算。因 此，在并行处理中，我们每次并不寻找绝对值最大的非主对角元消去，而是按一定的顺序将 A 中的所有上三角元素全部消去一遍，这样的过程称为一轮。由于对称性，在一轮中，A 的 下三角元素也同时被消去一遍。经过若干轮，可使 A 的非主对角元的绝对值减少，收敛于 一个对角方阵。具体算法如下： 设处理器个数为 p，对矩阵 A 按行划分为 2p 块，每块含有连续的 m/2 行向量，记 m = n / p ，这些行块依次记为 A0,A1, …,A2p-1，并将 A2i 与 A2i+1 存放与标号为 i 的处理器中。 每轮计算开始，各处理器首先对其局部存储器中所存的两个行块的所有行两两配对进行 旋转变换，消去相应的非对角线元素。然后按图 21.1 所示规律将数据块在不同处理器之间 传送，以消去其它非主对角元素。 开 始 ：（0，1）（2，3）（4，5）（6，7） 第一步 ：（0，3）（1，5）（2，7）（4，6） 第二步 ：（0，5）（3，7）（1，6）（2，4） 第三步 ：（0，7）（5，6）（3，4）（1，2） 第四步 ：（0，6）（7，4）（5，2）（3，1） 第五步 ：（0，4）（6，2）（7，1）（5，3） 第六步 ：（0，2）（4，1）（6，3）（7，5） 第七步 ：（0，1）（2，3）（4，5）（6，7） 0 1 2 3 4 5 6 7 图 1.1 p=4 时的雅可比算法求对称矩阵特征值的数据交换图