# 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 (2011)

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

## Access Full Article

top## Abstract

top## How to cite

topBen 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 45.1 (2011): 1-16. <http://eudml.org/doc/197822>.

@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},

keywords = {Combinatorial optimization; dynamic programming; gree-dy algorithm; matrix chain product; parallel computing; combinatorial optimization; greedy algorithm},

language = {eng},

month = {3},

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/197822},

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

DA - 2011/3//

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; combinatorial optimization; greedy algorithm

UR - http://eudml.org/doc/197822

ER -

## References

top- A.K. Chandra, Computing matrix products in near-optimal time. IBM Research Report, RC 5625 (1975).
- F.Y. Chin, An O(n) algorithm for determining a near-optimal computation order of matrix chain products. Commun. ACM21 (1978) 544–549. Zbl0377.15005
- T.H. Cormen, C.E. Leicerson, R.L. Rivest and C. Stein, Introduction à l'Algorithmique. Dunod (2002).
- M. Cosnard and D. Trystram, Algorithmes et Architectures Parallèles. InterEditions (1993).
- H. El-Rewini and M. Abd-El-Bar, Advanced Computer Architecture and Parallel Processing. Wiley (2005).
- 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
- S.S. Godbole, An efficient computation of matrix chain products. IEEE Trans. Comput.C-22 (1973) 864–866.
- T.C. Hu and M.T. Shing, Computation of matrix chain products. Part I. SIAM J. Comput.11 (1982) 362–373. Zbl0483.68041
- T.C. Hu and M.T. Shing, Computation of matrix chain products. Part II. SIAM J. Comput.13 (1984) 229–251. Zbl0542.68028
- 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
- S. Lakshmivarahan and S.K. Dhall, Analysis and Design of Parallel Algorithms – Arithmetic and Matrix problems. Mc Graw Hill (1990).
- 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.
- 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.
- N. Santoro, Chain multiplication of matrices of approximately or exactly the same size. Commun. ACM27 (1984) 152–156.
- A. Schoor, Fast algorithms for sparse matrix multiplication. Inform. Process. Lett.15 (1982) 87–89. Zbl0502.65026
- J. Takche, Complexities of special matrix multiplication problems. Comput. Math. Appl. 12 (1988) 977–989. Zbl0654.65035

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.