Abstract: 반세기를 넘나든 수학적 도전#

1969년 볼커 스트라센이 발견한 혁신적 행렬 곱셈 알고리즘은 컴퓨터 과학사의 전환점이었다. 2×2 행렬 곱셈을 8번이 아닌 7번의 곱셈만으로 해결하는 이 방법은 “당연하다고 여겨지는 것"에 대한 첫 번째 도전이었다. 그리고 2025년, AI 시스템 AlphaEvolve가 56년간 깨지지 않던 복소수 행렬 곱셈 기록을 갱신하며 새로운 장을 열었다. 인간의 창의성에서 시작되어 인공지능의 발견으로 이어진 이 여정은 수학과 컴퓨팅의 미래를 보여주는 완벽한 서사다.

알아야 할 인물과 배경 지식#

볼커 스트라센 (Volker Strassen)#

1936년 독일에서 태어난 수학자로, 알고리즘 이론과 복잡도 이론 분야의 선구자다. 1969년 자신의 이름을 딴 스트라센 알고리즘을 발표하면서 행렬 곱셈에 대한 기존 관념을 뒤흔들었다. 이 논문의 제목은 “가우스 소거법은 최적이 아니다(Gaussian Elimination is not Optimal)“였는데, 이는 수학계에 던진 일종의 선전포고였다. 스트라센은 단순히 더 빠른 알고리즘을 제시한 것이 아니라, 수세기 동안 최적이라고 여겨졌던 방법들이 실제로는 개선의 여지가 있다는 것을 증명했다. 그의 연구는 이후 수많은 연구자들이 더 효율적인 알고리즘을 찾기 위해 노력하는 계기가 되었고, 현재까지도 알고리즘 복잡도 이론의 기초가 되고 있다.

행렬 곱셈의 기본 개념#

행렬 곱셈은 두 개의 행렬을 곱해서 새로운 행렬을 만드는 연산이다. 가장 단순한 2×2 행렬의 경우를 생각해보자. 행렬 A와 B를 곱할 때, 결과 행렬 C의 각 원소는 A의 행과 B의 열을 곱해서 더한 값이다. 전통적인 방법으로는 2×2 행렬 곱셈에 총 8번의 곱셈이 필요하다. 이는 매우 직관적이고 자연스러운 방법이어서, 수학자들은 이것이 최선이라고 생각했다. 하지만 행렬의 크기가 커질수록 필요한 계산량은 급격히 증가한다. n×n 행렬의 경우 O(n³)의 복잡도를 가지는데, 이는 행렬의 크기가 두 배가 되면 계산량이 8배로 늘어난다는 의미다. 컴퓨터 그래픽, 인공지능, 과학 계산 등 현대 컴퓨팅의 거의 모든 영역에서 행렬 곱셈이 핵심적으로 사용되기 때문에, 이 연산의 효율성은 전체 시스템 성능에 직결된다.

AlphaEvolve와 AlphaTensor#

구글 딥마인드에서 개발한 AI 시스템들로, AlphaTensor는 행렬 곱셈에 특화되어 설계된 시스템이었다. 하지만 복소수 값 행렬에 대해서는 스트라센 알고리즘을 뛰어넘지 못했다. 반면 AlphaEvolve는 범용 목적으로 설계된 시스템임에도 불구하고, 56년간의 난제를 해결해냈다. 이는 특화된 시스템보다 일반적인 시스템이 더 창의적인 해법을 찾아낼 수 있음을 보여주는 놀라운 사례다. AlphaEvolve는 강화학습과 진화 알고리즘을 결합한 하이브리드 접근법을 사용하여, 인간이 수십 년간 시도해도 찾지 못한 수학적 패턴을 발견했다.

1969년의 혁신: 스트라센의 7번 곱셈#

기존 방법의 한계#

행렬 곱셈을 배울 때 우리가 처음 배우는 방법은 매우 직관적이다. 2×2 행렬 두 개를 곱할 때:

[a b] × [A C] = [aA+bB  aC+bD]
[c d]   [B D]   [cA+dB  cC+dD]

결과 행렬의 각 원소를 계산하려면 총 8번의 곱셈이 필요하다:

aA, bB, aC, bD, cA, dB, cC, dD

이 방법은 너무나 자연스러워서 다른 방법이 있을 거라고 생각하기 어렵다. 마치 1+1=2처럼 당연한 것으로 여겨졌다.

스트라센의 놀라운 발견#

스트라센은 똑같은 결과를 7번의 곱셈만으로 얻을 수 있는 방법을 발견했다. 핵심 아이디어는 중간 계산값들을 영리하게 조합하는 것이었다:

7개의 중간값 계산:

M₁ = (a+d) × (A+D)
M₂ = (c+d) × A
M₃ = a × (C-D)
M₄ = d × (B-A)
M₅ = (a+b) × D
M₆ = (c-a) × (A+C)
M₇ = (b-d) × (B+D)

최종 결과 조합:

결과₁₁ = M₁ + M₄ - M₅ + M₇
결과₁₂ = M₃ + M₅
결과₂₁ = M₂ + M₄
결과₂₂ = M₁ - M₂ + M₃ + M₆

언뜻 보기에는 더 복잡해 보이지만, 핵심은 곱셈 횟수다. 덧셈과 뺄셈은 상대적으로 빠른 연산이므로, 곱셈 횟수를 줄이는 것이 전체 성능 향상의 열쇠였다.

분할정복의 마법#

스트라센 알고리즘의 진짜 힘은 재귀적 적용에 있다. 큰 행렬을 작은 블록으로 나누고, 각 블록에 대해 같은 방법을 반복 적용할 수 있다는 점이다.

예를 들어 4×4 행렬은 2×2 블록 4개로 나눌 수 있고, 각 블록의 곱셈에 스트라센 알고리즘을 사용하면:

기존 방법: 8³ = 512번의 기본 곱셈
스트라센 방법: 7³ = 343번의 기본 곱셈

이 차이는 행렬 크기가 커질수록 기하급수적으로 벌어진다.

복잡도 이론의 새로운 지평#

O(n³)에서 O(n^2.807)로#

스트라센 알고리즘의 복잡도는 O(n^log₂7) ≈ O(n^2.807)이다. 이는 다음을 의미한다:

1000×1000 행렬의 경우:

기존 방법: 약 10억 번의 기본 연산
스트라센 방법: 약 5억 번의 기본 연산 (거의 2배 빠름)

10,000×10,000 행렬의 경우:

기존 방법: 약 1조 번의 기본 연산
스트라센 방법: 약 4천억 번의 기본 연산 (2.5배 이상 빠름)

실용성의 딜레마#

하지만 현실은 복잡하다. 스트라센 알고리즘은 이론적으로는 더 빠르지만, 실제 구현에서는 몇 가지 문제가 있다:

메모리 사용량 증가: 중간 계산값들을 저장하기 위해 더 많은 메모리가 필요하다.

수치적 안정성: 덧셈과 뺄셈이 많아지면서 반올림 오차가 누적될 수 있다.

작은 행렬에서의 오버헤드: 행렬이 작을 때는 추가적인 덧셈/뺄셈 비용이 곱셈 절약 효과를 상쇄한다.

실제로는 보통 500×500 또는 1000×1000 이상의 행렬에서만 스트라센 알고리즘이 유의미한 성능 향상을 보인다.

56년간의 침묵을 깬 복소수 행렬의 비밀#

복소수 행렬의 특별함#

스트라센의 발견 이후, 수많은 연구자들이 더 효율적인 알고리즘을 찾기 위해 노력했다. 실제로 실수 행렬에 대해서는 여러 개선사항들이 발견되었다:

위노그라드 개선 (1971): 덧셈 횟수를 18번에서 15번으로 줄임 최근 최적화 (2017, 2023): 덧셈 횟수를 12번까지 줄임

하지만 복소수 값 4×4 행렬에 대해서는 다른 이야기였다. 복소수는 실수와 허수 부분을 모두 가지고 있어 계산이 더 복잡하다. 더 중요한 것은 재귀 적용 가능성이었다.

Winograd vs Strassen의 결정적 차이#

많은 사람들이 놓치는 중요한 점이 있다. 사실 48번의 곱셈으로 4×4 행렬을 계산하는 방법은 이전에도 존재했다. 바로 Winograd 알고리즘이다.

하지만 핵심은 재귀 적용 가능성에 있었다:

복소수의 특성: 교환법칙이 성립 (a×b = b×a) 행렬 곱셈의 특성: 비교환적 (A×B ≠ B×A)

Strassen 알고리즘이 혁신적이었던 이유는 이런 비교환적 특성에도 불구하고 더 큰 행렬에 재귀적으로 적용할 수 있었기 때문이다. Winograd의 48-곱셈 알고리즘은 같은 방식으로 재귀 적용할 수 없었다.

2025년의 혁신: AlphaEvolve의 돌파구#

AI가 발견한 새로운 수학#

AlphaEvolve가 달성한 것은 복소수 값 4×4 행렬 곱셈에서 스칼라 곱셈 횟수를 49번에서 48번으로 줄인 것이다. 겉으로 보기에는 단 1번의 차이에 불과해 보이지만, 이것이 왜 혁명적인지 이해하려면 다음을 고려해야 한다:

역사적 의미: 달 착륙 이전부터 지속된 56년간의 기록을 깨뜨린 것

기술적 혁신: Winograd와 달리 재귀적으로 적용 가능한 최초의 범용적 개선

AI의 창의성: 특화된 AlphaTensor보다 범용 시스템이 더 나은 해법 발견

인간이 놓친 패턴#

AlphaEvolve의 알고리즘은 특성 0을 가진 모든 체(field)에서 작동하며, 행렬 곱셈이 비교환적임에도 불구하고 더 큰 행렬에 재귀적으로 적용될 수 있다. 이는 인간 수학자들이 반세기 넘게 놓친 수학적 구조를 AI가 발견했다는 것을 의미한다.

특히 주목할 점은 AlphaEvolve가 행렬 곱셈에만 특화된 시스템이 아니라는 것이다. 이전의 AlphaTensor는 행렬 곱셈을 위해 특별히 설계되었지만 복소수 행렬에서는 한계를 보였다. 반면 범용 시스템인 AlphaEvolve가 이 문제를 “우연히” 해결한 것은 AI의 일반화 능력과 창의성을 보여주는 놀라운 사례다.

실용적 영향과 미래 전망#

컴퓨팅 패러다임의 변화#

전 세계 컴퓨터에서 매초 수행되는 수많은 행렬 곱셈을 고려할 때, 이런 작은 개선도 엄청난 효율성 향상과 에너지 절약을 의미한다:

직접적 영향:

스마트폰 배터리 수명 연장
데이터센터 전력 소비 감소
AI 훈련 시간 단축
그래픽 처리 속도 향상

장기적 효과:

새로운 알고리즘의 하드웨어/소프트웨어 적용
컴퓨팅 효율성의 전반적 향상

AI의 수학적 창의성#

이번 성과에서 가장 인상적인 점은 AI가 단순히 영리한 구현이나 최적화 기법을 발견한 것이 아니라는 것이다. AlphaEvolve는 인간이 반세기 넘게 놓친 증명 가능하게 더 나은 알고리즘을 발견했다.

이는 AI가 핵심 수학 영역에서 인간의 지식을 실질적으로 발전시킨 진정한 순간을 보여준다. 수십 년간 우리를 피해간 다른 수학적 돌파구들도 이제 손에 닿을 수 있는 거리에 있을지 모른다.

이론적 한계와 갤럭틱 알고리즘#

더 빠른 알고리즘들의 딜레마#

스트라센 이후로도 이론적으로 더 빠른 알고리즘들이 개발되었다. 코퍼스미스-위노그라드 알고리즘 같은 것들은 더 나은 점근적 복잡도를 가지지만, “갤럭틱 알고리즘"이라고 불린다. 실제로 유용해지려면 행렬 크기가 우주의 원자 수보다 커야 할 정도로 큰 상수항을 가지기 때문이다.

현재까지도 실용적인 범위에서는 스트라센 알고리즘의 변형이 가장 효율적인 해법 중 하나로 여겨진다. AlphaEvolve의 발견은 이런 실용적 범위에서의 개선이라는 점에서 더욱 의미가 크다.

범용 vs 특화 시스템의 역설#

예상을 뒤엎은 결과#

AlphaTensor (특화 시스템):

행렬 곱셈만을 위해 설계
인간의 도메인 지식으로 최적화
복소수 행렬에서는 한계 봉착

AlphaEvolve (범용 시스템):

다양한 문제를 해결하도록 설계
더 일반적인 탐색 능력
예상 밖의 해법 발견

이는 때로는 특화된 전문성보다 넓은 시야가 더 혁신적일 수 있다는 중요한 교훈을 준다. 인간의 사고에서도 전문 분야에 갇히지 않고 다양한 관점을 유지하는 것의 중요성을 시사한다.

컴퓨터 과학사에 미친 영향#

패러다임의 이중 전환#

스트라센의 발견이 첫 번째 패러다임 전환이었다면, AlphaEvolve의 성과는 두 번째 전환점이다:

1969년 스트라센: “최적이라고 여겨지는 알고리즘도 개선될 수 있다” 2025년 AlphaEvolve: “AI가 인간의 수학적 지식을 실질적으로 확장할 수 있다”

연구 방법론의 혁신#

과거의 접근법:

논리적 추론 → 가설 설정 → 검증
인간의 직관과 수학적 통찰에 의존

새로운 가능성:

AI의 패턴 인식과 대규모 탐색
인간이 놓친 조합의 체계적 발견
인간-AI 협력 모델

결론: 두 혁신이 만든 새로운 미래#

스트라센 알고리즘에서 시작된 행렬 곱셈 최적화의 여정이 AlphaEvolve의 혁신으로 새로운 장을 열었다. 1969년 인간의 창의적 사고가 “당연한 것"에 의문을 제기했다면, 2025년에는 AI의 탐색 능력이 인간이 56년간 찾지 못한 답을 발견했다.

이 두 사건을 관통하는 공통점은 고정관념에 대한 도전이다. 스트라센은 8번의 곱셈이 필수라는 고정관념을 깨뜨렸고, AlphaEvolve는 인간만이 수학적 발견을 할 수 있다는 고정관념을 깨뜨렸다.

단기적 영향 (1-5년):

새로운 알고리즘의 하드웨어/소프트웨어 적용
다른 수학 문제에 유사한 AI 시스템 적용 시도

중기적 영향 (5-15년):

AI가 수학자의 연구 파트너가 됨
새로운 수학적 발견들이 연쇄적으로 나타날 가능성

장기적 영향 (15년+):

과학 연구 방법론의 근본적 변화
인간-AI 협력 모델의 새로운 표준 확립

56년간 깨지지 않던 기록이 무너진 오늘, 우리는 인공지능이 인간의 창조적 파트너로서 미지의 영역을 탐험하는 새로운 시대의 문턱에 서 있다. 스트라센이 1969년에 심은 의문의 씨앗이, 반세기를 넘어 AI와 인간이 함께 키워낸 새로운 수학적 진리로 꽃피었다. 다음에는 또 어떤 불가능해 보이는 벽이 무너질까? 그 답은 아마도 우리가 상상하는 것보다 훨씬 빨리 나올 것이다.

스트라센에서 AlphaEvolve까지: 56년간의 행렬 곱셈 혁신사