矩阵-向量乘积

矩阵-向量乘积通常在共享内存机器上很容易并行化，方法是将矩阵按行分割成对应向量段的小条带。每个处理器随后计算其中一个条带的矩阵-向量乘积。 对于分布式内存机器，如果每个处理器仅在其内存中拥有向量的一部分段，可能会出现问题。根据矩阵的带宽，我们可能需要为向量的其他元素进行通信，这可能导致通信瓶颈。然而，许多稀疏矩阵问题源于仅相邻节点连接的网络。例如，有限差分或有限元问题产生的矩阵通常只涉及局部连接：矩阵元素a_{i,j}仅在变量i和j物理上接近时才非零。 在这种情况下，将网络或网格自然地细分为合适的块并将其分布在处理器上似乎是合理的。在计算Ap^{(i)}时，每个处理器需要相邻块中某些节点的p^{(i)}值。如果与这些相邻块的连接数远小于内部节点数，则通信时间可以与计算工作重叠。

更近期的方法中，**图划分**已成为处理具有非局部连接的一般问题的一种强大工具。考虑y \leftarrow Ax和矩阵A的（对称）无向图G。假设顶点i存储x_i, y_i以及所有j的非零a_{i,j}。让顶点i表示计算任务 y_i = \sum_j a_{i,j} x_j。我们可以将顶点i的权重设为计算y_i的操作数，边(i, j)的权重设为1，表示如果顶点i和j映射到不同处理器时发送x_j到顶点i的成本。一个好的图划分启发式算法会将G划分为对应于P个处理器的P个子集，使得：

• 各子集的顶点权重和近似相等，
• 跨越子集的边切割和最小化。

这确保了良好的负载均衡并最小化了通信。优秀的图划分软件包括Chaco[223]和METIS[259]（以及并行版本的ParMETIS）。

划分后，可以进一步进行优化以减少通信。例如，如果一个顶点子集包含多个到另一个子集的边，则可以将向量的相应元素打包成一条消息，使得每个处理器向另一个处理器发送不超过一条消息。关于分布式内存系统的实现方面的更详细讨论，请参见De Sturler和van der Vorst[111,112]以及Pommerell[369]。

高质量的并行算法已在软件包中实现，如Aztec[236]和PETSc[38]。这些软件可以通过本书的主页ETHOME获取。