Lec12.1-Dynamic Programming 2

Multiplying Matrices
n Two matrices, A with (p x q) matrix and B with (q x r)

matrix, can be multiplied to get C with dimensions p x r,
using scalar multiplications
1
Multiplying Matrices
2
Ex2:Matrix-chain multiplication
n We are given a sequence (chain) <A1, A2, ..., An> of n
matrices to be multiplied, and we wish to compute the
product. A1.A2…An.
n Matrix multiplication is associative, and so all

parenthesizations yield the same product,
(A1 (A2 (A3 A4))) ,

(A1 ((A2 A3) A4)) ,
((A1 A2) (A3 A4)) ,
((A1 (A2 A3)) A4) ,
(((A1 A2) A3) A4).
3
Matrix-chain multiplication – cont.
n We can multiply two matrices A and B only if they are
compatible the number of columns of A must equal the
number of rows of B. If A is a p × q matrix and B is a q ×
r matrix, the resulting matrix C is a p × r matrix.
n The time to compute C is dominated by the number of

scalar multiplications, which is p q r.
4
n Ex: consider the problem of a chain <A1, A2, A3> of
three matrices, with the dimensions of 10 × 100, 100
× 5, and 5 × 50, respectively.
n If we multiply according to ((A1 A2) A3), we perform

10 · 100 · 5 = 5000 scalar multiplications to compute
the 10 × 5 matrix product A1 A2, plus another 10 · 5 ·
50 = 2500 scalar multiplications to multiply this matrix
byA3 for a total of 7500 scalar multiplications
n If instead , we multiply as (A1 (A2 A3)), we perform

100 · 5 · 50 = 25,000 scalar multiplications to
compute the 100 × 50 matrix product A2 A3, plus
another 10 · 100 · 50 = 50,000 scalar multiplications
to multiply A1 by this matrix, for a total of 75,000
scalar multiplications. Thus, computing the product
according to the first parenthesization is 10 times
faster.
5
n Matrix multiplication is associative
q q (AB)C = A(BC)
n The parenthesization matters

n Consider A X B X C X D, where
q A is 30x1, B is 1x40, C is 40x10, D is 10x25
n Costs:
q ((AB)C)D = 1200 + 12000 + 7500 = 20700
q (AB)(CD) = 1200 + 10000 + 30000 = 41200
q A((BC)D) = 400 + 250 + 750 = 1400
6
Matrix Chain Multiplication (MCM)
Problem
n Input:
q Matrices A1, A2, …, An, each Ai of size pi-1 x pi,
n Output:
q Fully parenthesised product A1 x A2 x … x An
that minimizes the number of scalar
multiplications.
n Note:
q In MCM problem, we are not actually multiplying
matrices
q Our goal is only to determine an order for
multiplying matrices that has the lowest cost
7
Matrix Chain Multiplication (MCM)
Problem
n Typically, the time invested in determining
this optimal order is more than paid for by the
time saved later on when actually performing
the matrix multiplications
n So, exhaustively checking all possible

parenthesizations does not yield an efficient
algorithm
8
Counting the Number of Parenthesizations
n Denote the number of alternative parenthesizations of a
sequence of (n) matrices by P(n) then a fully
parenthesized matrix product is given by:
! (A1 (A2 (A3 A4))) , If n = 4 <A1,A2,A3,A4> then the number of

! (A1 ((A2 A3) A4)) , alternative parenthesis is =5
! ((A1 A2) (A3 A4)) , P(4) =P(1) P(4-1) + P(2) P(4-2) + P(3) P(4-3)
! ((A1 (A2 A3)) A4) , = P(1) P(3) + P(2) P(2) + P(3) P(1)= 2+1+2=5
! (((A1 A2) A3) A4). P(3) =P(1) P(2) + P(2) P(1) = 1+1=2
P(2) =P(1) P(1)= 1
9
Counting the Number of Parenthesizations
10
Step 1: Optimal Sub-structure
11
12
13
14
Step 2: Recursive Solution
n Next we define the cost of optimal solution
recursively in terms of the optimal solutions to
sub-problems
n For MCM, sub-problems are:

q problems of determining the min-cost of a
parenthesization of Ai Ai+1…Aj for 1 <= i <= j <= n
n Let m[i, j] = min # of scalar multiplications

needed to compute the matrix Ai...j.
q For the whole problem, we need to find m[1, n]
15
n Since Ai..j can be obtained by breaking it into
Ai..k Ak+1..j, We have (each Ai of size pi-1 x
pi)
q m[i, j] = m[i, k] + m[k+1, j] + pi-1pkpj
n There are j-i possible values for k: i <= k <= j
n Since the optimal parenthesization must use

one of these values for k, we need only check
them all to find the best.
16
17
Step 3: Computing the Optimal Costs
18
Elements of Dynamic Programming
19
Overlapping Sub-problems
20
The following code assumes that matrix Ai has
dimensions pi-1 x pi for i =1,2, …, n
21
22
23
24
25
26
27
Step 4: Constructing an Optimal Solution
n Although Matrix-Chain-Order determines the
optimal number of scalar multiplications
needed to compute a matrix-chain product, it
does not directly show how to multiply the
matrices
n Using table s, we can construct an optimal

solution
28
29
30
31
32

Lec12.1-Dynamic Programming 2

Uploaded by

Copyright:

Available Formats

Lec12.1-Dynamic Programming 2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lec12.1-Dynamic Programming 2

Uploaded by

Copyright:

Available Formats

Multiplying Matrices

n Two matrices, A with (p x q) matrix and B with (q x r)

n Matrix multiplication is associative, and so all

(A1 (A2 (A3 A4))) ,

n The time to compute C is dominated by the number of

n If we multiply according to ((A1 A2) A3), we perform

n If instead , we multiply as (A1 (A2 A3)), we perform

n The parenthesization matters

n So, exhaustively checking all possible

! (A1 (A2 (A3 A4))) , If n = 4 <A1,A2,A3,A4> then the number of

n For MCM, sub-problems are:

n Let m[i, j] = min # of scalar multiplications

n There are j-i possible values for k: i <= k <= j

n Since the optimal parenthesization must use

n Using table s, we can construct an optimal

You might also like