6矩阵运算 矩阵运算是数值计算中最重要的一类运算特别是在线性代数和数值分析中它是一种最 基本的运算。本章讨论的矩阵运算包括矩阵转置、矩阵向量相乘、矩阵乘法、矩阵分解以及 方阵求逆等。在讨论并行矩阵算法时分三步进行:①算法描述及其串行算法:②算法的并行 化及其实现算法框架以及简单的算法分析:③算法实现的MPI源程序,以利于读者实践操 11矩阵转置 111矩阵转置及其串行算法 对于一个n阶方阵A=[o,将其每一下三角元素a(>)沿主对角线与其对称元素a互 换就构成了转置矩阵A。假设一对数据的交换时间为一个单位时间,则下述矩阵转置 Matrix Transposing)算法18.1的运行时间为(m2-n)/2=O(m2) 算法18.1单处理器上矩阵转置算法 输入:矩阵Anxn 输出:矩阵Anxn的转置Anxn for i=2 to n do to i-I do 交换叫和a[, endOr endo End 图1.1子块转置 112矩阵转置并行算法 此处主要讨论网孔上的块棋盘划分( Block-Checker Board Partitioning,又称为块状划分) 的矩阵转置算法,它对循环棋盘划分( yclic- Checker Board Partitioning)也同样适用。另外, 超立方上块棋盘划分的矩阵转置算法可参见文献[l 实现矩阵的转置时,若处理器个数为p,且它们的编号依次是0,1,…p1,则将n阶矩1. 6 矩阵运算 矩阵运算是数值计算中最重要的一类运算,特别是在线性代数和数值分析中,它是一种最 基本的运算。本章讨论的矩阵运算包括矩阵转置、矩阵向量相乘、矩阵乘法、矩阵分解以及 方阵求逆等。在讨论并行矩阵算法时分三步进行：①算法描述及其串行算法；②算法的并行 化及其实现算法框架以及简单的算法分析；③算法实现的 MPI 源程序，以利于读者实践操 作。 1.1 矩阵转置 1.1.1 矩阵转置及其串行算法 对于一个 n 阶方阵 A=[aij]，将其每一下三角元素 aij (i>j)沿主对角线与其对称元素 aji 互 换就构成了转置矩阵 A T。假设一对数据的交换时间为一个单位时间，则下述矩阵转置(Matrix Transposing)算法 18.1 的运行时间为(n 2 -n)/2=O(n 2 )。 算法 18.1 单处理器上矩阵转置算法 输入：矩阵 An×n 输出：矩阵 An×n 的转置 A T n×n Begin for i=2 to n do for j=1 to i-1 do 交换 a[i,j]和 a[j,i] endfor endfor End A41 P12 A42 P13 A43 P14 A12 P1 A13 P2 A14 P3 A11 P0 A21 P4 A23 P6 A24 P7 A22 P5 A31 P8 A32 P9 A34 P11 A33 P10 A44 P15 图 1.1 子块转置 1.1.2 矩阵转置并行算法 此处主要讨论网孔上的块棋盘划分(Block-Checker Board Partitioning，又称为块状划分) 的矩阵转置算法，它对循环棋盘划分(Cyclic-Checker Board Partitioning)也同样适用。另外， 超立方上块棋盘划分的矩阵转置算法可参见文献[1]。 实现矩阵的转置时，若处理器个数为 p，且它们的编号依次是 0,1, …,p-1，则将 n 阶矩