Matrix-Chain Multiplication

• A1, A2, ..., An의 matrices가 주어졌을 때, 각각의 곱을 구하고자 한다.

  → A1 * A2 * ... * An

• 순서에 따라서 게산량의 차이가 발생한다.

• 순서와 상관없이 답은 동일하다.

The Cost of Multiplying Two Matrices

• A = p * q
• B = q * r
  • 그 곱을 한 결과는 C = p * r

• C 를 구하기 위한 연산의 cost는 p * q * r

The cost of Multiplying Three Matrices

밍쥬등장!!!!

• 세 개의 Matrix A, B, C
  • A = p * q
  • B = q * r
  • C = r * s
• A * B * C를 계산하는 두 가지 방법 → (A * B) * C or A * (B * C)
  • A, B를 먼저 곱할 때; (A * B) * C
    • p * q * r + p * r * s = p * r * (q + s)
  • B, C를 먼저 곱할 때; A * (B * C)
    • q * r * s + p * q * s = (p + r) * q * s

More Matrices, More Ways to Parenthesize

• 어느 행렬을 먼저 곱할지 결정해야 함.
• 연산 곱셈 수행에서 엄청나게 큰 차이를 만들어 낸다.

Number of parenthesizations

• matrics가 n개 일 때 곱하기를 하는 방법