CSCE 411 Lecture 11

Lecture Slides

« previous | Wednesday, September 19, 2012 | next »

Dynamic Programming

Matrix Chain Algoritm

Multiplying $n\times m$ matrix with $m\times p$: naïve algorithm takes $nmp$ multiplications and $n(m-1)p$ additions

Chained multiplications can add up quickly:

Order Matters

Multiplying the following matrices:

• A : 30 × 1
• B : 1 × 40
• C : 40 × 10
• D : 10 × 25

$((AB)(CD))$ requires 41,200 multiplications, but $(A((BC)D))$ requires 1400

Matrix Chain Order Problem

Use dynamic programming to find the optimum chaining to give minimum number of operations:

Given $n$ matrices such that their sizes are compatible for multiplication.

Define $M(i,j)$ to be the minimum number of operations needed to compute $A_i{A}_{i+1}\dots A_j$.

Goal: find $M(1,n)$ Basis: $M(i,i)=0$

1. Consider all possible ways to split $A_i$ through $A_j$ into two pieces
2. Compare best case cost for computing product of two pieces (plus cost of multiplying two products)
3. Take the best one such that $M(i,j)=\underset{k}{\min }(M(i,k)+M(k+1,j)+d_{i-1}{d}_k{d}_j)$

$\underset{P_1}{\underbrace{(A_i\dots A_k)}}\underset{P_2}{\underbrace{(A_{k+1}\dots A_j)}}$

• minimum cost to compute $P_1$ is $M_{(}i,k)$
• minimum cost to compute $P_2$ is $M_{(}k+1,j)$
• cost of computing product of $P_1{P}_2$ is $d_{i-1}{d}_k{d}_j$

Find Dependencies

Fill in our table for $M$

	1	2	3	4	5
1	0				(goal)
2	n/a	0
3	n/a	n/a	0
3	n/a	n/a	n/a	0
4	n/a	n/a	n/a	n/a	0

Compute cells adjacent to values we already know first (work from diagonal to $M(1,5)$)

Pseudocode

(1..m).each {|i| M[i][i] = 0}
(1..n-1).each do |d| # diagonals
  (1..n-d).each do |i| # rows w/ an entry on dth diagonal
    j = i+d # column corresponding to row i on dth diagonal
    M[i][j] = Infinity
    (1..j-1).each do |k|
      M[i][j] = min(M[i][j], M[i][k] + M[k+1][j]+d[i-1]d[k]d[j])
    end
  end
end