2025-11-27T11:04:19.442540

A non-commutative algorithm for multiplying 4x4 matrices using 48 non-complex multiplications

Dumas, Pernet, Sedoglavic

The quest for non-commutative matrix multiplication algorithms in small dimensions has seen a lot of recent improvements recently. In particular, the number of scalar multiplications required to multiply two $4\times4$ matrices was first reduced in \cite{Fawzi:2022aa} from 49 (two recursion levels of Strassen's algorithm) to 47 but only in characteristic 2 or more recently to 48 in \cite{alphaevolve} but over complex numbers. We propose an algorithm in 48 multiplications with only rational coefficients, hence removing the complex number requirement. It was derived from the latter one, under the action of an isotropy which happen to project the algorithm on the field of rational numbers. We also produce a straight line program of this algorithm, reducing the leading constant in the complexity, as well as an alternative basis variant of it, leading to an algorithm running in $7 n^{2+\frac{\log_2 3}{2}} +o\left(n^{2+\frac{log_2 3}{2}}\right)$ operations over any ring containing an inverse of 2.

academic

4×4 행렬 곱셈을 48개의 비복소수 곱셈으로 계산하는 비교환 알고리즘

기본 정보

논문 ID: 2506.13242
제목: A non-commutative algorithm for multiplying 4×4 matrices using 48 non-complex multiplications
저자: Jean-Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic
소속: Univ. Grenoble Alpes (Dumas & Pernet), Univ. Lille (Sedoglavic)
분류: cs.SC (기호 계산)
발표 시간: 2025년 11월 27일 (arXiv 사전인쇄본)
논문 링크: https://arxiv.org/abs/2506.13242

초록

본 논문은 48번의 스칼라 곱셈을 사용하여 4×4 행렬 곱셈을 계산하는 비교환 알고리즘을 제시한다. 이 알고리즘은 유리수 계수만을 사용하며 복소수가 필요 없다. 이는 AlphaEvolve11에서 제시한 복소수 영역 알고리즘의 개선으로, 등거리 변환(isotropy)을 통해 유리수 영역으로 투영한 것이다. 논문은 직선 프로그램(straight-line program) 구현을 제공하며, 2의 역원을 포함하는 임의의 환에서 $7n^{2+\frac{\log_2 3}{2}} + o(n^{2+\frac{\log_2 3}{2}})$ 의 연산 복잡도를 달성하는 대체 기저 변형을 제시한다.

연구 배경 및 동기

문제 배경

핵심 문제: 소규모 차원 행렬 곱셈의 최적 비교환 알고리즘 탐색, 특히 필요한 스칼라 곱셈 횟수 감소. 행렬 곱셈은 컴퓨터 과학과 수치 계산의 기본 연산이며, 그 효율성은 수많은 응용 분야의 성능에 직접 영향을 미친다.
중요성:
- 행렬 곱셈의 시간 복잡도는 선형대수 계산, 기계학습, 과학 계산 등 분야의 효율성에 직접 영향
- Strassen 알고리즘(1969)은 복잡도를 $O(n^3)$ 에서 $O(n^{2.81})$ 로 처음 단축하여 빠른 행렬 곱셈 연구의 문을 열었음
- 소규모 차원 행렬 곱셈 알고리즘은 재귀적으로 대규모 행렬에 적용 가능하여 실제 응용 가치 있음
기존 방법의 한계:
- Strassen 알고리즘은 4×4 행렬에서 49번의 곱셈 필요(2층 재귀)
- Fawzi 등5은 특성 2인 체에서 47번의 곱셈 달성
- AlphaEvolve11은 대형 언어 모델과 진화 코딩 에이전트를 사용하여 48번의 곱셈 알고리즘 발견, 하지만 복소수 계수 필요
- 복소수 계수는 정수환, 유한체 등 특정 환에서의 알고리즘 적용을 제한
연구 동기:
- 복소수 요구 사항 제거로 더 광범위한 대수 구조에서 알고리즘 적용 가능하게 함
- 텐서 분해 이론의 대칭성(등거리 군 작용)을 활용하여 체계적으로 알고리즘 변환
- 실용적인 직선 프로그램 구현 제공 및 상수항 최적화

핵심 기여

주요 이론적 기여: AlphaEvolve 알고리즘의 등거리 궤도(isotropy orbit)에 유리수 점이 존재함을 증명하고, 48번의 곱셈을 갖는 순수 유리수 계수 알고리즘 제시
방법론적 기여: 텐서 분해의 등거리 군 이론을 체계적으로 적용하여 등거리 변환(식 24)을 통해 복소수 영역 알고리즘을 유리수 영역으로 투영
실용적 기여:
- 완전한 직선 프로그램 구현 제공(목록 1-4), 총 341개 연산
- 이론적 복잡도 한계: $11.65625n^{2.792} - 10.65625n^2$
- 대체 기저 변형 제공, 6개 연산만 필요(1+2+3), 복잡도 $7n^{2.792}$
일반성: 알고리즘은 2의 역원을 포함하는 모든 환에 적용 가능하여 응용 범위 확장
오픈소스 구현: 모든 행렬과 코드가 PLinOpt 라이브러리에서 공개 가능

방법 상세 설명

작업 정의

입력: 두 개의 4×4 행렬 $A = (a_{ij})$ 와 $B = (b_{ij})$ , 원소는 $\frac{1}{2}$ 를 포함하는 환 $R$ 에서 나옴
출력: 곱 행렬 $C = A \cdot B = (c_{ij})$
제약: 스칼라 곱셈 횟수 최소화, 유리수 계수만 사용(복소수 회피)

이론적 프레임워크: 텐서 분해 표현

1. 쌍선형 사상의 텐서 표현

행렬 곱셈은 쌍선형 사상으로 표현 가능: $\beta_{mm}: R^{m \times k} \times R^{k \times n} \rightarrow R^{m \times n}, \quad (A, B) \mapsto A \cdot B$

이 사상은 텐서 공간 $(R^{m \times k})^* \otimes (R^{k \times n})^* \otimes R^{m \times n}$ 의 텐서 분해로 인코딩됨: $T = \sum_{i=1}^r M_i \otimes N_i \otimes O_i$

여기서:

$r$ 은 텐서 계수(tensor rank), 필요한 스칼라 곱셈 횟수에 대응
각 $(M_i, N_i, O_i)$ 는 계수 1 텐서
삼선형 표현: $\text{Trace}(O_i^T \cdot M_i \cdot N_i)$

2. Strassen 알고리즘의 텐서 표현

Strassen의 2×2 행렬 곱셈 알고리즘(7번 곱셈)은 계수 7 텐서 분해에 대응, 유형은 $X^2Y^2Z^2 + 6XYZ$ .

3. 등거리 군 작용(Isotropy Group Action)

정리 2.1: 행렬 곱셈 텐서의 등거리 군: $\text{psl}_{\pm}(R^m) \times \text{psl}_{\pm}(R^k) \times \text{psl}_{\pm}(R^n) \rtimes S_3$

정의 2.2: 등거리 $g = (U \times V \times W)$ 의 계수 1 텐서 $A \otimes B \otimes C$ 에 대한 작용: $(U^{-T} \cdot A \cdot V^T) \otimes (V^{-T} \cdot B \cdot W^T) \otimes (W^{-T} \cdot C \cdot U^T)$

이는 텐서 계수를 불변으로 유지하지만 계수를 변경한다.

핵심 알고리즘 구성

핵심 등거리 변환

본 논문의 핵심 혁신은 특정 등거리 변환(식 24) 발견: $\begin{bmatrix} I & 0 & 0 & I \\ 0 & 1 & I & 0 \\ 0 & -I & -1 & 0 \\ -1 & 0 & 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} I & 0 & 0 & 1 \\ 0 & -I & -I & 0 \\ 0 & -I & I & 0 \\ -I & 0 & 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

여기서 $I$ 는 허수 단위.

유리수 계수 텐서 분해

위의 등거리 적용 후, 48개의 계수 1 텐서 분해 획득(식 25-72), 각각 형태: $m_i = \left(\sum_{j,k} \alpha_{jk}^{(i)} a_{jk}\right) \otimes \left(\sum_{j,k} \beta_{jk}^{(i)} b_{jk}\right) \otimes \left(\sum_{j,k} \gamma_{jk}^{(i)} c_{jk}\right)$

핵심 특성:

모든 계수 $\alpha, \beta, \gamma \in \{-1, -\frac{1}{2}, 0, \frac{1}{2}, 1\}$ (유리수)
텐서 유형: $16X^2Y^2Z^2 + 32XYZ$ (16개 계수 2×2×2, 32개 계수 1×1×1)
분모는 2, 4, 8의 거듭제곱만 포함

예시: 첫 번째 곱셈 항

$m_1 = \frac{1}{4}\left(\sum_{i,j} (-1)^{i+j+1} a_{ij}\right) \otimes (b_{31} + b_{41}) \otimes \left(\sum c_{terms}\right)$

LRP 행렬 표현

알고리즘은 세 개의 행렬 $(L, R, P)$ 로 간결하게 표현 가능:

$L \in R^{48 \times 16}$ : $A$ 의 원소에서 48개의 좌측 피연산자로의 선형 변환
$R \in R^{48 \times 16}$ : $B$ 의 원소에서 48개의 우측 피연산자로의 선형 변환
$P \in R^{16 \times 48}$ : 48개의 곱에서 $C$ 의 원소로의 선형 변환

계산 흐름: $\text{vec}(C) = P \cdot (L \cdot \text{vec}(A) \odot R \cdot \text{vec}(B))$

여기서 $\odot$ 는 원소별 곱셈(Hadamard 곱).

기술적 혁신점

체계화된 대칭성 활용: 시행착오 탐색이 아닌 안정자 부분군 $(C_2 \times D_4) \rtimes C_2$ 와 이론 기반 추측을 활용하여 등거리 변환 발견
복소수에서 유리수로의 투영: 고차원 복소수 공간에서 발견된 알고리즘을 유리수 부분공간으로 투영 가능함을 증명, 이는 비자명한 결과
직선 프로그램 최적화:
- PLinOpt 도구를 사용한 최적화된 직선 프로그램 자동 생성
- 핵 분해(kernel decomposition)를 통한 연산 횟수 감소
- $R$ 행렬 계수가 단순해도 최적 SLP는 비자명한 곱셈 필요 가능
대체 기저 방법: 기저 변환(change of basis)을 통한 추가 단순화, 연산을 336개로 감소(원래 341개 대비)

실험 설정

구현 도구

PLinOpt 라이브러리: 선형 및 쌍선형 프로그램 최적화를 처리하는 C++ 루틴 모음
코드 규모: 약 8.09 kSLOC (천 줄 소스 코드)
오픈소스: 모든 행렬과 코드가 GitHub에서 공개

데이터 파일

알고리즘의 다양한 표현 저장:

4x4x4_48_rational_L.sms, _R.sms, _P.sms: 표준 LRP 표현
4x4x4_48_rational-ALT_*.sms: 대체 기저 표현
4x4x4_48_rational-CoB_*.sms: 기저 변환 행렬

평가 지표

텐서 계수: 필요한 스칼라 곱셈 횟수(48)
총 연산 수: 덧셈과 이동 연산의 총 개수
점근 복잡도: $O(n^{\log_4 3}) \approx O(n^{2.792})$
상수항: 주도 상수 및 저차항 계수

실험 결과

주요 결과

표준 직선 프로그램(목록 1-4)

연산 분해:

$L$ 행렬: 104번 덧셈
$R$ 행렬: 84번 덧셈 + 1번 곱셈(이진 이동)
$P$ 행렬: 119번 덧셈 + 33번 곱셈(이진 이동)
총계: 341개 연산

복잡도 한계: $\left(1 + \frac{341}{48-16}\right)n^{2+\log_4 3} - \frac{341}{32}n^2 \approx 11.65625n^{2.792} - 10.65625n^2$

대체 기저 변형(부록 C)

연산 분해:

$L_{alt}$ : 1번 덧셈
$R_{alt}$ : 2번 덧셈
$P_{alt}$ : 3번 덧셈
총계: 6개 연산

기저 변환 오버헤드:

CoB_L: 103번 덧셈
CoB_R: 79번 덧셈 + 5번 곱셈
CoB_P: 116번 덧셈 + 33번 곱셈
총계: 336개 연산

복잡도 한계: $7n^{2.792} + \frac{336}{31}(n^{\log_4 47} - n^2) = 7n^{2.792} + o(n^{2.792})$

기존 방법과의 비교

방법	곱셈 횟수	계수 체	적용 환	복잡도 상수
Strassen (2층)	49	유리수	임의	-
Fawzi 등 5	47	유리수	특성 2	-
AlphaEvolve 11	48	복소수	복소수 체	-
본 논문(표준)	48	유리수	$\frac{1}{2}$ 포함 환	11.66
본 논문(대체 기저)	48	유리수	$\frac{1}{2}$ 포함 환	7.00

핵심 발견

존재성 증명: AlphaEvolve 알고리즘의 등거리 궤도에 유리수 점이 실제로 존재함을 증명, 이는 자명하지 않음
계수 단순성: 모든 계수가 $\{-1, -\frac{1}{2}, 0, \frac{1}{2}, 1\}$ 로 구현이 용이
최적화 역설: $R$ 행렬 계수가 $\{-1, 0, 1\}$ 만 포함하지만 최적 직선 프로그램은 여전히 비자명한 곱셈 필요(핵 분해로 인해)
대체 기저 장점: 기저 변환을 통해 주도 상수를 11.66에서 7.00으로 감소 가능, 대가는 $o(n^{2.792})$ 의 기저 변환 오버헤드

결론 및 논의

주요 결론

AlphaEvolve의 복소수 알고리즘을 유리수 알고리즘으로 성공적으로 변환, 48번 곱셈 유지
등거리 군 작용은 알고리즘 공간을 체계적으로 탐색하는 효과적인 도구
두 가지 구현 제공: 표준판(341 연산)과 대체 기저판(6+336 연산)
알고리즘은 $\frac{1}{2}$ 를 포함하는 모든 환에 적용 가능, 응용 범위 확장

한계

환의 제한: 2가 가역이어야 함, 특성 2 체에 부적합
큰 상수항: 표준판 상수 11.66이 크므로 충분히 큰 행렬에서만 유리
수치 안정성 미지: 2와 유사한 수치 정확도 분석 미완료
비구성적: 등거리 변환 발견은 여전히 "educated guesses"에 의존, 완전 자동화 미달성

향후 방향

3×4×7 알고리즘: 쌍둥이 논문3에서 AlphaEvolve의 다른 복소수 알고리즘 처리
수치 분석: 오차 전파 및 조건수 연구
자동화 발견: 등거리 변환 자동 탐색 방법 개발
다른 차원: 5×5, 3×3×3 등에 동일 방법 적용
실제 성능: 캐시, 병렬화 등을 고려한 실제 하드웨어 성능 테스트

심층 평가

장점

1. 이론적 기여 현저함

중요한 공백 해결: AlphaEvolve 알고리즘의 복소수 계수 제한이라는 실제 문제 해결
방법론 혁신: 등거리 군 이론의 체계적 적용, 복소수에서 유리수로의 이론적 경로 제공
수학적 엄밀성: Landsberg의 텐서 기하학 이론 기반, 견고한 대수 기하학 토대

2. 실용 가치 높음

완전한 구현: 직선 프로그램과 LRP 행렬 제공, 직접 사용 가능
오픈소스 재현 가능: 모든 데이터와 코드가 PLinOpt 라이브러리에서 공개
광범위한 적용성: 유리수 계수로 정수, 유리수, 유한체(홀수 특성) 등에서 사용 가능

3. 기술 세부 사항 충분함

완전한 알고리즘 표시: 식 25-72에서 모든 48개 곱셈항 상세 나열
다양한 표현: 삼선형 형식, LRP 행렬, 직선 프로그램 등 다양한 표현 제공
최적화 전략: 핵 분해 및 대체 기저 등 최적화 기법 시연

4. 명확한 작성

충분한 배경 소개: Strassen 알고리즘에서 텐서 분해 이론까지 단계적 도입
풍부한 예시: 예시 2.1에서 등거리가 복소수를 어떻게 도입하는지 시연
체계화된 기호: 명확한 정의, 일관된 기호

부족한 점

1. 방법의 한계

등거리 변환 발견: "educated guesses" 사용 인정, 체계화된 탐색 방법 부족
안정자 부분군 의존: 안정자 부분군 $(C_2 \times D_4) \rtimes C_2$ 를 이미 알아야 함, 새로운 문제에 적용 어려울 수 있음
특성 제한: 특성 2 체에 부적합(Fawzi의 47번 알고리즘이 오히려 적용 가능)