a[k, i]=temp[k] (vi)if(sum[0]>p)then p= sum[0] end if nd for nd while (2)for i=l to n do sF=sta小*叫 end for BU]=sqrt[suI if([0,]*a[0, j]<)then BUF-BU] endif nd fe End 上述算法的一轮迭代需进行n(n-ly2次旋转变换,若取一次乘法或一次加法运算时间为 个单位时间,则一次旋转变换要做3次内积运算而消耗6n个单位时间:与此同时,两列 元素进行正交计算还需要12n个单位时间,所以奇异值分解的一轮计算时间复杂度为 n(n-1)2*(12n+6n)=9m(n-1)nF=O(n) 132求对称矩阵特征值的单侧旋转法的并行计算 在求对称矩阵特征值的单侧旋转法的计算中,主要的计算是矩阵的各列正交化过程为 了进行并行计算,我们对n阶对称矩阵A按行划分为p块p为处理器数),每块含有连续的q 行向量,这里q=m,第i块包含A的第ⅸ×q,…(计+1)×q-1行向量,其数据元素被分配到 第i号处理器上(=0,1,…p-1)。E矩阵取阶数为n的单位矩阵l,按同样方式进行数据划分, 每块含有连续的q行向量。对矩阵A的每一个列向量而言,它被分成P个长度为q的子向 量,分布于p个处理器之中,它们协同地对各列向量做正交计算。在对第i列与第j列进行 正交计算时,各个处理器首先求其局部存储器中的q维子向量[、[小、[小的内积,然后 通过归约操作的求和运算求得整个n维向量对[、[、U的内积并广播给所有处理器, 最后各处理器利用这些内积对其局部存储器中的第i列及第j列q维子向量的元素做正交计 算。算法21.7按这样的方式对所有列对正交化一次以完成一轮运算,重复进行若干轮运算, 直到迭代收敛为止。在各列正交后,编号为0的处理器收集各处理器中的计算结果,由0号 处理器计算矩阵的特征值.具体算法框架描述如下: 算法217求对称矩阵特征值的并行单侧旋转算法 输入:对称矩阵A,精度e 输出:对称矩阵A的特征值存于向量B中 对所有处理器 my_ rank( my rank=0…,p-1)同时执行如下的算法 (a)while(not convergence)de (1)k=0a[k,i]= temp[k] end for (vi) for k=1 to n do e[k,i]= temp1[k] end for (vii) if (│sum[0]│>p) then p=│sum[0] │ end if end if end for end for end while (2)for i=1 to n do su=0 for j=1 to n do su=su+a[j,i]* a[j,i] end for B[j]=sqrt[su] if (e[0,j]*a[0,j]<0) then B[j]= - B[j] endif end for End 上述算法的一轮迭代需进行 n(n-1)/2 次旋转变换，若取一次乘法或一次加法运算时间为 一个单位时间，则一次旋转变换要做 3 次内积运算而消耗 6n 个单位时间；与此同时，两列 元素进行正交计算还需要 12n 个单位时间，所以奇异值分解的一轮计算时间复杂度为 n(n-1)/2*(12 n +6n)= 9n(n-1) n=O(n 3 )。 1.3.2 求对称矩阵特征值的单侧旋转法的并行计算 在求对称矩阵特征值的单侧旋转法的计算中, 主要的计算是矩阵的各列正交化过程.为 了进行并行计算, 我们对 n 阶对称矩阵 A 按行划分为 p 块(p 为处理器数)，每块含有连续的 q 行向量，这里 q=n/p，第 i 块包含 A 的第 i×q, …,(i+1)×q-1 行向量，其数据元素被分配到 第 i 号处理器上(i=0,1,…,p-1)。E 矩阵取阶数为 n 的单位矩阵 I，按同样方式进行数据划分， 每块含有连续的 q 行向量。对矩阵 A 的每一个列向量而言，它被分成 p 个长度为 q 的子向 量，分布于 p 个处理器之中，它们协同地对各列向量做正交计算。在对第 i 列与第 j 列进行 正交计算时，各个处理器首先求其局部存储器中的 q 维子向量[i,j]、[i,i]、[j,j]的内积，然后 通过归约操作的求和运算求得整个 n 维向量对[i,j]、[i,i]、[j,j]的内积并广播给所有处理器， 最后各处理器利用这些内积对其局部存储器中的第 i 列及第 j 列 q 维子向量的元素做正交计 算。算法 21.7 按这样的方式对所有列对正交化一次以完成一轮运算，重复进行若干轮运算， 直到迭代收敛为止。在各列正交后, 编号为 0 的处理器收集各处理器中的计算结果，由 0 号 处理器计算矩阵的特征值. 具体算法框架描述如下： 算法 21.7 求对称矩阵特征值的并行单侧旋转算法 输入：对称矩阵 A，精度 e 输出：对称矩阵 A 的特征值存于向量 B 中 Begin 对所有处理器 my_rank(my_rank=0,…, p-1)同时执行如下的算法： (a) while (not convergence) do (1)k=0