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
topHow 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.
- 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).
- 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.
- T.C. Hu and M.T. Shing, Computation of matrix chain products. Part II. SIAM J. Comput.13 (1984) 229–251.
- V. Kumar, A. Grama, A. Gupta and G. Karypis, Introduction to Parallel Computing – Design and Analysis of Algorithms. The Benjamin/Cummings Pub. Co. (1994).
- 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.
- J. Takche, Complexities of special matrix multiplication problems. Comput. Math. Appl. 12 (1988) 977–989.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.