고속 다중극자법

1. 개요[편집]

고속 다중극자법 Fast Multipole Method (FMM)
발표	그린가드 · 로클린 (1987)
해결하는 문제	N개 원천 → N개 관측점의 전 쌍 합
복잡도	O(N²) → O(N) (고정 정확도)
자료구조	사진트리(2D) · 팔진트리(3D), 적응형
연산자	P2M · M2M · M2L · L2L · L2P + 근거리 P2P
평가	20세기 10대 알고리즘(2000년 선정)

고속 다중극자법(Fast Multipole Method, FMM)은 $N$ 개 원천이 $N$ 개 관측점에 미치는 영향의 전 쌍 합을, 지정한 정확도 안에서 $O(N)$ 연산으로 계산하는 알고리즘이다. 1987년 그린가드와 로클린이 2차원 쿨롱 문제에 대해 정식화했고, 곧 3차원과 헬름홀츠 방정식 커널로 확장되면서 경계요소법·모멘트법·중력 N체 문제의 계산 규모를 한 자릿수 이상 끌어올렸다.¹

문제는 정직하다. 아래 합을 모든 $i$ 에 대해 구하는 것.

$$\phi(\mathbf{x}_i) = \sum_{j\neq i} q_j\,K(\mathbf{x}_i,\mathbf{x}_j), \qquad K = \frac{1}{|\mathbf{x}_i-\mathbf{x}_j|}$$

곧이곧대로 하면 $N^2$ 번. $N=10^6$ 이면 $10^{12}$ 번이고, 한 스텝에 몇 시간이 걸린다. FMM이 여기에 넣는 관측은 두 개다. 첫째, 멀리 있는 원천 무리가 만드는 장은 부드럽다 — 다중극 전개로 몇 개 계수에 압축된다. 둘째, “멀다”는 관계는 계층적이다 — 상자를 반씩 쪼개 내려가면 각 층에서 “새로 멀어진” 상대만 처리하면 되고, 그 개수가 층과 무관하게 상수다. 이 둘을 합치면 총비용이 층 수와 무관하게 입자 수에 선형이 된다.

2. 트리와 여섯 개의 연산자[편집]

전체 영역을 감싸는 상자에서 시작해 재귀적으로 8등분(3차원)해 팔진트리를 만든다. 입자 밀도가 균일하면 고정 깊이로, 불균일하면 잎 상자당 입자 수가 $s$(보통 수십 개) 이하가 될 때까지 적응적으로 쪼갠다. 그다음은 위로 한 번, 아래로 한 번 훑는다.

• P2M (Particle to Multipole) — 잎 상자 안의 입자들로부터 그 상자의 다중극 계수를 만든다.
• M2M (Multipole to Multipole) — 자식 상자의 다중극을 부모 중심으로 이동해 합친다. 상향 패스는 이것의 반복이다.
• M2L (Multipole to Local) — 핵심 연산. 잘 분리된(well-separated) 상대 상자의 다중극 전개를 내 상자 중심의 국소 전개로 변환한다.
• L2L (Local to Local) — 부모의 국소 전개를 자식 중심으로 옮긴다. 하향 패스의 뼈대.
• L2P (Local to Particle) — 잎에서 국소 전개를 실제 입자 위치에서 평가한다.
• P2P (Particle to Particle) — 이웃 상자들과는 근사가 성립하지 않으므로 그냥 직접 계산한다.

핵심은 상호작용 리스트다. 어떤 상자의 M2L 상대는 “부모의 이웃들의 자식 중에서, 내 이웃이 아닌 것”으로 정의된다. 3차원에서 이 개수는 최대 $6^3 - 3^3 = 189$ 개로, 트리 깊이와 무관한 상수다. 그래서 상자 하나당 비용이 상수이고, 상자 총수가 $O(N)$ 이므로 전체가 $O(N)$ 이 된다. 흔히 “멀리 있는 건 대충 본다”로 요약되지만 더 정확한 요약은 **“멀어지는 사건은 각 입자에게 유한 번만 일어난다”**이다.

한 가지 자주 헷갈리는 점 — FMM은 상자-상자 상호작용을 다룬다. 원천 상자의 다중극을 관측 상자의 국소 전개로 한 번에 넘기므로, 그 상자 안 입자 수에 관계없이 변환 비용이 같다. 이 점이 입자-상자 상호작용만 하는 트리코드와의 결정적 구조 차이다.

3. 오차와 전개 차수[편집]

잘 분리된 상자 쌍의 거리비를 $1/c$(표준 배치에서 $c \ge 2$)라 하면, 차수 $p$ 에서 자른 오차는

$$\left|\phi - \phi_p\right| \;\lesssim\; \frac{\sum_j |q_j|}{c-1}\left(\frac{1}{c}\right)^{p+1}$$

로 기하급수적으로 줄어든다. 즉 유효숫자를 한 자리 더 원하면 $p$ 를 대략 3.3 올리면 된다. FMM이 다른 근사 알고리즘과 다른 지점이 바로 이것 — 정확도가 사용자가 돌리는 손잡이 하나($p$)로 사전에 보장된다. 필요하면 $p$ 를 키워 배정도 반올림 수준(약 $10^{-15}$)까지 갈 수 있고, 그때도 복잡도는 여전히 $O(N)$ 이다(상수만 커진다).

비용 쪽 사정은 이렇다. 3차원 전개 항 수는 $(p+1)^2$ 이고, M2L을 정직하게 행렬곱으로 하면 상자당 $O(p^4)$ 다. 이걸 낮추는 것이 FMM 구현 경쟁의 절반을 차지한다.

• 회전 기반 분해: 축 방향으로 회전해 $z$ 축 평행 이동으로 만들면 $O(p^3)$.
• 평면파/지수 전개: 그린가드-로클린의 1997년 개정판이 도입한 것으로, 상향·하향·측면 6방향으로 지수 전개를 거쳐 M2L을 대각화한다. $O(p^2)$ 로 떨어지며 오늘날 고성능 라플라스 FMM의 표준.
• 저계수 압축: 189개 M2L 행렬을 SVD로 미리 압축해 두는 방식. 커널 독립 구현에서 특히 잘 맞는다.

실무 감각으로는, 3~4자리 정확도면 $p=4{\sim}6$, 물리 시뮬레이션에서 흔히 요구하는 6자리면 $p\approx 10$ 언저리다. $p$ 를 정한 뒤에는 잎 상자 크기 $s$ 를 조절해 P2P와 M2L의 비용 균형을 맞추는데, 이 튜닝을 안 하면 $O(N)$ 알고리즘이 직접합보다 느린 참사가 실제로 벌어진다. 손익분기점은 대개 $N \sim 10^3$–$10^4$ 이고, 낮은 정확도를 요구할수록 앞당겨진다.

4. 트리코드와의 관계[편집]

FMM보다 한 해 앞선 1986년, 반스와 헛이 발표한 트리코드(반스-헛 알고리즘)는 같은 계층 아이디어를 훨씬 단순하게 쓴다. 관측 입자 하나마다 트리를 내려가며, 상자 크기 $s$ 와 거리 $d$ 가 $s/d < \theta$ 를 만족하면 그 상자를 질량중심 하나로 대체하고 더 내려가지 않는다.

항목	트리코드(반스-헛)	FMM
상호작용	입자 ↔ 상자	상자 ↔ 상자
전개 차수	보통 단극자(필요 시 사중극자)	임의 차수 p
복잡도	O(N log N)	O(N)
오차 제어	개각 θ, 경험적	p, 사전 오차 한계
구현 난도	하루	몇 주
주 사용처	천체물리·우주론	적분방정식·고정밀 전자기·정전기

천체물리가 트리코드를 계속 쓰는 이유는 명확하다. 중력 시뮬레이션의 오차 예산은 어차피 이체 완화·시간적분·초기조건이 지배하므로 1% 수준이면 충분하고, 밀도 동적 범위가 $10^6$ 을 넘는 상황에서 단순한 자료구조가 훨씬 잘 버틴다. 반면 경계요소법처럼 행렬-벡터 곱의 오차가 그대로 반복 해법의 수렴을 망치는 문제에서는 보장된 정확도가 필수라 FMM 쪽이 이긴다.

다만 트리코드의 개각 판정이 오차를 보장하지 않는다는 점은 알려져 있어야 한다. 살몬과 워런(1994)은 $\theta$ 를 고정한 표준 판정이 특정 질량 분포에서 임의로 큰 오차를 낼 수 있음을 보였고, 이후 상자의 다중극 모멘트를 반영한 개선된 판정이 표준이 됐다. “θ=0.5면 안전하다”는 것은 정리가 아니라 은하 시뮬레이션 경험칙이다.

5. 커널을 갈아 끼우기[편집]

원래 FMM은 커널마다 전개식과 이동 연산자를 손으로 유도해야 했다. 라플라스, 헬름홀츠, 스토크스, 탄성 커널마다 논문 한 편씩 나오던 시절이 있었다. 이 장벽을 낮춘 것이 두 갈래다.

• 커널 독립 FMM(잉·비로스·조린, 2004). 다중극 계수 대신, 상자를 둘러싼 등가 표면 위의 가상 원천 밀도로 원거리장을 표현한다. 필요한 것은 커널을 점에서 평가하는 함수 하나뿐이라, 새 커널에 붙이는 데 몇 시간이면 된다. 대신 등가 표면 이산화와 그 역문제의 조건수 관리가 필요하다.
• 블랙박스 FMM(퐁·다르브, 2009). 상자 안에서 커널을 체비쇼프 격자에 보간해 저계수 표현을 만들고 SVD로 압축한다. 역시 커널 평가 함수만 있으면 된다.

이 흐름의 끝에는 계층 행렬(H-행렬, HSS, ACA) 같은 순수 대수적 사촌들이 있다. 이쪽은 커널 공식을 전혀 모른 채 행렬 블록의 저계수성을 수치적으로 발견한다. FMM이 “왜 저계수인지 알고 쓰는” 쪽이라면 이쪽은 “저계수인지만 확인하고 쓰는” 쪽이고, 전자가 빠르고 후자가 범용이다.

6. 파동 커널과 주기 경계[편집]

$e^{ikR}/R$ 커널에는 두 개의 서로 다른 파탄이 있다.

• 저주파 파탄. 상자가 파장보다 훨씬 작으면 고전적 다중극 전개의 $h_l^{(1)}$ 과 $j_l$ 이 지수적으로 발산·소멸해 유한 정밀도에서 자릿수 소실이 일어난다. 저주파 안정 정식화 또는 라플라스 FMM으로의 전환이 필요하다.
• 고주파. 상자 지름 $D$ 에 대해 필요한 항 수가 $p \sim kD$ 로 자라므로 $O(N)$ 이 유지되지 않는다. 로클린의 대각 형식(1993)을 써서 M2L을 구면 위 표본점 사이의 대각 곱으로 바꾸고, 층마다 표본 수를 바꿔가며 보간하는 것이 MLFMA다. 복잡도는 $O(N\log N)$. 전투기 전기체의 레이더 단면적을 모멘트법으로 계산할 수 있게 된 것이 이 알고리즘 덕이다.

주기 경계는 또 다른 이야기다. 무한 격자합 $\sum_{\mathbf{n}} \sum_j q_j K(\mathbf{x}_i - \mathbf{x}_j + \mathbf{n}L)$ 은 쿨롱 커널에서 조건부 수렴이라 더하는 순서가 답을 바꾼다. FMM에서는 최상위 상자의 다중극을 이용해 주변 이미지 상자들의 기여를 재귀적으로 접어 올린 뒤, 발산하는 쌍극자 항을 명시적 경계 조건(진공 vs 틴폴)으로 처리한다. 사실상 에발트 합산이 실공간·역공간으로 나눠서 하던 일을 계층 구조로 다시 하는 것이다. 분자동역학 현장에서는 여전히 PME 계열이 표준이고, FMM은 아주 큰 $N$ 이나 비주기·불균일 계에서 유리해지는 선택지로 자리 잡았다.²

7. 병렬화 — 알고리즘의 절반[편집]

$O(N)$ 이라는 간판은 예쁘지만, FMM은 병렬 환경에서 다루기 까다로운 알고리즘이다. 상향·하향 패스가 트리 층마다 동기화를 요구하고, 잎 근처에는 일이 몰리고 뿌리 근처에는 일이 없다.

• 트리 분배. 입자를 공간 채움 곡선(모턴 또는 힐베르트 순서)으로 정렬해 1차원으로 편 다음 잘라 나눈다. 곡선의 국소성 덕분에 인접한 조각이 공간적으로도 뭉쳐 있어 통신량이 작다. 그래프 분할을 쓰는 것보다 훨씬 싸고, 재분할이 매 스텝 필요한 동적 문제에 특히 유리하다.
• 부하 분산. 상자마다 비용이 다르므로(적응 트리에서는 P2P 비용이 잎 입자 수의 제곱) 입자 수가 아니라 추정 작업량으로 가중해 곡선을 자른다. 살몬·워런의 “국소 필수 트리”(LET) 개념 — 각 프로세스가 자기 계산에 필요한 원격 노드만 미리 받아 두는 것 — 이 오늘날 분산 FMM 구현의 표준 패턴이다.
• 가속기. P2P는 산술 강도가 높고 규칙적이라 GPU 컴퓨팅과 궁합이 좋다. 그래서 GPU에서는 오히려 $p$ 를 낮추고 잎 상자를 키워 P2P 비중을 일부러 늘리는 튜닝이 이득인 경우가 많다. 이론적으로 최적인 파라미터와 하드웨어에서 최적인 파라미터가 다른 전형적 사례다.

구현체로는 ExaFMM, PVFMM, ScalFMM, FMM3D 등이 있고, 1990년대 초 워런과 살몬의 트리코드 계열이 고든 벨 상을 여러 차례 받으며 이 계보의 병렬 기술을 끌어올렸다.³

8. 실무에서 만나는 것들[편집]

• 정확도를 재는 법. $N$ 이 커서 정답을 모르므로, 무작위로 고른 입자 수백 개만 직접합으로 계산해 상대 오차 노름을 본다. 이때 퍼텐셜은 잘 맞는데 힘(기울기)이 한 자리 나쁜 것이 정상이다. 미분이 오차를 증폭하기 때문이며, 힘 정확도가 필요하면 $p$ 를 1~2 올린다.
• 에너지 보존과의 궁합. FMM 오차는 입자 위치의 매끄러운 함수가 아니라 트리 구조가 바뀔 때 불연속적으로 튄다. 심플렉틱 적분기의 장기 보존성이 이 불연속에 훼손될 수 있어, 장기 궤도 적분에서는 트리 재구성 빈도와 개각·차수를 보수적으로 잡는다.
• 반복 해법 안에서. 적분방정식을 풀 때 FMM은 크리로프 부분공간법의 행렬-벡터 곱을 대신한다. 이때 FMM 오차는 “행렬이 매번 조금씩 다른” 비정확 행렬곱으로 작용하므로, 수렴 판정 기준을 FMM 오차보다 아래로 잡으면 잔차가 바닥을 치고 더 안 내려간다. 이를 이용해 초반 반복에는 낮은 $p$, 후반에는 높은 $p$ 를 쓰는 완화 전략이 표준이 되었다.
• 조건수는 개선되지 않는다. FMM은 곱셈을 싸게 할 뿐 문제를 쉽게 만들지 않는다. 나쁜 조건의 적분방정식은 여전히 전처리기가 필요하고, 실제로 대규모 BEM에서 병목은 FMM이 아니라 반복 횟수인 경우가 흔하다.

9. 관련 문서[편집]

• 다중극 전개 · 구면조화 함수 · 라플라스 방정식 · 헬름홀츠 방정식
• 경계요소법 · 모멘트법 · 이산 쌍극자 근사 · 계층적 행렬
• N체 문제 · 반스-헛 알고리즘 · 에발트 합산 · 분자동역학
• 공간 채움 곡선 · 부하 분산 · 그래프 분할 · 병렬 컴퓨팅 · GPU 컴퓨팅
• 크리로프 부분공간법 · 전처리기 · 다중격자법 · 고속 푸리에 변환

10. Footnotes[편집]

1. 2000년 Computing in Science & Engineering 이 뽑은 “20세기 10대 알고리즘”에 고속 푸리에 변환, 심플렉스법, 크리로프 반복법 등과 나란히 이름을 올렸다. 목록 중 가장 늦게 태어난 축에 속하는데, 다른 항목들이 대부분 1940~60년대생인 걸 생각하면 1987년은 거의 신인이다. ↩

2. 알고리즘 복잡도와 실제 속도가 다른 대표적 사례이기도 하다. PME는 $O(N\log N)$ 이지만 고속 푸리에 변환 상수가 극도로 작고, FMM은 $O(N)$ 이지만 트리 순회·연산자 적용 상수가 크다. 수십만 원자 규모의 평범한 단백질 계에서는 여전히 PME가 이기며, 교차점은 코드·하드웨어마다 다르다. “점근적으로 빠르다”와 “내 계산에서 빠르다”는 다른 문장이다. ↩

3. 그래서 FMM 코드를 처음 짜 본 사람이 공통으로 겪는 감정이 있다. 알고리즘 설명은 한 페이지인데 구현은 수천 줄이고, 그중 절반이 상호작용 리스트를 옳게 만드는 인덱스 지옥이다. 상용·오픈소스 라이브러리를 갖다 쓰라는 조언이 이 분야만큼 자주 나오는 곳도 드물다. ↩