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 ( full) or lower/upper triangular. Given a matrix chain of length , we first present a dynamic programming algorithm (DPA) adapted from the well known standard algorithm and having the same O( ) complexity. We then design and analyse two optimal O() greedy algorithms leading in general to different optimal...