(1.3) MATRIX TRANSPOSITION(Q)/由于算法18.11对A进行QR分解 只得到Q,因而要使用算法18.1对矩阵Q进行转置,得到(Q1)=(Q)=Q* (14M= MATRIX PRODUCT(RQ)陴*算法185将矩阵RQ相乘,得到新的 A矩阵* (1. 5for il to n do if(a[i>p)then p[ end if d fc end for end while (2)for i=l to n do Eigenvalue=[i, i d for 显然,QR分解求矩阵特征值算法的一轮时间复杂度为QR分解、矩阵转置和矩阵相乘 算法的时间复杂度之和。 142QR方法求一般矩阵全部特征值的并行算法 并行QR分解求矩阵特征值的思想就是反复运用并行QR分解和并行矩阵相乘算法进行 迭代,直到矩阵序列{41}收敛于一个上三角矩阵或块上三角矩阵为止。具体的并行算法描 述如下 算法219QR方法求一般矩阵全部特征值的并行算法 输入:矩阵Anxm,单位矩阵Q, 输出:矩阵特征值 Eigenvalue 对所有处理器 my rank( my rank=0,…,p-1)同时执行如下的算法 (a)while((p>e)and(count<1000)do (1)p=0, /*对矩阵A进行QR分解 (2)if( my rank=0)then/0号处理器* Turnningtransform()/*旋转变换* (i)将旋转变换后的A和Q的第j行传送到第1号处理器 (22)将旋转变换后的A和Q的第m-1行传送到第1号处理器 nd if (3)if( my ran>0)and( my rank<(p-1))then/中间处理器*/ (3. 1)forj=0 to my rank*m-1 do (i)接收左邻处理器传送来的A和Q子块中的第j行 (iifor i=0 to m-I do*/ (1.3)MATRIX_TRANSPOSITION(Q) /*由于算法 18.11 对 A 进行 QR 分解 只得到 Q -1，因而要使用算法 18.1 对矩阵 Q -1 进行转置，得到（Q -1）T=( Q -1 ) -1=Q*/ (1.4)A=MATRIX_PRODUCT(R,Q) /*算法 18.5 将矩阵 RQ 相乘，得到新的 A 矩阵 */ (1.5)for i=1 to n do for j=1 to i-1do if (│a[i,j]│> p) then p=│a[i,j]│ end if end for end for end while (2) for i=1 to n do Eigenvalue[i]=a[i,i] end for End 显然，QR 分解求矩阵特征值算法的一轮时间复杂度为 QR 分解、矩阵转置和矩阵相乘 算法的时间复杂度之和。 1.4.2 QR 方法求一般矩阵全部特征值的并行算法 并行 QR 分解求矩阵特征值的思想就是反复运用并行 QR 分解和并行矩阵相乘算法进行 迭代，直到矩阵序列 Ai 收敛于一个上三角矩阵或块上三角矩阵为止。具体的并行算法描 述如下： 算法 21.9 QR 方法求一般矩阵全部特征值的并行算法 输入：矩阵 An×n,单位矩阵 Q，ε 输出：矩阵特征值 Eigenvalue Begin 对所有处理器 my_rank(my_rank=0,…, p-1)同时执行如下的算法: (a) while ((p>ε) and (count<1000)) do (1)p=0 , count = count +1 /* 对矩阵 A 进行 QR 分解*/ (2)if(my_rank=0) then/*0 号处理器*/ (2.1)for j=0 to m-2 do (i)for i=j+1 to m-1 do Turnningtransform( ) /*旋转变换*/ end for (ii)将旋转变换后的 A 和 Q 的第 j 行传送到第 1 号处理器 end for (2.2)将旋转变换后的 A 和 Q 的第 m-1 行传送到第 1 号处理器 end if (3)if ((my_rank>0) and (my_rank<(p-1))) then /*中间处理器*/ (3.1)for j=0 to my_rank*m-1 do (i)接收左邻处理器传送来的 A 和 Q 子块中的第 j 行 (ii)for i=0 to m-1 do