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

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1981
Accession Number
ADA113349

Entities

People

  • M. T. Shing
  • T. C. Hu

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Dynamic Programming
  • Equations
  • Graph Theory
  • Inequalities
  • Mathematics
  • North Carolina
  • Permutations
  • Polygons
  • Sequences
  • Trees (Data Structures)
  • Triangles

Readers

  • Computer Science.
  • Control Systems Engineering.
  • Industrial Economics