International Journal of Computer
Trends and Technology

Research Article | Open Access | Download PDF

Volume 23 | Number 1 | Year 2015 | Article Id. IJCTT-V23P115 | DOI : https://doi.org/10.14445/22312803/IJCTT-V23P115

Matrix-Chain Multiplication Using Greedy and Divide-Conquer approach

Raghav Lakhotia, Sanjeev Kumar, Rishabh Sood, Harmeet Singh, Javaid Nabi

Citation :

Raghav Lakhotia, Sanjeev Kumar, Rishabh Sood, Harmeet Singh, Javaid Nabi, "Matrix-Chain Multiplication Using Greedy and Divide-Conquer approach," International Journal of Computer Trends and Technology (IJCTT), vol. 23, no. 1, pp. 65-72, 2015. Crossref, https://doi.org/10.14445/22312803/IJCTT-V23P115

Abstract

Matrix Chain Multiplication is a famous application of optimization problem and is used widely in signal processing and network industry for routing. The crux of the solution lies in minimizing the cost or minimizing the number of arithmetic operations required to multiply out the matrices. A top-down dynamic approach is a well-known solution for this problem which helps to determine the minimal cost required to perform the required multiplication of the matrices. The dynamic solution bears time complexity of the order ? .The authors in this paper present a greedy approach to find the optimal computation order of matrix chain multiplication. This approach provides the minimum cost required to compute the required result in a runtime of the order ? as compared to the dynamic approach runtime of ? . Although the end result i.e. the matrix obtained after the chain multiplication provided by theapproaches, the proposed approach and the dynamic approach is the same.

Keywords

Matrix Chain Multiplication, Dynamic Approach, Greedy Approach.

References

[1] Thomas H. Cormen, Charles E. Leiserson , Ronald L. Rivest, Clifford Stein, Introduction To Algorithms, The MIT Press.
[2] Aho, A.V., Hopcroft, J.E., and Ullman, J.DThe Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.
[3] Chin, F.Y. “An O(n) algorithm for determining a near optimal computation order of matrix chain product.”Cemmun. ACM 21, 7 July1978, pp. 544-549.
[4] Nicola Santoro, “Chain Multiplication of Matrices of Approximately or exactly the same size.”, February 1984 Volume 27 Number 2.
[5] Chee Yap, “A Real Elementary Approach to the MasterRecurrence and Generalizations.”, 8th Annual Conference, TAMC 2011, Tokyo, Japan.
[6] Sanjeev Kumar, RaghavLakhotia, RishabhSood, HarmeetSingh– “Compare Dynamic Programming and Greedy Matrix Chain Multiplication Algorithm” , available at url - http:// mcmssnk. rhcloud.com/compareAlgo.html
[7] Muhammad Hafeez, Muhammad Younus, “An Effective Solution for Matrix Parenthesization Problem through Parallelization”, International Journal of Computers, Issue 1, Vol. 1, 2007.
[8] T. C. Hu, M. T. Shirig, “Computation of Matrix ChainProducts”, Stanford University, September 1981.
[9] Deimel, L.E., and Lampe T.A. “An invariance theorem concerning optimal computation of matrix chain products.” Rep. TR79-14, North Carolina State Univ., Raleigh, NC, 1979.
[10]Sadashiva S. Godbole “An Efficient computation of matrix chain products”. IEEE Trans. Comput. C-22, 9 Sept. 1973, 864-866.