스트라센(Strassen) 알고리즘 정의, 연습문제, 그리고 주식투자 활용

*가독성을 고려하지 않은 글입니다.

📘 1. 스트라센(Strassen) 알고리즘의 정의

🔹 핵심 아이디어

정사각 행렬 곱 C = A × B를 분할정복으로 계산할 때,
기존 8번의 부분행렬 곱 대신 7번만 곱하고 덧셈/뺄셈을 늘린 방법이다.

7개의 곱

M1 = (A11 + A22)(B11 + B22)
M2 = (A21 + A22) B11
M3 = A11 (B12 - B22)
M4 = A22 (B21 - B11)
M5 = (A11 + A12) B22
M6 = (A21 - A11)(B11 + B12)
M7 = (A12 - A22)(B21 + B22)

결과 조합

C11 = M1 + M4 - M5 + M7
C12 = M3 + M5
C21 = M2 + M4
C22 = M1 - M2 + M3 + M6

⚙️ 시간복잡도

분할정복 점화식:
T(n) = 7T(n/2) + O(n^2)

결과적으로
T(n) = O(n^log₂7) ≈ O(n^2.807)

기존 O(n^3)보다 빠르다.

---

📗 2. 연습문제 모음

🧩 (1) 복잡도 증명

문제
T(n)=7T(n/2)+cn^2의 해를 구하라.
힌트
Master 정리에 따라 O(n^log₂7).

---

🧮 (2) 연산 수 세기

문제
2×2 행렬의 곱에서 스트라센 알고리즘의 덧셈/뺄셈 횟수를 구하라.
답
곱셈 7회, 덧/뺄셈 18회.

---

🧠 (3) 정확도 비교 실험

문제
랜덤 실수 행렬에서 Strassen과 GEMM의 상대오차를 비교하라.
힌트
||C_s - C_g|| / ||C_g||로 계산.
n=64,128,256,512 실험.

---

📏 (4) 비정방/비거듭제곱 처리

문제
비정방 행렬을 Strassen으로 처리하는 패딩 전략을 설계하라.
힌트
가장 긴 변을 2의 거듭제곱으로 패딩 후 결과를 잘라낸다.

---

💾 (5) 메모리 사용량

문제
순진한 재귀 구현의 메모리 사용량을 줄이는 방법을 제안하라.
힌트
버퍼 재사용, in-place 계산.

---

⚡ (6) 블록 행렬 구조 활용

문제
공분산 행렬이 블록대각 구조일 때 복잡도가 어떻게 줄어드는가?
힌트
독립 블록은 각각 따로 곱 → 전체 복잡도 감소.

---

🧬 (7) (심화) Winograd 변형

문제
Winograd 변형이 더 빠른 이유와 수치오차 차이를 분석하라.
힌트
곱셈은 줄지만 덧셈 증가로 오차는 커질 수 있다.

---

💹 3. 주식투자(퀀트)에서의 활용

스트라센 자체는 투자전략은 아니지만,
대규모 행렬 연산을 빠르게 처리해 퀀트 연구 효율을 높일 수 있다.

---

🏦 주요 활용 영역

1️⃣ 공분산/상관 행렬 계산

• 자산 N개 → 공분산 행렬 크기 N×N.
• 리스크 파리티, 최소분산, 블랙-리터만 등에서 반복 계산됨.
• Strassen으로 연산 시간 단축 가능.

2️⃣ 시뮬레이션(몬테카를로)

• 정규 상관 시나리오 생성 시 Cholesky 분해·행렬곱 반복.
• 빠른 곱이 시뮬레이션 속도 향상.

3️⃣ 실시간 공분산 갱신

• 롤링 윈도우 기반의 실시간 업데이트.
• 블록 업데이트 + 빠른 곱으로 레이턴시 감소.

4️⃣ NLP/딥러닝 팩터 추정

• 뉴스/재무보고서 임베딩 → 대형 행렬연산.
• 학습 및 추론 속도 향상으로 리밸런싱 빈도 증가.

---

⚠️ 실무 체크리스트

구분	설명
정확도	덧셈 증가로 수치오차↑ → float64 사용
크로스오버	300~500 이하 크기에서는 오히려 느릴 수 있음
메모리/캐시	재귀 수준이 깊을수록 캐시 미스 주의
대안	GPU/cuBLAS, OpenBLAS, MKL 같은 고성능 GEMM 우선 고려
구조활용	희소성·저랭크·블록대각 형태면 더 큰 속도 향상 가능

---

🧪 미니 실험 아이디어

• KOSPI 100 또는 S&P100 수익률로 공분산 행렬 계산.
• (a) BLAS, (b) Strassen, (c) 저랭크 근사 비교.
  → 속도·메모리·오차·포트 가중치 차이 비교.

---

🧰 4. 파이썬 의사코드

def strassen(A, B, crossover=128):
    n = A.shape[0]
    if n <= crossover:
        return gemm(A, B)

    # Padding
    A2, B2 = pad_to_power_of_two(A), pad_to_power_of_two(B)
    n2 = A2.shape[0]
    mid = n2 // 2

    A11, A12, A21, A22 = A2[:mid,:mid], A2[:mid,mid:], A2[mid:,:mid], A2[mid:,mid:]
    B11, B12, B21, B22 = B2[:mid,:mid], B2[:mid,mid:], B2[mid:,:mid], B2[mid:,mid:]

    M1 = strassen(A11+A22, B11+B22, crossover)
    M2 = strassen(A21+A22, B11, crossover)
    M3 = strassen(A11, B12-B22, crossover)
    M4 = strassen(A22, B21-B11, crossover)
    M5 = strassen(A11+A12, B22, crossover)
    M6 = strassen(A21-A11, B11+B12, crossover)
    M7 = strassen(A12-A22, B21+B22, crossover)

    C11 = M1 + M4 - M5 + M7
    C12 = M3 + M5
    C21 = M2 + M4
    C22 = M1 - M2 + M3 + M6

    C = assemble(C11, C12, C21, C22)
    return unpad_to_original(C, A.shape[0], B.shape[1])




### 실무팁