An efficient parallel algorithm for the matrix-chain-product problem

作     者：Ramanan, P 

作者机构：Department of Computer Science Wichita State University Wichita KS 67260-0083 United States 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1996年第25卷第4期

页      面：874-893页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：matrix-chain product polygon triangulation dynamic programming parallel algorithm PRAM model processor-time complexity 

摘      要：We consider the problem of finding an optimal order of computing a matrix-chain product. This problem can be solved using dynamic programming in O(n(3)) sequential time, but the best sequential algorithm known for this problem runs in O(n log n) time. A general technique for parallelizing a class of dynamic-programming algorithms leads to an algorithm that runs in O (n(6)/log n) time on a concurrent-read exclusive-write parallel random-access machine (CREW PRAM) with O (n(6)/log n) processors. The best parallel algorithm previously known runs in O(log(3) n) time using O(n(2)/log(3) n) processors. We present an algorithm that runs in O(log(4) n) time on a CREW PRAM with n processors.