CSCE 411 Lecture 11

Lecture Slides

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

Dynamic Programming

Matrix Chain Algoritm

Multiplying Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \times m} matrix with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \times p} : naïve algorithm takes $n\,m\,p$ multiplications and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_(k+1,j)}
• cost of computing product of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_1 \, P_2} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_{i-1} \, d_k \, d_j}

Find Dependencies

Fill in our table for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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