Browse Prior Art Database

Deciding the Order of Computation of Matrix Chain Products

IP.com Disclosure Number: IPCOM000085947D
Original Publication Date: 1976-Jun-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Chandra, AK: AUTHOR

Abstract

Given a sequence of matrices to be multiplied, there is described herein a way of choosing the order of association so as to reduce total computing time. Assume that the sequence of matrices to be multiplied takes the form: M(1) x M(2) x ... x M(n).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 88% of the total text.

Page 1 of 1

Deciding the Order of Computation of Matrix Chain Products

Given a sequence of matrices to be multiplied, there is described herein a way of choosing the order of association so as to reduce total computing time. Assume that the sequence of matrices to be multiplied takes the form: M(1) x M(2) x ... x M(n).

The order in which they are associated can dramatically affect computation time, so much so that if the best association order yields running time T, a bad order of association can run in time O(T/3/). The best known way of choosing the optimal order is expensive if n is large, running in time O(n/3/) [1].

Let the sizes of matrices, M(1), M(2), ..., M(n) be k(0)xk(1), k(1)xk(2), ..., k(n- 1)xk(n), and let k(1) be the minimum of all the k's. Then choose the following order of association: M)(1)x...x(M(i-2)x(Mi-1)xM(i)))...)x
(...((M(i+1)xM(i+2))xM(i+3))x...xM(n)

The advantage of this method is that the minimum index k , appears in all the multiplications, thereby helping to reduce the total time. It can be shown, in fact, that this method is no more than a factor of 2 away from the optimal association order [2] whether the ordinary way of multiplying two matrices is used, or the asymptotically better ways. [3].

The feature of the described method is that it quickly chooses a near-optimal order of association for multiplying a sequence of matrices. [1] The Design and Analysis of Computer Algorithms, Aho, Hopcroft and Ullman, Addison Wesley, 1974 (sec. 2.8). [2]...