Scribd
Upload
11 views17 pages

ch15 Matrix Chain

The document discusses the matrix chain multiplication problem. It describes how multiplying a chain of matrices can be done in different ways by parenthesizing the product in different ways. It presents an algorithm that uses dynamic programming to solve the problem of finding the optimal parenthesization that minimizes the number of scalar multiplications. The algorithm works by recursively building up the solution, considering all possible ways to split the product between two matrices at each step and tracking the lowest cost. It runs in O(n^3) time and O(n^2) space.

Uploaded by

Sakib-bin-momin Farabi 1911343642
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views17 pages

ch15 Matrix Chain

The document discusses the matrix chain multiplication problem. It describes how multiplying a chain of matrices can be done in different ways by parenthesizing the product in different ways. It presents an algorithm that uses dynamic programming to solve the problem of finding the optimal parenthesization that minimizes the number of scalar multiplications. The algorithm works by recursively building up the solution, considering all possible ways to split the product between two matrices at each step and tracking the lowest cost. It runs in O(n^3) time and O(n^2) space.

Uploaded by

Sakib-bin-momin Farabi 1911343642
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 17

Matrix Chain Multiplication

Chapter 15

Mirza Mohammad Lutfe Elahi


CSE 373 Design and Analysis of Algorithms ECE@NSU
Matrix-chain Multiplication
• Suppose we have a sequence or chain
A1, A2, …, An of n matrices to be multiplied
– That is, we want to compute the product
A1A2…An

• There are many possible ways


(parenthesizations) to compute the product

CSE 373 Design and Analysis of Algorithms ECE@NSU


Matrix-chain Multiplication
• Example: consider the chain A1, A2, A3, A4 of
4 matrices
– Let us compute the product A1A2A3A4
• There are 5 possible ways:
1. (A1(A2(A3A4)))
2. (A1((A2A3)A4))
3. ((A1A2)(A3A4))
4. ((A1(A2A3))A4)
5. (((A1A2)A3)A4)

CSE 373 Design and Analysis of Algorithms ECE@NSU


Matrix-chain Multiplication
• 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?

CSE 373 Design and Analysis of Algorithms ECE@NSU


Algorithm- Multiply two Matrices

CSE 373 Design and Analysis of Algorithms ECE@NSU


Matrix-chain Multiplication
• Example: Consider three matrices
A10´100, B100´5, and C5´50
• There are 2 ways to parenthesize
– ((AB)C) = D10´5 · C5´50
• AB Þ 10·100·5=5,000 scalar multiplications Total:
• DC Þ 10·5·50 =2,500 scalar multiplications 7,500
– (A(BC)) = A10´100 · E100´50
• BC Þ 100·5·50=25,000 scalar multiplications
• AE Þ 10·100·50 =50,000 scalar multiplications
Total:
75,000

CSE 373 Design and Analysis of Algorithms ECE@NSU


Matrix-chain Multiplication
• Matrix-chain multiplication problem
– Given a chain A1, A2, …, An of n matrices, where
for i = 1, 2, …, n, matrix Ai has dimension pi-1´pi
– Parenthesize the product A1A2…An such that the
total number of scalar multiplications is
minimized
• Brute force method of exhaustive search
takes time exponential in n

CSE 373 Design and Analysis of Algorithms ECE@NSU


Dynamic Programming Approach
• The structure of an optimal solution
– Let us use the notation Ai..j for the matrix that
results from the product Ai Ai+1 … Aj
– An optimal parenthesization of the product
A1A2…An splits the product between Ak and Ak+1
for some integer k where1 ≤ k < n
– First compute matrices A1..k and Ak+1..n ; then
multiply them to get the final matrix A1..n

CSE 373 Design and Analysis of Algorithms ECE@NSU


Dynamic Programming Approach
– Key observation: parenthesizations of the
subchains A1A2…Ak and Ak+1Ak+2…An must also
be optimal if the parenthesization of the chain
A1A2…An is optimal (why?)

– That is, the optimal solution to the problem


contains within it the optimal solution to
subproblems

CSE 373 Design and Analysis of Algorithms ECE@NSU


Dynamic Programming Approach
• Recursive definition of the value of an
optimal solution
– Let m[i, j] be the minimum number of scalar
multiplications necessary to compute Ai..j
– Minimum cost to compute A1..n is m[1, n]
– Suppose the optimal parenthesization of Ai..j
splits the product between Ak and Ak+1 for some
integer k where i ≤ k < j

CSE 373 Design and Analysis of Algorithms ECE@NSU


Dynamic Programming Approach
– Ai..j = (Ai Ai+1…Ak)·(Ak+1Ak+2…Aj)= Ai..k · Ak+1..j
– Cost of computing Ai..j =
cost of computing Ai..k +
cost of computing Ak+1..j +
cost of multiplying Ai..k and Ak+1..j
– Cost of multiplying Ai..k and Ak+1..j is pi-1pk pj

– m[i, j ] = m[i, k] + m[k+1, j ] + pi-1pk pj


for i ≤ k < j
– m[i, i ] = 0 for i = 1,2,…,n

CSE 373 Design and Analysis of Algorithms ECE@NSU


Dynamic Programming Approach
– But… optimal parenthesization occurs at one
value of k among all possible i ≤ k < j
– Check all these and select the best one

0 if i=j
m[i, j ] =
min {m[i, k] + m[k+1, j ] + pi-1pk pj } if i<j
i ≤ k< j

CSE 373 Design and Analysis of Algorithms ECE@NSU


Dynamic Programming Approach
• To keep track of how to construct an optimal
solution, we use a table s
• s[i, j ] = value of k at which Ai Ai+1 … Aj 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

CSE 373 Design and Analysis of Algorithms ECE@NSU


Algorithm – Compute Optimal Cost

Takes O(n3) time


Requires O(n2) space

CSE 373 Design and Analysis of Algorithms ECE@NSU


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 Ai Ai+1 … Aj for the minimum cost

CSE 373 Design and Analysis of Algorithms ECE@NSU


Algorithm – Print Optimal Parenthesis

CSE 373 Design and Analysis of Algorithms ECE@NSU


Example

CSE 373 Design and Analysis of Algorithms ECE@NSU

You might also like