This paper discusses the computation of matrix chain products of the form M1 × M22 × ··· × Mn where Mi's are matrices. The order in which the matrices are computed affects the number of operations. A sufficient condition about the association of the matrices in the optimal order is presented. An O(n) algorithm to find an order of computation which takes less than 25 percent longer than the optimal time Topt is also presented. In most cases, the algorithm yields the optimal order or an order which takes only a few percent longer than Topt (less than 1 percent on the average).
An O(n) algorithm for determining a near-optimal computation order of matrix chain products
The Latest from CACM
Shape the Future of Computing
ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.
Get InvolvedCommunications of the ACM (CACM) is now a fully Open Access publication.
By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.
Learn More
Join the Discussion (0)
Become a Member or Sign In to Post a Comment