Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices

Faouzi Ben Charrada; Sana Ezouaoui; Zaher Mahjoub

RAIRO - Operations Research - Recherche Opérationnelle (2011)

  • Volume: 45, Issue: 1, page 1-16
  • ISSN: 0399-0559

Abstract

top
This paper addresses a combinatorial optimization problem (COP), namely a variant of the (standard) matrix chain product (MCP) problem where the matrices are square and either dense (i.e. full) or lower/upper triangular. Given a matrix chain of length n, we first present a dynamic programming algorithm (DPA) adapted from the well known standard algorithm and having the same O(n3) complexity. We then design and analyse two optimal O(n) greedy algorithms leading in general to different optimal solutions i.e. chain parenthesizations. Afterwards, we establish a comparison between these two algorithms based on the parallel computing of the matrix chain product through intra and inter-subchains coarse grain parallelism. Finally, an experimental study illustrates the theoretical parallel performances of the designed algorithms.

How to cite

top

Ben Charrada, Faouzi, Ezouaoui, Sana, and Mahjoub, Zaher. "Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices." RAIRO - Operations Research - Recherche Opérationnelle 45.1 (2011): 1-16. <http://eudml.org/doc/275071>.

@article{BenCharrada2011,
abstract = {This paper addresses a combinatorial optimization problem (COP), namely a variant of the (standard) matrix chain product (MCP) problem where the matrices are square and either dense (i.e. full) or lower/upper triangular. Given a matrix chain of length n, we first present a dynamic programming algorithm (DPA) adapted from the well known standard algorithm and having the same O(n3) complexity. We then design and analyse two optimal O(n) greedy algorithms leading in general to different optimal solutions i.e. chain parenthesizations. Afterwards, we establish a comparison between these two algorithms based on the parallel computing of the matrix chain product through intra and inter-subchains coarse grain parallelism. Finally, an experimental study illustrates the theoretical parallel performances of the designed algorithms.},
author = {Ben Charrada, Faouzi, Ezouaoui, Sana, Mahjoub, Zaher},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {combinatorial optimization; dynamic programming; gree-dy algorithm; matrix chain product; parallel computing; greedy algorithm},
language = {eng},
number = {1},
pages = {1-16},
publisher = {EDP-Sciences},
title = {Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices},
url = {http://eudml.org/doc/275071},
volume = {45},
year = {2011},
}

TY - JOUR
AU - Ben Charrada, Faouzi
AU - Ezouaoui, Sana
AU - Mahjoub, Zaher
TI - Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2011
PB - EDP-Sciences
VL - 45
IS - 1
SP - 1
EP - 16
AB - This paper addresses a combinatorial optimization problem (COP), namely a variant of the (standard) matrix chain product (MCP) problem where the matrices are square and either dense (i.e. full) or lower/upper triangular. Given a matrix chain of length n, we first present a dynamic programming algorithm (DPA) adapted from the well known standard algorithm and having the same O(n3) complexity. We then design and analyse two optimal O(n) greedy algorithms leading in general to different optimal solutions i.e. chain parenthesizations. Afterwards, we establish a comparison between these two algorithms based on the parallel computing of the matrix chain product through intra and inter-subchains coarse grain parallelism. Finally, an experimental study illustrates the theoretical parallel performances of the designed algorithms.
LA - eng
KW - combinatorial optimization; dynamic programming; gree-dy algorithm; matrix chain product; parallel computing; greedy algorithm
UR - http://eudml.org/doc/275071
ER -

References

top
  1. [1] A.K. Chandra, Computing matrix products in near-optimal time. IBM Research Report, RC 5625 (1975). 
  2. [2] F.Y. Chin, An O(n) algorithm for determining a near-optimal computation order of matrix chain products. Commun. ACM21 (1978) 544–549. Zbl0377.15005MR497383
  3. [3] T.H. Cormen, C.E. Leicerson, R.L. Rivest and C. Stein, Introduction à l'Algorithmique. Dunod (2002). Zbl1158.68539
  4. [4] M. Cosnard and D. Trystram, Algorithmes et Architectures Parallèles. InterEditions (1993). 
  5. [5] H. El-Rewini and M. Abd-El-Bar, Advanced Computer Architecture and Parallel Processing. Wiley (2005). 
  6. [6] S. Ezouaoui, F. Ben Charrada and Z. Mahjoub, O(n) instances of the matrix chain product problem solved in linear time, in Proc. of ROADEF'09, Nancy, France (2009). Zbl1216.90071
  7. [7] S.S. Godbole, An efficient computation of matrix chain products. IEEE Trans. Comput. C-22 (1973) 864–866. Zbl0483.68041
  8. [8] T.C. Hu and M.T. Shing, Computation of matrix chain products. Part I. SIAM J. Comput.11 (1982) 362–373. Zbl0483.68041MR652909
  9. [9] T.C. Hu and M.T. Shing, Computation of matrix chain products. Part II. SIAM J. Comput.13 (1984) 229–251. Zbl0542.68028MR739987
  10. [10] V. Kumar, A. Grama, A. Gupta and G. Karypis, Introduction to Parallel Computing – Design and Analysis of Algorithms. The Benjamin/Cummings Pub. Co. (1994). Zbl0861.68040
  11. [11] S. Lakshmivarahan and S.K. Dhall, Analysis and Design of Parallel Algorithms – Arithmetic and Matrix problems. Mc Graw Hill (1990). 
  12. [12] H. Lee, J. Kim, S.J. Hong and S. Lee, Processor allocation and task scheduling of matrix chain products on parallel systems. IEEE Trans. Parallel Distrib. Syst.14 (2003) 3–14. 
  13. [13] Z. Mahjoub and F. Karoui-Sahtout, Maximal and optimal degrees of parallelism for a parallel algorithm, in Proc. of Transputers'94, IOS Press (1994) 220–233. 
  14. [14] N. Santoro, Chain multiplication of matrices of approximately or exactly the same size. Commun. ACM27 (1984) 152–156. MR784127
  15. [15] A. Schoor, Fast algorithms for sparse matrix multiplication. Inform. Process. Lett.15 (1982) 87–89. Zbl0502.65026MR675876
  16. [16] J. Takche, Complexities of special matrix multiplication problems. Comput. Math. Appl.12 (1988) 977–989. Zbl0654.65035MR953835

NotesEmbed ?

top

You must be logged in to post comments.