"利用矩阵乘法求所有点对间最短路径-并行计算(中科大讲义)"
在计算科学中，解决所有点对间最短路径问题是一个常见且重要的任务，尤其是在图论和网络分析中。这篇讲义讨论了一种利用矩阵乘法的方法来解决这个问题，并介绍了在并行计算环境中的实现策略。对于一个有向图G，由顶点V和边E组成，其边权矩阵W记录了每条边的权重，我们需要找到一个最短路径长度矩阵D，其中的元素dij表示从顶点vi到vj的最短路径长度。
计算原理如下：
1. 初始化：若vi和vj之间无直接边，d(1)ij设为无穷大（代表无法到达），对于同一顶点，d(1)ij设为0，因为没有路径长度。
2. 假设图中不存在负权有向回路，那么最终的最短路径dij可以通过d(n-1)ij得到，即经过最多n-1条边的最短路径。
3. 最优性原理：利用动态规划的思想，d(k)ij是通过中间节点集合{v1, v2, ..., vn}中至少有一个节点的最短路径，可以转换为矩阵乘法的形式，即d(k)ij等于d(k/2)il和d(k/2)lj的最小值之和，当将加法替换为乘法，最小值替换为求和时。
4. 应用矩阵乘法：通过不断进行矩阵乘法，从D1到D2，再到D4，以此类推，直到D2logn，即得到最短路径矩阵Dn。
讲义中还提到了SIMD-CC（Single Instruction Multiple Data - Cooperative Computing）架构上的并行算法，这是并行计算的一种模式，允许多处理单元同时执行相同的操作，但处理不同的数据。在并行计算领域，算法的设计和优化至关重要，因为它能够充分利用硬件资源，提高计算效率。
并行计算涉及多个主题，包括并行计算机系统结构模型、并行算法设计基础、基本通信操作、矩阵运算以及并行程序设计。这些主题涵盖了从理论到实践的各个方面，如并行机系统的SMP（Symmetric Multi Processing）、MPP（Massively Parallel Processing）和Cluster，以及并行算法设计过程，如并行算法的一般设计方法和技术。
在并行计算的第三篇中，讲解了并行数值算法，包括基本通信操作、稠密矩阵运算，如线性方程组的求解，以及快速傅里叶变换等。最后，第四篇关注并行程序设计，介绍了并行程序设计基础、编程模型以及分布式存储系统编程，同时还涵盖了并行程序设计环境和工具。
这篇讲义深入探讨了如何利用矩阵乘法解决图中所有点对间最短路径的问题，并结合并行计算的理论和实践，提供了一种高效的解决方案。
我的内容管理
展开
