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(n^{3}) 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.

Keywords: 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://archive.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://archive.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://archive.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, Volume 45 (2011) no. 1, pp. 1-16. doi : 10.1051/ro/2011100. http://archive.numdam.org/articles/10.1051/ro/2011100/

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

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

,[3] Introduction à l'Algorithmique. Dunod (2002). | Zbl

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

and ,[5] Bar, Advanced Computer Architecture and Parallel Processing. Wiley (2005).

and -[6] O(n) instances of the matrix chain product problem solved in linear time, in Proc. of ROADEF'09, Nancy, France (2009).

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

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

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

and ,[10] Introduction to Parallel Computing - Design and Analysis of Algorithms. The Benjamin/Cummings Pub. Co. (1994). | Zbl

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

and ,[12] Processor allocation and task scheduling of matrix chain products on parallel systems. IEEE Trans. Parallel Distrib. Syst. 14 (2003) 3-14.

, , and ,[13] Maximal and optimal degrees of parallelism for a parallel algorithm, in Proc. of Transputers'94, IOS Press (1994) 220-233.

and ,[14] Chain multiplication of matrices of approximately or exactly the same size. Commun. ACM 27 (1984) 152-156. | MR

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

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

,*Cited by Sources: *