高阶矩阵相乘算法的研究
高阶矩阵相乘算法的研究,开发研究与设计技术,
杨永娟 蒋 群 约2633字
摘要:本文通过对于高阶矩阵相乘算法的串并行比较，尤其是MPI技术下的并行算法的探讨，得出在MPI环境下进行高阶矩阵相乘的可行性、简单性、必要性。
关键词:高阶矩阵;并行算法;MPI技术
中图分类号:TP311文献标识码:A文章编号:1009-3044(2007)16-31080-01
The Research of High Matrix Multiplication's Algorithm
YANG Yong-juan,JIANG Qun
(Anhui University of Science & Technology Computer Science and
Technology,Huainan 232001,China)
Abstract:Through the comparison between serial and parallel multiply arithmetic
of high-level matrix, especially the study on parallel arithmetic through MPI method,
the author concludes that it is possible, simple and necessary to multiply high-level
matrix under MPI environment.
Key words:High-level Matrix;Parallel Arithmetic;MPI Method
1 绪言
我们经常会遇到大型的高阶矩阵的有关计算，尤其是两矩阵相乘更为常见。在应用中常用矩阵相乘的定义算法对其进行计算，即通常所说的串行算法。这个算法用到了大量的循环和相乘运算，这使得算法效率不高。而矩阵相乘的计算效率很大程度上的影响了整个程序的运行速度，所以对矩阵相乘算法进行一些改进是必要的。随着大型的具有多处理机的并行计算机系统的发展，一些大型计算可以构造相应的并行计算方法进行并行处理，从而减少机器的工作单元，提高计算效率，节约资源，这也就是所要研究的并行算法。
在并行机上实现矩阵相乘必须要研究相关的并行算法，目前矩阵相乘并行算法有许多种，它们主要取决于矩阵的划分，根据不同的划分有行列划分法、行行划分法、列列划分法等许多技术，下面主要采用行列划分法进行矩阵相乘的串并行运算比较。
设矩阵Am×k与Bk×n，积矩阵为Cm×n。则Cm×n=Am×k×Bk×n。
每个元素Cij=?Ait×Btj(i=1,„,m;j=1,„,n)
2 矩阵乘法的串行算法
在java串行中很好解决这个问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
，直接用三个循环即可算出结果:
for (int i=0;i
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
此并行算法思想是:将一高阶矩阵分解成除数小得多的矩阵相乘的子问题，然后交给各节点机实现，最后进行简单的相加得到最终的结果。
假设现有两个4×4的矩阵进行相乘，则为，
将上面的公式替换为:
按照矩阵乘法计算即为:
C11=A11×B11+A12×B21
C12=A11×B12+A12×B22
C21=A21×B11+A22×B22
C22=A21×B12+A22×B22
此时由刚才的4×4阶的两个大矩阵相乘，改为2×2的8个小矩阵相乘与四个2×2的四个小矩阵相加，可以将各8个小矩阵分配给不同的节点然后利用不同的处理机进行并行运算，这样就可以提高机器的利用效率，最后再加所有的结果交给一个主控机由它进行合并。这时它的复杂性就很少了，若阶数若高，同时处理机的数目越大的话，这种并行计算的优势将体现的更多～但这里还要注意的是，不能因为追求并行性而盲目加大处理器数目，因为各个处理器之间的通讯也是需要代价的。
3.2 并行算法的MPI流程图
假设并行机的处理器有p个:
图1 并行算法图
在刚开始时需要将A、B矩阵的各个子矩阵分别传递给各个不同的处理器，因此需要顺序做，而一旦传送完毕后，各个处理器就可以自己做自己的矩阵相乘运算了，即图中所标的并行处理开始处，直到各个部分处理完毕后，再进行最后的合并。
4 结论
通过上述串行算法与并行算法的比较，可以看出并行算法的明显优势，它具有巨大的数值计算和数据处理能力。现实生活中有许多情况都可以利用并行算法来解决，它能够被广泛地应用于各行各业中。特别是现在的MPI技术，更使得人们编写并行程序越来越简单。
参考文献:
[1]朱旭.矩阵计算的并行算法和实现[J].工程数学学报,1997,14(2):99-103.
[2]李小洲,李庆华.矩阵相乘Cannon并行算法在工作站机群上的实现[J].计算机工程,vol.14 No.8 Aug.2004:49-51.
[3]彭雷,朱永芬,戴光明.PVM下矩阵相乘并行算法的研究与实现[J].微机发展,2004,28(6):102-103.
[4][美]科尔曼(Corrmen,T.H)(算法导论(第2版影印版)[M].北京:高等教育出版社,2002.
[5]Wikinson B,Allen M.陆鑫达等译.并行程序设计[M].北京:机械工业出版社,2002.
[6]郁志辉.高性能计算并行编程技术-MPI并行程序设计[M].北京:清华大学出版社,2001.
注:“本文中所涉及到的图表、公式注解等形式请以PDF格式阅读原文。”
浙公网安备 33021202002483