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 $n\,m\,p$ 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

$((A\,B)\,(C\,D))$ requires 41,200 multiplications, but $(A\,((B\,C)\,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)=\min _{k}(M(i,k)+M(k+1,j)+d_{i-1}\,d_{k}\,d_{j})$

$\underbrace {(A_{i}\,\dots \,A_{k})} _{P_{1}}\,\underbrace {(A_{k+1}\,\dots \,A_{j})} _{P_{2}}$

• 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