도구스개발

슈트라센 행렬 곱셈 계산기

2×2 행렬 곱셈을 8번이 아니라 7번의 곱셈으로 해내는 슈트라센 항등식을 M1~M7 단계까지 보여주고, 곧이곧대로 O(n³) 곱셈과 무작위 행렬로 대조해 곱셈 횟수가 실제로 7^k인지 확인합니다.

행렬 크기 n×n

한 줄에 한 행, 값은 공백이나 쉼표로 구분합니다.

한 줄에 한 행, 값은 공백이나 쉼표로 구분합니다.

두 결과가 일치하는가

일치

최대 오차 0.00e+0

슈트라센 곱셈 횟수7번
곧이곧대로(O(n³)) 곱셈 횟수8번
패딩된 크기2×2

M1~M7 — 2×2일 때의 자취

곱값
M1 = (A11+A22)(B11+B22)65
M2 = (A21+A22)B1135
M3 = A11(B12−B22)-2
M4 = A22(B21−B11)8
M5 = (A11+A12)B2224
M6 = (A21−A11)(B11+B12)22
M7 = (A12−A22)(B21+B22)-30

C11 = M1+M4−M5+M7 = 19 · C12 = M3+M5 = 22 · C21 = M2+M4 = 43 · C22 = M1−M2+M3+M6 = 50

재귀 단계별 부분문제 수

단계부분문제 크기슈트라센 (7^단계)곧이곧대로였다면 (8^단계)
02×211
11×178

마지막 행(크기 1×1까지 내려간 자리)의 두 값이 곧 전체 곱셈 횟수입니다. n이 커질수록 7^단계가 8^단계보다 훨씬 느리게 자라 격차가 벌어집니다.

곱셈 하나를 줄이는 대신 덧셈이 늘어나는 거래입니다. 2×2 블록 하나를 처리할 때 곱셈은 8번에서 7번으로 줄지만 덧셈·뺄셈은 4번에서 18번으로 늘어납니다. n이 커질수록 곱셈 절감이 덧셈 증가를 압도해 유리해지지만, 이 계산기가 다루는 작은 크기(n=2·4·8)에서는 실제 실행 시간이 아니라 곱셈 횟수라는 이론적 지표만 비교합니다. 실무 구현은 대개 n=32~128 이하에서는 곧이곧대로 곱하는 쪽으로 돌아갑니다.
뺄셈이 늘어난 만큼 부동소수점에서는 자릿수 손실(catastrophic cancellation)에 더 취약하다고 알려져 있습니다. 값의 크기가 크게 차이 나는 행렬을 섞으면 곧이곧대로 곱한 결과보다 오차가 커질 수 있습니다.

사용 방법

  1. 1행렬 크기(n)를 2, 4, 8 중에서 고릅니다. 2×2일 때는 M1~M7 값을 직접 볼 수 있습니다.
  2. 2두 행렬의 성분을 입력하거나 무작위 예시 버튼을 씁니다.
  3. 3곧이곧대로 곱과 슈트라센의 결과가 일치하는지, 오차가 0에 가까운지 확인합니다.
  4. 4재귀 단계표에서 슈트라센의 곱셈 수(7^level)와 곧이곧대로였다면의 수(8^level)가 얼마나 벌어지는지 봅니다.

자주 묻는 질문

2×2 블록을 곱할 때 필요한 곱셈 횟수를 8번에서 7번으로 줄입니다. M1=(A11+A22)(B11+B22)부터 M7까지 7개의 곱을 먼저 구하고, 나머지는 덧셈·뺄셈만으로 C11~C22를 조립합니다. 곱셈 하나를 줄이는 대신 덧셈이 4번에서 18번으로 늘어나는 거래입니다.

n×n 행렬을 2×2 블록(각 블록은 n/2 크기)으로 보고 블록의 곱셈을 재귀적으로 다시 이 방법으로 풀면, 곱셈 횟수의 재귀식이 T(n)=7·T(n/2)가 되어 T(n)=n^log₂7≈n^2.807이 됩니다. 곧이곧대로 곱하면 T(n)=n³이라, n이 커질수록 격차가 크게 벌어집니다.

아닙니다. 작은 행렬에서는 늘어난 덧셈과 재귀 호출의 부가비용 때문에 오히려 느릴 수 있습니다. 실무 구현은 어느 크기 밑에서는 곧이곧대로 곱하는 쪽으로 돌아가며, 그 교차점이 대개 n=32~128 근처로 알려져 있습니다. 이 계산기가 다루는 n=2·4·8은 곱셈 횟수만 이론적으로 줄어드는 것을 보여주는 것이지, 실제로 더 빠르다는 뜻은 아닙니다.

뺄셈이 늘어난 만큼 자릿수 손실(catastrophic cancellation)에 더 취약하다고 알려져 있습니다. 값의 크기가 고르면 문제되지 않지만, 크기가 크게 차이 나는 값들을 섞으면 곧이곧대로 곱한 결과보다 오차가 커질 수 있습니다.

0으로 채워(패딩) 다음 2의 거듭제곱 크기로 늘린 뒤 계산하고, 결과에서 원래 크기만큼만 잘라냅니다. 3×3 행렬은 4×4로 패딩됩니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고 입력값은 이 기기에만 남습니다.

알아두면 좋은 점

  • 곱셈 횟수는 무작위 행렬로 실제로 세어 7^log₂n(패딩된 크기 기준)과 일치하는지, 곧이곧대로는 n³번인지 크기 1·2·4·8·16·32에서 확인했습니다.
  • 슈트라센의 결과와 곧이곧대로 곱한 결과가 성분마다 일치하는지(오차 0에 가까운지) 크기 1~8에서 대조했습니다.
  • 2×2 M1~M7 값은 단위행렬·구체적 숫자 예제로 손으로 검산해 정의된 식과 일치함을 확인했습니다.
  • 실제로 더 빠른지는 다루지 않습니다. 이 계산기는 곱셈 횟수라는 이론적 지표만 비교하며, 교차점 이하 크기에서는 실제 실행 시간이 오히려 늘 수 있습니다.

함께 보면 좋은 도구

행렬 계산2×2 행렬의 덧셈·곱셈·행렬식·역행렬을 계산합니다.행렬 곱 순서행렬 크기 목록을 넣으면 곱하는 순서(괄호)에 따라 스칼라 곱셈 횟수가 얼마나 달라지는지 내고 동적 계획법으로 최적 괄호를 찾습니다.피보나치 행렬 거듭제곱[[1,1],[1,0]]ⁿ을 분할정복으로 거듭제곱해 피보나치수를 O(log n)에 구합니다.gitignore 판정.gitignore 규칙과 경로를 넣으면 그 파일이 무시되는지, 어느 줄이 마지막으로 이겼는지 알려줍니다.울프람 규칙규칙 번호 0~255를 8비트로 풀어 세 칸 이웃에 대응시키고 세대를 쌓아 무늬를 그립니다.

마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.