Multi-Way Choices: Matrix Chain Multiplication

Multiplying two matrices of order (m, n) and (n, p) requires mnp number of multiplications.

​

Consider the problem of multiplying a chain of matrices: A_1, A_2, A₃

A_1, : (2 x 3), A_2, : (3 x 4), A : (4 x 5)

​

(A_1, A₂) A₃ : (2 x 3 x 4 )+ (2 x 4 x 5) = 24+ 40= 64

A₁ ( A₂ , A₃ ): (3 x 4 x 5)+ (2 x 3x 5) = 60 + 30 = 90

we see that by changing the sequence of evaluation, the cost of operation (number of multiplications) changes.

1

DYNAMIC PROGRAMMING

(Matrix Chain Multiplication)

Instructor

Neelima Gupta

University of Delhi, INDIA

ngupta@cs.du.ac.in

​

2

Multi-Way Choices: Matrix Chain Multiplication

Input: n matrices: A_1, A_{2, ………,} A_n

​

of order (d_1, d₂ ),(d_2, d₃ ),…… , (d_n,d_n+1) r.espectively

​

​

Aim: Determine the order in which the matrices should be multiplied so as to minimize the number of multiplications.

​

3

Order and the Choices to make

Order is implicit in the problem

​

Choices Optimal has for the split point k

​

(A_1, A_{2, ……}A_k ) ( A_{k+1 …,} A_n )

​

k could be 1 or 2 or …. n-1

​

k =1 means (A₁) ( A_{2 …,} A_n )

k =n-1 means (A_1, A_{2, ……}A_n-1 ) ( A_n )

4

Let Opt(1, n) denote the minimum the number of multiplications required to multiply the chain

A_1, A_{2, ………,} A_n

​

Let k be the split point then the minimum the number of multiplications required to multiply the chain is

m1 + m2 + d₁ d_k+1 d_n+1

where m1= minimum the number of multiplications required to multiply the chain A_1, A_{2, ………,} A_k recursively and

m2= minimum the number of multiplications required to multiply the chain A_k+1, A_{2, ………,} A_n recursively

​

​

5

Then,

​

Opt(1, n) = min_k {m1 + m2 + d₁ d_k+1 d_n+1}

​

= min_k {Opt(1, k) + Opt(k+1, n) + d₁ d_k+1 d_n+1}

​

Generalising,

​

Opt(1i, n j)

= min_k {Opt(1i, k) + Opt(k+1, nj) + d_i d_k+1 d_j+1}

​

6

Example:

Matrix dimensions:

• A₁ : 3 × 5
• A₂ : 5 × 4
• A₃ : 4 × 2
• A₄ : 2 × 7
• A₅ : 7 × 3
• A₆ : 3 × 8

7

Problem of parenthesization

8

A₁ *A₂ = 3*5*4 = 60

A₂*A₃ = 5*4*2 = 40

A₃*A₄ = 4*2*7 = 56

A₄*A₅ = 2*7*3 = 42

A₅*A₆ = 7*3*8 = 168

A₁ : 3 × 5

A₂ : 5 × 4

A₃ : 4 × 2

A₄ : 2 × 7

A₅ : 7 × 3

A₆ : 3 × 8

Problem of parenthesization

9

A₁ : 3 × 5

A₂ : 5 × 4

A₃ : 4 × 2

A₄ : 2 × 7

A₅ : 7 × 3

A₆ : 3 × 8

• A₁ _A₃= A₁ *A₂ *A₃ = min( (A₁.A₂).A₃ =60+ 3*4*2 =84 or A₁.(A₂ .A₃)=40+ 3*5*2=70) =70
• A₂ _A₄= A₂ *A₃ *A₄ = min( (A₂.A₃).A₄ =40+ 5*2*7=110 or A2.(A3.A4)=56+5*4*7=196)=110
• A₃ _A₅= A₃ *A₄ *A₅ = min( (A₃.A₄).A₅ =56+4*7*3=140 or A₃.(A₄.A₅)=42+ 4*2*3 =66) = 66
• A₄ _A₆= A₄ *A₅ *A₆ = min( (A₄ *A₅)*A₆= 42+2*3*8=90 or A₄ *(A₅ *A₆ )=168+ 2*7*8=312)=90

Problem of parenthesization

10

A₁ : 3 × 5

A₂ : 5 × 4

A₃ : 4 × 2

A₄ : 2 × 7

A₅ : 7 × 3

A₆ : 3 × 8

Overlapping Subproblems

m[1………4]

​

​

m[1],m[2,3,4] m[1,2],m[3,4] m[1,2,3],m[4]

​

​

m[2],m[3,4] m[2,3],m[4] m[1],m[2,3] m[1,2],m[3]

11

Number of sub-problems

Opt[i……………j] i<=j

n options n options

​

Number of subproblems= n²

12

Running Time

13

Ο(n²) entries in the table

​

each takes O(n) time to compute

​

Total running time : Ο(n³).