b0=b[amax end for 6)用A! gather操作将各个处理器中计算出的特征向量的分量的新值组合并广播到 所有处理器中 (7)diff=max-oldmax, oldmaxmax end while 若各取一次乘法和加法运算时间、一次除法运算时间、一次比较运算时间为一个单位时 间,一轮迭代的计算时间为m+2m;一轮迭代中,各处理器做一次归约操作,通信量为1, 次扩展收集操作,通信量为m,则通信时间为4,(√p-1)+(m+1)n(p-1)。因此乘幂法的 轮并行计算时间为Tn=m+2m+4(√P-1)+(m+1xn(P-1) MPI源程序请参见所附光盘。 12求对称矩阵特征值的雅可比法 121雅可比法求对称矩阵特征值的串行算法 若矩阵A=[a是n阶实对称矩阵,则存在一个正交矩阵U,使得 UAU=D 其中D是一个对角矩阵,即 0 这里λ(=1,2…,m)是A的特征值,U的第i列是与λ对应的特征向量。雅可比算法主要是通 过正交相似变换将一个实对称矩阵对角化,从而求出该矩阵的全部特征值和对应的特征向 量。因此可以用一系列的初等正交变换逐步消去A的非对角线元素,从而使矩阵A对角化。 设初等正交矩阵为R(PqO,其(pP)(q,q)位置的数据是cosO,(p,q)(qp)位置的数据分别是 sinO和 sinA(p≠q),其它位置的数据和一个同阶数的单位矩阵相同。显然可以得到 不妨记B=R(PqO)AR(PqO,如果将右端展开,则可知矩阵B的元素与矩阵A的元素 之间有如下关系 bpp=appcos20+aggsin20+apgsin20 bpg=((aqg-app)sin20)/2+apg cos bpi=apjcoso+aa sine bip=aip cose+ aigsine bi=ajr 其中1≤,j≤n且≠Pq。因为A为对称矩阵,R为正交矩阵,所以B亦为对称矩阵 若要求矩阵B的元素b=0,则只需令(aq-ap)sin2)2+apqc0s20=0,即:b[i] =b[i]/max end for (6)用 Allgather 操作将各个处理器中计算出的特征向量的分量的新值组合并广播到 所有处理器中 (7)diff=max-oldmax, oldmax=max end while End 若各取一次乘法和加法运算时间、一次除法运算时间、一次比较运算时间为一个单位时 间，一轮迭代的计算时间为 mn+2m；一轮迭代中，各处理器做一次归约操作，通信量为 1， 一次扩展收集操作，通信量为 m，则通信时间为 4t ( p −1) + (m +1)tw( p −1) s 。因此乘幂法的 一轮并行计算时间为 T = mn + 2m + 4t ( p −1) + (m +1)tw(p −1) p s 。 MPI 源程序请参见所附光盘。 1.2 求对称矩阵特征值的雅可比法 1.2.1 雅可比法求对称矩阵特征值的串行算法 若矩阵 A=[aij]是 n 阶实对称矩阵，则存在一个正交矩阵 U，使得 U TAU=D 其中 D 是一个对角矩阵，即               = n D           0 0 0 0 0 0 2 1 这里 λi (i=1,2,…,n)是 A 的特征值，U 的第 i 列是与 λi 对应的特征向量。雅可比算法主要是通 过正交相似变换将一个实对称矩阵对角化，从而求出该矩阵的全部特征值和对应的特征向 量。因此可以用一系列的初等正交变换逐步消去 A 的非对角线元素，从而使矩阵 A 对角化。 设初等正交矩阵为 R(p,q,θ)，其(p,p)( q,q)位置的数据是 cosθ，(p, q)( q, p)位置的数据分别是 -sinθ 和 sinθ(p ≠ q)，其它位置的数据和一个同阶数的单位矩阵相同。显然可以得到： R(p,q,θ) TR(p,q,θ)=In 不妨记 B= R(p,q,θ) TAR(p,q,θ)，如果将右端展开，则可知矩阵 B 的元素与矩阵 A 的元素 之间有如下关系： bpp = appcos2θ+aqqsin2θ+apqsin2θ bqq = appsin2θ+aqq cos2θ-apqsin2θ bpq = ((aqq -app)sin2θ)/2+apq cos2θ bqp = bpq bpj= apjcosθ+aqjsinθ bqj = -apjsinθ +aqjcosθ bip= aipcosθ+aiqsinθ biq= -aipsinθ +aiqcosθ bij= aij 其中 1 ≤ i, j ≤ n 且 i,j ≠ p,q。因为 A 为对称矩阵，R 为正交矩阵，所以 B 亦为对称矩阵。 若要求矩阵 B 的元素 bpq =0，则只需令 ((aqq -app)sin2θ)/2+apq cos2θ=0，即：