GREEDY ALGORITHMS FOR OPTIMAL COMPUTING OF MATRIX CHAIN PRODUCTS INVOLVING SQUARE DENSE AND TRIANGULAR MATRICES

摘要

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 paren-thesizations. 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.