AI가 발견한 더 빠른 행렬과 전치행렬 간 곱셈 알고리즘 : RXTX

 

데이터 분석, 통계학, 기계학습 등 다양한 분야에서는 행렬 X와 그 전치행렬 Xᵗ의 곱(X Xᵗ)을 자주 계산합니다. 예를 들어, 회귀분석에서 사용하는 공분산 행렬이나, 딥러닝에서 입력 데이터 간의 상관성을 나타낼 때 이러한 곱셈이 등장하죠. 이 연산은 기본적으로 일반적인 행렬 곱셈만큼 복잡하지만, 이 연산 특유의 구조적 특성을 살리면 더 빠르게 처리할 수 있다는 점에서 많은 연구가 이어지고 있습니다.

 

이런 흐름 속에서 인공지능 기술이 새로운 해법을 제시했습니다. 기계학습 기반의 탐색 알고리즘과 조합 최적화 기법을 결합해 XXᵗ 계산을 더 빠르게 수행하는 새로운 알고리즘 RXTX를 제안된 것입니다. 기존 최고 수준의 알고리즘보다 약 5% 적은 연산량으로 결과를 도출하며, 심지어 작은 크기의 행렬에서도 성능 개선을 보인다는 점에서 큰 의미를 가집니다.

 

이처럼 RXTX는 단순히 이론적인 발전에 머무르지 않고, 실제 하드웨어 환경에서도 빠른 실행 속도를 보이며 실용적인 가능성을 제시하고 있습니다.

---

RXTX

 

1) 기존 방식의 문제점

 

기존의 행렬 곱셈 알고리즘은 Strassen 알고리즘과 같은 고속 행렬 곱셈 기법을 활용하였습니다. 특히 XXᵗ와 같은 특수한 구조를 가진 연산도 일반적인 곱셈으로 환원해 계산했습니다. 하지만 이런 방식은 구조적 특징을 활용하지 못해 불필요한 연산이 포함되고, 성능 개선에 한계가 있었습니다.

 

가장 널리 쓰이던 방법은 2×2 블록 행렬로 분할해 Strassen 방식을 적용하는 것으로, 이는 성능을 어느 정도 개선했지만 여전히 연산량 측면에서 최적은 아니었습니다.

---

2) 접근 방식

 

RXTX는 전통적인 수학적 유도 방식이 아닌, AI 기반 탐색 방식을 도입해 만들어진 알고리즘입니다. 특히 강화학습과 정수계획법(MILP)을 결합한 새로운 탐색 전략을 통해 가장 적은 연산으로 XXᵗ를 계산할 수 있는 방법을 발견했습니다.

 

구체적으로는 4×4 블록으로 행렬을 분할하고, 총 8번의 재귀 호출과 26개의 일반 곱셈만으로 XXᵗ를 계산합니다. 이는 기존 방법보다 적은 재귀 호출과 연산량으로 동일한 결과를 얻을 수 있게 해 줍니다.

 

그림 : RXTX 와 기존 방식과의 곱셈 수 비교

 

---

3) 세부 적용 기술

 

1️⃣ 블록 행렬 분할 및 재귀적 계산

• RXTX는 입력 행렬 X를 4×4 블록 형태로 나눈 후, 이를 이용한 재귀적 계산을 수행합니다.
• 일반적으로 재귀 호출은 연산량을 줄이기 위한 핵심 기법으로, RXTX는 8번의 재귀 호출로 XXᵗ를 구성합니다.

2️⃣ 연산 최적화 (곱셈 수 감소)

• RXTX는 총 26개의 일반 곱셈만으로 XXᵗ를 계산합니다.
• 이는 기존 방식(16회 재귀, 24개 곱셈)보다 효율적이며, 총 곱셈 수는 약 5% 감소한 수준입니다.

3️⃣ 덧셈 최적화 (공통 부분식 활용)

• 원래는 139개의 덧셈이 필요했지만, 공통 부분식을 활용해 이를 100개까지 줄였습니다.
  예) X6 + X7 같은 표현이 반복적으로 등장하는 부분을 미리 계산하여 재활용합니다.

4️⃣ AI 기반 탐색 구조

• 강화학습 기반의 Large Neighborhood Search를 사용해, 가능한 많은 조합 중에서 최적의 곱셈 구조를 탐색합니다.
• MILP(Mixed Integer Linear Programming)를 이용해 수학적으로 가장 연산이 적은 조합을 추출합니다.

 

4) 실제 실행 시간 비교

• 기존의 수학 라이브러리(BLAS)를 이용하는 경우와의 비교에서도 99% 실행 케이스에서 RXTX가 더 빨랐습니다.
• BLAS 대비 평균 약 9% 정도의 성능 향상이 있었습니다. 

그림 : 기존 BLAS 방식 대비 런타임 속도 비교

---

5) 제약사항

 

RXTX는 특정 하드웨어 환경(예: CPU 단일 스레드, 특정 BLAS 구현 등)에 따라 성능이 달라질 수 있습니다. 따라서 실제 적용 시에는 환경에 맞춘 최적화가 필요합니다. 또한 매우 작은 행렬의 경우, 기존의 단순한 방법이 오히려 더 빠를 수 있으므로, 적절한 크기에서 RXTX를 적용하는 것이 중요합니다. 

---

 

RXTX는 전치행렬과의 곱을 효율적으로 수행하는 새로운 알고리즘으로 인공지능이 수학적 알고리즘 설계에 직접 기여할 수 있음을 보여주었습니다. RXTX는 5% 수준의 연산량 절감을 통해 실제 실행 속도도 향상시키며, 특히 데이터 분석, 통계, 머신러닝 등 대규모 행렬 연산이 빈번한 분야에서 큰 효과를 기대할 수 있습니다.

 

현재 AI모델의 학습, 추론에서 행렬 연산이 거의 대부분의 자원과 시간을 사용하고 있다는 것은 잘 알려진 사실입니다. 5%가 크지 않게 보일 수도 있지만, 이런 계산이 엄청나게 반복적으로 일어나고 누적되기 때문에 이번 새로운 알고리즘의 개발은 큰 의미를 가질 수 있습니다.

 

그러니, 이 기법이 AI 쪽에서 사용하는 라이브러리에 얼마나 빨리, 안정적으로 적용될 수 있을지가 관건이겠네요. 그럴리야 없겠지만... 정말 정말 단순하게 생각해 본다면 이런 생각을 해 볼 수도 있지 않을까요? NVIDIA가 CUDA 라이브러리에 이 알고리즘을 반영한다면 성능이 그만큼 좋아지겠지만 자사의 GPU 수요가 5% 가량 감소할 수도 있지 않나 하는... 그래도 저는 기술 발전을 거스를수는 없다는 생각이긴 합니다. 그러니 조만간 이 기술이 반영된 소프트웨어가 나올 것으로 기대합니다. ^^;

 

---

참고자료

• 논문) XXt Can Be Faster (링크)

---

Q&A

 

Q. RXTX는 어떤 상황에서 가장 효과적인가요?

RXTX는 특히 대형 행렬의 전치곱 연산이 반복적으로 필요한 경우, 예를 들어 통계 분석, 딥러닝, 무선통신 등에서 매우 효과적입니다.

 

Q. 왜 AI를 활용해야 했나요? 전통적인 수학적 방법으로는 안 되나요?

전통적인 방법으로는 탐색 공간이 너무 커서 사람이 일일이 설계하기 어렵습니다. AI는 수많은 후보 중 최적의 구조를 빠르게 탐색할 수 있는 강력한 도구입니다.

 

Q. 작은 크기의 행렬에는 RXTX가 비효율적인가요?

작은 행렬에는 재귀 호출이 오히려 부담이 될 수 있어, 기존의 단순한 방법이 더 나은 경우도 있습니다. 논문에서는 이를 고려해 적절한 크기부터 RXTX를 사용하는 것이 좋다고 언급합니다.