A fast sequential algorithm for the matrix chain ordering problem. (21st June 2021)

• Record Type: Journal Article
• Authors: Lacmou Zeutouo, Jerry; Kengne Tchendji, Vianney; Myoupo, Jean Frédéric
• Is Part Of: Concurrency and computation. Volume 33:Number 24(2021)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2021-06-21
• Subjects: coarse‐grained multicomputer -- dynamic programming -- MCOP -- quadrangle inequality -- TCP; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.6445
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: This article presents a fast sequential algorithm for the matrix chain ordering problem. Our solution is based on Yao's sequential algorithm that solves this problem in 𝒪 ( n 2 ) time by reducing the total number of distinct subproblems to be performed. We solve them fastly by avoiding some unnecessary computations. Our strategy consists in organizing the evaluation of the subproblems according to their dependencies instead of their precedence order as in the previous solutions. In many cases, our solution runs in 𝒪 ( n ) time. An experimental study is conducted to benchmark the performance of our algorithm by measuring the average of the results obtained on five random data sets. This shows that our algorithm is × 18.93 faster than Yao's sequential algorithm and × 5.07 faster than the previous best CGM‐based parallel solutions on 32 processors.