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

reportActive / Technical Report | Accession Number: ADA113349 | Open PDF

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 0n log n algorithm for finding an optimum order is presented in part II. Author

Author(s):
Hu, T. C. ; Shing, M. T.
Author Organization(s):
STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Descriptive Note:
Technical rept.,
Supplementary Note:
DOI: 10.21236/ADA113349
Pagination:
0100

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
STAN-CS-81-875, ARO-16323.2-M
Contract/Grant Number(s):
DAAG29-80-C-0029, NSF-MCS77-23738
Monitor Series:
16323.2-M
 Subject Terms
Joint Capability Areas:
JCA_1.2.5_Lessons Learned; JCA_5_Command and Control; JCA_5.3_Planning; JCA_1.2.3_Educating
Modernization Areas:
Directed Energy
Communities of Interest:
No COI(s) Identified
Descriptor(s):
*Matrix theory, *Matrices(Mathematics), *Computations, Algorithms, Chains, Optimization, Theorems, Multiplication
Field(s)/Group(s):
Theoretical Mathematics
Report Date:
1981 Sep 01