[go: up one dir, main page]
Scribd
Upload
79 views15 pages

Matrix-Chain Multiplication: - Suppose We Have A Sequence or Chain A, A,, A of N Matrices To Be Multiplied

The document describes the matrix-chain multiplication problem and presents a dynamic programming approach to find an optimal parenthesization of matrices that minimizes the number of scalar multiplications. It defines the problem, provides examples, and presents a dynamic programming algorithm that computes the minimum cost in O(n3) time using a bottom-up approach with tables for the minimum cost m and how to split the chains optimally s. The optimal solution can then be constructed from the split table.

Uploaded by

rosev15
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
79 views15 pages

Matrix-Chain Multiplication: - Suppose We Have A Sequence or Chain A, A,, A of N Matrices To Be Multiplied

The document describes the matrix-chain multiplication problem and presents a dynamic programming approach to find an optimal parenthesization of matrices that minimizes the number of scalar multiplications. It defines the problem, provides examples, and presents a dynamic programming algorithm that computes the minimum cost in O(n3) time using a bottom-up approach with tables for the minimum cost m and how to split the chains optimally s. The optimal solution can then be constructed from the split table.

Uploaded by

rosev15
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 15

11-1

Matrix-chain Multiplication
Suppose we have a sequence or chain
A
1
, A
2
, , A
n
of n matrices to be
multiplied
That is, we want to compute the product
A
1
A
2
A
n

There are many possible ways
(parenthesizations) to compute the
product
11-2
Matrix-chain Multiplication contd
Example: consider the chain A
1
, A
2
, A
3
,
A
4
of 4 matrices
Let us compute the product A
1
A
2
A
3
A
4

There are 5 possible ways:
1. (A
1
(A
2
(A
3
A
4
)))

2. (A
1
((A
2
A
3
)A
4
))

3. ((A
1
A
2
)(A
3
A
4
))

4. ((A
1
(A
2
A
3
))A
4
)

5. (((A
1
A
2
)A
3
)A
4
)
11-3
Matrix-chain Multiplication contd
To compute the number of scalar
multiplications necessary, we must know:
Algorithm to multiply two matrices
Matrix dimensions

Can you write the algorithm to multiply
two matrices?
11-4
Algorithm to Multiply 2 Matrices
Input: Matrices A
pq
and B
qr
(with dimensions pq and qr)
Result: Matrix C
pr
resulting from the product AB

MATRIX-MULTIPLY(A
pq
, B
qr
)
1. for i 1 to p
2. for j 1 to r
3. C[i, j] 0
4. for k 1 to q
5. C[i, j] C[i, j] + A[i, k] B[k, j]
6. return C
Scalar multiplication in line 5 dominates time to compute
CNumber of scalar multiplications = pqr
11-5
Matrix-chain Multiplication contd
Example: Consider three matrices
A
10100
, B
1005
, and C
550
There are 2 ways to parenthesize
((AB)C) = D
105
C
550

AB 10 100 5=5,000 scalar multiplications
DC 10 5 50 =2,500 scalar multiplications
(A(BC)) = A
10100
E
10050

BC 100 5 50=25,000 scalar multiplications
AE 10 100 50 =50,000 scalar multiplications
Total:
7,500
Total:
75,000
11-6
Matrix-chain Multiplication contd
Matrix-chain multiplication problem
Given a chain A
1
, A
2
, , A
n
of n matrices,
where for i=1, 2, , n, matrix A
i
has
dimension p
i-1
p
i
Parenthesize the product A
1
A
2
A
n
such that
the total number of scalar multiplications is
minimized
Brute force method of exhaustive search
takes time exponential in n
11-7
Dynamic Programming Approach
The structure of an optimal solution
Let us use the notation A
i..j
for the matrix that
results from the product A
i
A
i+1
A
j

An optimal parenthesization of the product
A
1
A
2
A
n
splits the product between A
k
and
A
k+1
for some integer k where1 k < n
First compute matrices A
1..k
and A
k+1..n
; then
multiply them to get the final matrix A
1..n

11-8
Dynamic Programming Approach
contd
Key observation: parenthesizations of the
subchains A
1
A
2
A
k
and A
k+1
A
k+2
A
n
must
also be optimal if the parenthesization of the
chain A
1
A
2
A
n
is optimal (why?)

That is, the optimal solution to the problem
contains within it the optimal solution to
subproblems
11-9
Dynamic Programming Approach
contd
Recursive definition of the value of an
optimal solution
Let m[i, j] be the minimum number of scalar
multiplications necessary to compute A
i..j

Minimum cost to compute A
1..n
is m[1, n]
Suppose the optimal parenthesization of A
i..j

splits the product between A
k
and A
k+1
for
some integer k where i k < j
11-10
Dynamic Programming Approach
contd
A
i..j
= (A
i
A
i+1
A
k
)(A
k+1
A
k+2
A
j
)= A
i..k
A
k+1..j

Cost of computing A
i..j
= cost of computing
A
i..k
+ cost of computing A
k+1..j
+ cost of
multiplying A
i..k
and A
k+1..j
Cost of multiplying A
i..k
and A
k+1..j
is p
i-1
p
k
p
j

m[i, j ] = m[i, k] + m[k+1, j ] + p
i-1
p
k
p
j

for i k < j
m[i, i ] = 0 for i=1,2,,n
11-11
Dynamic Programming Approach
contd
But optimal parenthesization occurs at
one value of k among all possible i k < j
Check all these and select the best one

m[i, j ] =
0 if i=j
min {m[i, k] + m[k+1, j ] + p
i-1
p
k
p
j
} if i<j
i k< j
11-12
Dynamic Programming Approach
contd
To keep track of how to construct an
optimal solution, we use a table s
s[i, j ] = value of k at which A
i
A
i+1
A
j
is
split for optimal parenthesization
Algorithm: next slide
First computes costs for chains of length l=1
Then for chains of length l=2,3, and so on
Computes the optimal cost bottom-up
11-13
Algorithm to Compute Optimal Cost
Input: Array p[0n] containing matrix dimensions and n
Result: Minimum-cost table m and split table s

MATRIX-CHAIN-ORDER(p[ ], n)
for i 1 to n
m[i, i] 0
for l 2 to n
for i 1 to n-l+1
j i+l-1
m[i, j]
for k i to j-1
q m[i, k] + m[k+1, j] + p[i-1] p[k] p[j]

if q < m[i, j]
m[i, j] q
s[i, j] k
return m and s
Takes O(n
3
) time
Requires O(n
2
) space
11-14
Constructing Optimal Solution
Our algorithm computes the minimum-
cost table m and the split table s
The optimal solution can be constructed
from the split table s
Each entry s[i, j ]=k shows where to split the
product A
i
A
i+1
A
j
for the minimum cost
11-15
Example
Show how to multiply
this matrix chain
optimally

Solution on the board
Minimum cost 15,125
Optimal parenthesization
((A
1
(A
2
A
3
))((A
4
A
5
)A
6
))
Matrix Dimension
A
1
3035
A
2
3515
A
3
155
A
4
510
A
5
1020
A
6
2025

You might also like