Accession Number : ADA113349

Title :   Computation of Matrix Chain Products. Part I, Part II.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Hu,T C ; Shing,M T

PDF Url : ADA113349

Report Date : Sep 1981

Pagination or Media Count : 100

Abstract : This paper considers the computation of matrix chain products of the form M sub (1) x M sub (2) x ... X M sub (n-1). If the matrices are of different dimensions, the order in which the product is computed affects the number of operations. An optimum order is an order which minimizes the total number of operations. We present some theorems about an optimum order of computing the matrices. Based on these theorems, and 0(n log n) algorithm for finding an optimum order is presented in part II. (Author)

Descriptors :   *Matrix theory, *Matrices(Mathematics), *Computations, Algorithms, Chains, Optimization, Theorems, Multiplication

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE