并行算法优化刚度矩阵装配

为了并行装配，先统计每个变量在各处理器局部所涉及的单元数量，再在每个处理器上利用局部分配到的单元装配形成整体刚度矩阵的一部分。之后，将各处理器上的部分矩阵累加形成整体刚度矩阵，在每个处理器上得到整个刚度矩阵中的连续若干行。最后，对各行中的元素按列号从小到大的顺序进行排序。

假设在每个进程的局部都形成了一个部分矩阵，将第k个进程上的局部矩阵记为Ak，Ak用CSR格式存储在valhbk、idxhbk、iptrhbk中。由于每个进程上最终只存储矩阵中给定的若干个行，所以在进程k上将valhbk、idxhbk、iptrhbk一共分成p段，记为valhbk，j、idxhbk，j、iptrhbk，j，j＝0～p－1，第j段对应于第k个部分矩阵连续的若干行。

在进行如上处理后，现在问题实际上就转化为要在进程k上对所有存储在valhbk，j、idxhbk，j、iptrhbk，j中的部分矩阵里的行进行叠加。为达到 这个目 的，在采用MPI来实现时，可以先通过全收集聚合函数MPI_Allgatherv来将所有valhbk，j、idxhbk，j、iptrhbk，j收集到进程j上，之后再在各个进程上进行各自的叠加过程。

在将所 有valhbk，j、idxhbk，j、iptrhbk，j收 集 到 进 程j上 时，假 设 用val、idx、iptr三个数组且采用CSR格式在局部存储整体刚度矩阵的各行，其中val逐行依次存储各个非零元素的值，idx依次存储与val中各个元素对应的列号，iptr记录各行中第一个非零元存储在val与idx中的起始位置。由于每个iptrhbk，j都是针对原来进程k中部分矩阵的，所以在收集到val、idx、iptr中时，需要重新计算iptr的值。同时，由于要对多个部分矩阵中的对应行进行叠加，所以需要引入额外的整型数组cbpos、cpos、cptr来链接属于同一个行的所有元素，这有助于对具有相同行列标号的元素值进行叠加，以得到全局矩阵中各个元素的实际值。

在经过以上操作后，已经形成了全局矩阵，并且每个进程上存储了应该存储的矩阵行，但现在每个矩阵行中所存储的元素是无序的。与13.3.2节类似，需要按照ICT预条件的要求将各行中的元素按列号从小到大的顺序进行存储。(www.xing528.com)

由于ICT预条件要求各行中的元素按列号从小到大的顺序进行存储，所以还需要对得到的矩阵进行处理。排序时，当然可以对各个行分别进行，对每个行中的元素采用各种各样的排序技术进行排序，但这样排序所花费的时间比较长。

同样地，先将CSR格式的矩阵转存为CSC格式，按列号从小到大进行存储，在同一列内，各行上的元素也按行号从小到大的顺序进行存储。与串行算法不同的是，全局矩阵是对称矩阵，得到的矩阵就已是满足要求的存储形式。但在并行计算时，还需要将CSC格式再次转存为CSR格式。

到目前为止，所考虑的装配算法实际上是每装配一次整体刚度矩阵，上述各个步骤都要依次进行。但可以发现，在当前的实际应用中，离散网格一直没有变化，所以虽然整体刚度矩阵在每次装配时得到的元素值会有所不同，但非零元结构并没有变化，从而非零元所在列号以及每行中第一个非零元的存储位置始终不变。这样，非零元所在列号与每行中第一个非零元的存储位置只需要在进行第一次装配时进行计算，以后直接使用就可以了。类似地，各个处理器上装配过程中所用到的其他整型数组所存储的信息也必然没有变化，所以也都只要在第一次装配时计算，以后直接重复利用就可以了。以这种方式进行操作，可以适度减少算法的时间复杂度。