55 Additions Suffice for 3x3 Matrix Multiplication at Rank 23

당신이 거대하고 복잡한 케이크를 굽는 숙련된 셰프라고 상상해 보세요. 이 레시피는 수십 가지의 재료를 매우 특정한 방식으로 혼합할 것을 요구합니다. 컴퓨터의 세계에서 '재료를 혼합하는 것'은 숫자를 곱하는 것과 같고, '케이크를 굽는 것'은 두 개의 숫자 격자(행렬)를 곱하여 새로운 결과를 얻는 것과 같습니다. 오랫동안 수학자들은 이 작업을 수행하는 유일한 방법이 표준적이고 느린 레시피, 즉 모든 숫자를 하나씩 곱한 다음 그것들을 더하는 방식뿐이라고 생각했습니다. 하지만 1960년대에 스트라센(Strassen)이라는 천재가 마법 같은 기술을 발견했습니다. 그는 재료를 섞는 순서를 재배치하면 무거운 작업을 건너뛸 수 있다는 사실을 깨달았습니다. 덕분에 똑같이 맛있는 케이크를 만들면서도, 가장 비용이 많이 들고 시간이 오래 걸리는 단계인 '곱셈'을 더 적게 수행할 수 있게 된 것입니다.

하지만 여기에는 함정이 있습니다. 곱셈의 횟수를 줄이는 대신, 재료를 준비하기 위해 더 많은 '덧셈'(혼합용 그릇)을 수행해야 하는 경우가 많습니다. 이것을 이렇게 생각해 보세요. 단순히 밀가루를 그릇에 붓는 대신, 재료들을 결합하기 전에 아주 특정한 춤을 추듯 자르고, 젓고, 접는 과정을 거쳐야 할 수도 있습니다. 목표는 가능한 한 가장 적은 단계의 움직임을 사용하는 완벽한 댄스 루틴을 찾는 것입니다. 이 논문은 당신이 읽게 될 내용으로, 특정 유형의 케이크, 즉 3x3 행렬을 위한 더 효율적인 댄스를 찾아낸 한 팀에 관한 이야기입니다. 그들은 무거운 작업(곱셈)의 횟수를 바꾼 것이 아니라, 혼합 단계(덧셈)를 줄여서 작업량을 아주 미세하지만 유의미하게 단축했습니다.

새로운 기록을 세운 댄스

Logical AI의 삼루디 카루나라트네(Samurdhi Karunaratne)와 아누슈카 이다메코랄라(Anushka Idamekorala)가 작성한 이 논문은 두 개의 3x3 숫자 격자를 곱하는 새로운 기록을 발표합니다. 그들은 단 55번의 덧셈과 23번의 곱셈만으로 이를 수행하는 방법을 찾아냈습니다.

이것이 왜 대단한 일인지 이해하기 위해 이전의 최고 기록이었던 레시피를 떠올려 보세요. 선(Sun)이라는 연구자가 만든 현재의 챔피언 레시피는 56번의 덧셈을 필요로 했습니다. 이 논문의 저자들은 완전히 새로운 곱셈 방식을 발명한 것이 아닙니다. 대신, 그들은 기존의 공개된 레시피(페르미노브(Perminov)가 만든 것)를 가져와서, 이 레시피가 58번의 덧셈을 사용하거나 이전 버전에서 59번의 덧셈을 사용했던 점을 활용하여 '준비' 단계를 최적화했습니다. 그들은 재료를 미리 혼합하는 방식을 재배치함으로써 총 덧셈 단계를 55단계로 줄일 수 있다는 것을 깨달았습니다.

그들의 새로운 '주방'이 어떻게 작동하는지 세 가지 간단한 단계로 나누어 설명하겠습니다:

1. 왼쪽 재료 준비하기: 혼합하기 전에, 그들은 첫 번째 숫자 격자(이하 "왼쪽" 격자)를 가져와 13번의 간단한 덧셈 또는 뺄셈 단계를 거쳐 23개의 특별한 혼합물을 만듭니다.
2. 오른쪽 재료 준비하기: 두 번째 격자(이하 "오른쪽" 격자)에 대해서도 동일하게 수행하며, 23개의 특별한 혼합물을 만들기 위해 14번의 단계를 사용합니다.
3. 거대한 혼합과 최종 조립: 왼쪽과 오른쪽 격자의 서로 일치하는 혼합물들을 곱합니다(총 23번의 곱셈). 그런 다음, 그 23개의 결과물을 가져와 최종 3x3 결과를 조립하기 위해 28번의 추가 덧셈 단계를 수행합니다.

왼쪽과 오른쪽의 준비 작업(13 + 14)과 최종 조립(28)을 모두 더하면 정확히 55번의 덧셈이 됩니다. 이는 이전의 최고 기록보다 하나 적은 수치로, 이 특정 유형의 계산을 위한 가장 효율적인 방법입니다.

이것이 갖는 의미 (그리고 의미하지 않는 것)

여러분은 "이것이 정말 가능한 최선의 방법인가?"라는 의문을 가질 수도 있습니다. 저자들은 다음과 같이 신중하게 밝히고 있습니다: 반드시 그렇지는 않다는 것입니다. 그들은 자신들이 선택한 이 특정한 재료 배치에 대해서는 55번이 최선이라는 것을 증명했습니다. 그들은 수학적인 탐색을 통해 이 특정 레시피를 위해서는 더 적은 단계로 진행할 수 없음을 입증했습니다. 하지만, 재료의 배치 자체가 완전히 다른 또 다른 레시피가 있다면 훨씬 더 빠를 수도 있다는 점을 인정합니다. 그들은 아직 그것을 찾아내지 못했으며, 행렬 곱셈의 전체 미스터리를 해결했다고 주장하는 것도 아닙니다.

또한, 이것이 단순히 운 좋은 추측이나 틀릴 수도 있는 컴퓨터 시뮬레이션이 아니라는 점도 명확히 합니다. 그들은 진실에 대한 '증명서'를 제공했습니다. 그들은 전체 단계별 레시피(이를 '직선 프로그램'이라 부릅니다)를 작성했고, 레시피가 작동하기 위해 반드시 성립해야 하는 729개의 모든 수학적 규칙을 확인하기 위해 여러 독립적인 컴퓨터 프로그램(Python 및 Node.js로 작성됨)을 실행했습니다. 모든 검사가 통과되었습니다. 이는 수학적으로 견고하며, 곱셈의 순서가 중요한 특이한 숫자 체계에서도 이 레시피가 완벽하게 작동함을 의미합니다.

커튼 뒤의 AI

이 이야기는 레시피가 어떻게 발견되었는지에 대한 흥미로운 반전을 담고 있습니다. 저자들은 인간 연구자가 AI 시스템(구체적으로 OpenAI의 GPT-5.6 Sol을 사용하는 에이전트)을 가이드하여 이 레시피를 발견했음을 밝힙니다. 인간은 "56번 덧셈 기록을 깰 방법을 찾아라"라는 목표를 설정했습니다. AI는 기존 레시피의 지형을 탐색하다가, 페르미노브의 58번 덧셈 버전을 찾아냈고, 준비 단계를 미세하게 조정함으로써 세 번의 추가 동작을 줄일 수 있다는 것을 깨달았습니다. 그 후 AI는 자신의 작업을 재검토하고, 코드를 작성했으며, 수학적 검증까지 마쳤습니다. 이는 인간과 기계가 협력하는 완벽한 사례입니다. 인간은 방향과 '왜'를 제공했고, AI는 수백만 가지의 가능성 속에서 '어떻게'를 찾기 위해 무거운 작업을 처리했습니다.

결국, 이 논문은 작지만 정밀한 승리입니다. 이는 행렬 곱셈처럼 오래된 분야에서도, 자세히 들여다본다면 여전히 발견되기를 기다리고 있는 아주 작고 숨겨진 효율성이 존재한다는 것을 보여줍니다. 이것은 익숙한 숲속에서 약간 더 짧은 길을 찾아내는 것과 같습니다. 여전히 같은 목적지에 도착하지만, 단 한 걸음을 덜 걷게 되는 것입니다.