矩阵链乘序问题的并行算法研究  

Research of Parallel Algorithm Solving the Matrix Chain Ordering Problem

作　　者：徐卫志[1] 王洪国[1] 杨海[1] 于惠[1] 

机构地区：[1]山东师范大学信息科学与工程学院,250014

出　　处：《信息技术与信息化》2007年第6期71-73,共3页Information Technology and Informatization

基　　金：山东省自然科学基金(Q2006G03)

摘　　要：本文在矩阵链相乘串行动态规划算法基础上,提出一种基于二维网孔结构的并行矩阵链相乘动态规划算法。该算法采用一个上三角结构的二维网孔结构,在O(n2)的时间内解决矩阵链相乘问题,而二维网孔比以往采用的PRAM模型更接近实际。This paper proposes a parallel algorithm which is based on dynamic programming to solve the matrix chain ordering problem. The algorithm runs on an upper triangular structure ofa 2D mesh in O（n） time. The 2D mesh structure is more realistic than the PRAM model.

关 键 词：矩阵链相乘 动态规划 二维网孔 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]