daehee97/chained-matrix-multiplication

Chained Matrix Multiplication

연속 행렬 곱셈

• n 개의 연쇄 행렬 곱셈 : $𝐴1 × 𝐴2 × ⋯ × 𝐴𝑛$

• 일반적으로 𝑖×𝑘 행렬 과 𝑘×𝑗 행렬을 곱하면 𝑖×𝑗 행렬, 이 때 원소 곱셈의 횟수 = $𝑖 * 𝑘 * 𝑗$

• 행렬곱셈은 결합법칙이 성립 : $(𝐴𝑥 ×𝐴𝑦)×𝐴𝑧 =𝐴𝑥 ×(𝐴𝑦 ×𝐴𝑧)$

• 이 때 행렬 곱셈의 순서에 따라서 각 원소의 곱셈 횟수가 다른데, 각 원소의 곱셈 횟수가 가장 작아지도록 하는 곱셈 순서가 최적의 순서를 찾는 문제

---

문제 정의

n개의 연속 행렬곱셈 : $𝐴1 ×𝐴2 ×⋯×𝐴𝑛$

• $𝐴𝑘−1$ 의 행의 개수 와 $𝐴𝑘$ 의 열의 개수가 같아야함

• $𝑑𝑘$ 를 행렬 $𝐴𝑘$ 의 행의 원소 개수로 정함 $(1≤𝑘≤𝑛)$

• $𝑑𝑘−1$ 은 행렬 $𝐴𝑘$ 의 열의 원소 개수, $𝐴𝑘−1$ 의 행의 원소 개수임

• $𝑑0$ 는 $𝐴1$ 의 열의 원소 개수

---

문제 해결 아이디어

1단계: 재귀 관계식

• $𝑴$ : 연쇄행렬을 곱하는데 필요한 곱셈의 최소 회수 행렬

• $𝑴[𝒊][𝒋]$ : $𝐴$ 에서 $𝐴$ 까지 행렬을 곱하는데 필요한 곱셈의 최소 회수 $𝑖𝑗$ $(1 ≤ 𝑖 ≤ 𝑗 ≤ 𝑛)$

• 목표 : $𝐴i ⋯𝐴j$ 행렬을 $(𝐴i ⋯𝐴k )$ $(𝐴k+1 ⋯𝐴j)$ 로 분할하는 재귀관계식 찾기

분할정복 (Divide-and-Conquer)

• 𝑛개의 행렬을 두개의 최적부분 행렬의 곱으로 분할
• 예를 들어, $𝐴1𝐴2𝐴3𝐴4𝐴5𝐴6$ 은 다음과 같이 분할 가능

각 분할의 곱셈 횟수 :

• 각 부분 행렬의 곱셈 횟수 + 두 행렬의 곱셈 횟수

• $𝑀[1][𝑘]+𝑀[𝑘+1][6]+𝑑0 𝑑𝑘 𝑑6$

2단계: Top down 상향식 계산

• 초기화 : $𝑀[𝑖][𝑖]=0$ (주대각선을0으로)

• 최종목표 : $𝑀[1][𝑛]$

• Top down 상향식 계산 : 대각선1번, 대각선2번, ⋯ , 대각선 𝑛 − 1 번