Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices
RAIRO - Operations Research - Recherche Opérationnelle, Tome 45 (2011) no. 1, pp. 1-16.

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.

DOI : 10.1051/ro/2011100
Classification : 65K05, 90C27, 90C39, 90C59
Mots-clés : combinatorial optimization, dynamic programming, gree-dy algorithm, matrix chain product, parallel computing 
@article{RO_2011__45_1_1_0,
     author = {Ben Charrada, Faouzi and Ezouaoui, Sana and Mahjoub, Zaher},
     title = {Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1--16},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {1},
     year = {2011},
     doi = {10.1051/ro/2011100},
     mrnumber = {2786119},
     zbl = {1216.90071},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2011100/}
}
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
SP  - 1
EP  - 16
VL  - 45
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2011100/
DO  - 10.1051/ro/2011100
LA  - en
ID  - RO_2011__45_1_1_0
ER  - 
%0 Journal Article
%A Ben Charrada, Faouzi
%A Ezouaoui, Sana
%A Mahjoub, Zaher
%T Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2011
%P 1-16
%V 45
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2011100/
%R 10.1051/ro/2011100
%G en
%F RO_2011__45_1_1_0
Ben Charrada, Faouzi; Ezouaoui, Sana; Mahjoub, Zaher. Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices. RAIRO - Operations Research - Recherche Opérationnelle, Tome 45 (2011) no. 1, pp. 1-16. doi : 10.1051/ro/2011100. http://www.numdam.org/articles/10.1051/ro/2011100/

[1] A.K. Chandra, Computing matrix products in near-optimal time. IBM Research Report, RC 5625 (1975).

[2] F.Y. Chin, An O(n) algorithm for determining a near-optimal computation order of matrix chain products. Commun. ACM 21 (1978) 544-549. | MR | Zbl

[3] T.H. Cormen, C.E. Leicerson, R.L. Rivest and C. Stein, Introduction à l'Algorithmique. Dunod (2002). | Zbl

[4] M. Cosnard and D. Trystram, Algorithmes et Architectures Parallèles. InterEditions (1993).

[5] H. El-Rewini and M. Abd-El-Bar, Advanced Computer Architecture and Parallel Processing. Wiley (2005).

[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).

[7] S.S. Godbole, An efficient computation of matrix chain products. IEEE Trans. Comput. C-22 (1973) 864-866. | Zbl

[8] T.C. Hu and M.T. Shing, Computation of matrix chain products. Part I. SIAM J. Comput. 11 (1982) 362-373. | MR | Zbl

[9] T.C. Hu and M.T. Shing, Computation of matrix chain products. Part II. SIAM J. Comput. 13 (1984) 229-251. | MR | Zbl

[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). | Zbl

[11] S. Lakshmivarahan and S.K. Dhall, Analysis and Design of Parallel Algorithms - Arithmetic and Matrix problems. Mc Graw Hill (1990).

[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] 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] N. Santoro, Chain multiplication of matrices of approximately or exactly the same size. Commun. ACM 27 (1984) 152-156. | MR

[15] A. Schoor, Fast algorithms for sparse matrix multiplication. Inform. Process. Lett. 15 (1982) 87-89. | MR | Zbl

[16] J. Takche, Complexities of special matrix multiplication problems. Comput. Math. Appl. 12 (1988) 977-989. | MR | Zbl

Cité par Sources :