An Efficient Parallel Algorithm for the Matrix-Chain-Product Problem
Prakash V. Ramanan · SIAM Journal on Computing · 1996
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(\log ^2 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.