Voir la notice de l'article provenant de la source Numdam
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.
@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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
Cité par Sources :