11_数值计算_矩阵乘法_线性方程组求解

数值计算

  1. 矩阵
  2. 矩阵乘法
    1. 串行
    2. 并行
    3. 划分
    4. 直接并行实现
    5. 递归实现
    6. Cannon 算法
    7. Systolic 算法
  3. 求解线性方程组
    1. 高斯消去法
    2. 迭代方法
      1. 稀疏线性方程组及雅可比迭代
      2. 高斯-塞德尔松驰
      3. 红黑排序法
      4. 高阶差分法
      5. 过度松驰法

矩阵乘法-并行

  1. 使用n个处理器，
    1. 每个处理A阵的一行，与B阵的每一列相乘，得到C的一行。 或者：每个处理B阵的一列，与A阵的每一行相乘，得到C的一列
    2. 复杂度为O（n2）
  2. 使用n2个处理器
    1. 每个处理A的一行与B的一列相乘，得到C的一个点。
    2. 复杂度为O（n）。
  3. 使用n3个处理器
    1. 用n个处理器来完成A的一行与B的一列的乘积，然后要相加。
    2. 需要并行化内层的循环。
    3. 复杂度为O（logn）。注意不是O（1），也不是O（n）。

效率分析

矩阵乘法-划分

for (p = 0; p < s; p++)
    for (q = 0; q < s; q++) 
    {
        Cp,q = 0;                       /* clear elements of submatrix */
        for (r = 0; r < m; r++)       /* submatrix multiplication &*/
        Cp,q = Cp,q + Ap,r * Br,q;   /*add to accum. submatrix*/
    }

直接实现：

- 通信：
    - 每个从进程：收到一行和一列，以及要返回一个结果。有n^2个从进程
    - 所以tcomm=n^2（2tstartup+2ntdata)+n^2(tstartup+tdata）
    - 利用广播可以减少tstartup时间。
    - Tcomm=（tstartup+n^2tdata）+n^2（tstartup +tdata）
    - 时间主要消耗在数据返回上，因为tstartup 较大。
    - <b>用gather 表面上可以简化，实际上是一样的。</b>
- 计算：
    - Tcomp=2n
- 划分为子矩阵的复杂度分析，与之类似。

递归

Canon算法

    1. 所有块Aij(0≤i,j≤sqrt(p) - 1)向左循环移动i步；
    2. 所有块Bij(0≤i,j≤sqrt(p) - 1))向上循环移动j步；
  2. 所有处理器Pi,j做执行Ai,j和Bi,j的乘-加运算;
    1. A的每个块向左循环移动一步;
    2. B的每个块向上循环移动一步;
  4. 转2执行sqrt(p)-1次;

矩阵乘法-Systolic乘法

求解线性方程组