스트라센 알고리즘
스트라센 알고리즘은 2×2 블록 행렬 곱셈을 8회 대신 7회의 부분 곱셈으로 계산한다 행렬 곱셈 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다...
| 분류 | 알고리즘 · 행렬 곱셈 |
|---|---|
| 핵심 문제 | 2×2 블록 행렬 곱셈을 8회 대신 7회의 부분 곱셈으로 계산한다 |
| 방법 | 행렬을 네 블록으로 나눈 뒤 7개의 중간 행렬 곱과 덧셈·뺄셈 조합으로 결과 블록을 만든다 |
| 계산 비용 | 시간 O(n^log₂7)≈O(n^2.807), 추가 메모리 사용 |
| 적용 조건 | 행렬 차원 보정과 부동소수점 안정성, 작은 블록에서의 전환 기준을 고려한다 |
| 관련 활용 | 대형 조밀 행렬 곱셈에 사용되지만 실제 라이브러리는 캐시·SIMD와 반올림 오차를 함께 고려해 방법을 선택한다 |
| 관련 이론 | 자료구조, 계산 복잡도 |
| 참고 자료 | CP-Algorithms |
스트라센 알고리즘은 2×2 블록 행렬 곱셈을 8회 대신 7회의 부분 곱셈으로 계산한다 행렬 곱셈 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다.[1]
계산 절차는 행렬을 네 블록으로 나눈 뒤 7개의 중간 행렬 곱과 덧셈·뺄셈 조합으로 결과 블록을 만든다. 재귀적으로 적용하여 큰 행렬 곱을 가속한다. 각 단계의 상태가 무엇을 의미하는지 정의하고 초기값과 경계 입력을 검사하면 결과의 정확성을 증명하거나 테스트할 수 있다.
복잡도는 시간 O(n^log₂7)≈O(n^2.807), 추가 메모리 사용 적용 전제는 행렬 차원 보정과 부동소수점 안정성, 작은 블록에서의 전환 기준을 고려한다 실제 연산량·메모리 사용은 구현의 자료구조와 정수·실수 표현, 전처리 및 입력 크기에 따라 달라진다.
응용과 관련 기법을 보면 대형 조밀 행렬 곱셈에 사용되지만 실제 라이브러리는 캐시·SIMD와 반올림 오차를 함께 고려해 방법을 선택한다. 같은 문제라도 최악 시간 보장, 메모리 요구 사항과 정밀도·확률적인 실패 가능성에 따라 적합한 알고리즘이 달라진다.[2]