중첩절단

1. 개요

중첩절단 Nested Dissection (ND)
고안	앨런 조지 (Alan George, 1973)
목적	희소 대칭 행렬 분해의 채움(fill-in)·연산량 최소화
핵심	분리자로 그래프를 쪼개고 분리자를 맨 나중에 소거, 재귀
2D 격자	채움 O(N log N), 연산 O(N3/2) — 상수배 안에서 최적
3D 격자	채움 O(N4/3), 연산 O(N2)
대표 구현	METIS NodeND, SCOTCH, ParMETIS

적을 둘로 갈라 놓고, 경계선은 마지막에 처리한다. 분할 정복을 행렬에 적용하면 이렇게 된다.

중첩절단(重疊切斷, nested dissection, ND)은 희소 대칭 행렬의 촐레스키 분해나 LU 분해에 앞서 미지수의 소거 순서를 정하는 채움 감소 순서화(fill-reducing ordering) 기법으로, 행렬의 그래프를 작은 분리자(separator)로 두 조각 내고 두 조각을 먼저, 분리자를 맨 나중에 번호 매기는 일을 재귀적으로 반복한다. 1973년 앨런 조지가 정규 유한요소법 격자에 대해 제안했고,¹ 2차원 격자에서 어떤 순서화로도 넘을 수 없는 하한에 상수배까지 붙는다는 것이 같은 해 증명됐다.

희소 직접 솔버 문서가 “순서화가 전부다”라는 큰 그림과 여러 순서화의 비교를 이미 다룬다. 이 문서는 그중 중첩절단 하나를 붙잡고 왜 그 복잡도가 나오는지, 분리자 정리가 무엇을 보장하는지, 실무 구현이 이론과 어디서 갈리는지를 판다. 짝이 되는 국소 탐욕 기법은 최소차수 순서화에 따로 있다.

2. 채움이 생기는 규칙

대칭 행렬을 그래프로 보면 미지수가 정점, 비영 비대각 원소가 간선이다. 정점 $v$ 를 소거하면 $v$ 의 이웃끼리 전부 간선이 생긴다(이웃이 클리크가 된다). 원래 없던 간선이 채움이다. 이걸 순서 전체로 정리한 것이 로즈·타잔·뤼커(1976)의 채움 경로 정리다.²

순서 $\pi$ 아래에서 $L_{ij} \neq 0$ ($i > j$) 일 필요충분조건은, 원래 그래프에 $i$ 와 $j$ 를 잇되 중간 정점이 전부 $\min(i,j)$ 보다 먼저 번호 매겨진 경로가 있는 것이다.

중첩절단의 핵심 논리는 이 정리에서 바로 나온다. 정점 집합을 $\Omega_1, \Omega_2, S$ 로 나누되 $\Omega_1$ 과 $\Omega_2$ 사이의 모든 경로가 $S$ 를 지나게 하고, $S$ 에 가장 큰 번호들을 준다고 하자. 그러면 $\Omega_1$ 의 정점 $i$ 와 $\Omega_2$ 의 정점 $j$ 를 잇는 경로는 반드시 $S$ 의 정점을 지나는데, 그 정점은 $i, j$ 둘 다보다 번호가 크다. 조건을 못 맞추므로 $\Omega_1 \times \Omega_2$ 블록에는 채움이 단 하나도 생기지 않는다. 행렬로 쓰면

$$P A P^{\mathsf T} = \begin{pmatrix} A_{11} & 0 & A_{1S} \\ 0 & A_{22} & A_{2S} \\ A_{S1} & A_{S2} & A_{SS} \end{pmatrix}$$

의 0 블록이 분해 내내 0으로 남는다는 뜻이다. 남은 일은 $A_{11}, A_{22}$ 를 독립적으로 분해하고(같은 수법을 재귀 적용), 마지막에 분리자 위의 슈어 보수 $A_{SS} - A_{S1}A_{11}^{-1}A_{1S} - A_{S2}A_{22}^{-1}A_{2S}$ 를 밀집 행렬로 분해하는 것이다. 이 구조는 영역 분할법의 비중첩 부분구조화(substructuring)와 정확히 같은 식이다 — 직접법 쪽에서 같은 산을 오른 셈이다.

3. 2D·3D 격자의 복잡도 유도

$k \times k$ 정규 격자($N = k^2$, 5점 유한차분법 스텐실)를 생각한다. 가운데 십자 모양 분리자(크기 약 $2k$)로 네 조각을 내고 각 조각에 재귀한다.

채움. 최상위 분리자의 슈어 보수는 $O(k) \times O(k)$ 밀집 블록이라 채움이 $O(k^2) = O(N)$ 이다. 한 단계 내려가면 크기 $N/4$ 짜리 문제가 넷이다. 따라서

$$F(N) = 4\,F(N/4) + c\,N \quad\Rightarrow\quad F(N) = O(N \log N).$$

연산량. 크기 $O(k)$ 인 밀집 블록의 촐레스키는 $O(k^3) = O(N^{3/2})$ 이다.

$$W(N) = 4\,W(N/4) + c\,N^{3/2} \quad\Rightarrow\quad W(N) = O(N^{3/2}).$$

마스터 정리로 보면 재귀 항($4 \cdot (N/4)^{3/2} = N^{3/2}/2$)이 매 단계 절반씩 줄어드는 기하급수라 최상위 분리자 하나가 비용을 지배한다. 이것이 중첩절단의 본질적인 성격이다 — 깊은 곳은 공짜에 가깝고, 꼭대기의 밀집 블록이 비싸다.

대조군인 자연 순서(행 우선 번호)는 대역폭이 $k$ 인 띠 행렬이 되어 채움 $O(Nk) = O(N^{3/2})$, 연산 $O(Nk^2) = O(N^2)$ 이다. $N = 10^6$ 이면 연산량 비가 대략 $\sqrt N = 1000$ 배다.

호프만·마틴·로즈(1973)는 같은 격자에서 어떤 소거 순서를 써도 연산 $\Omega(N^{3/2})$, 채움 $\Omega(N \log N)$ 아래로 내려갈 수 없음을 보였다.³ 그래서 2D 정규 격자에서 중첩절단은 상수배를 제외하면 최적이다.

3D $k \times k \times k$ 격자($N = k^3$)에서는 분리자가 면이라 크기 $k^2 = N^{2/3}$ 이다. 같은 계산을 하면 최상위 밀집 블록 분해가 $(N^{2/3})^3 = N^2$, 채움은 $(N^{2/3})^2 = N^{4/3}$ 이 된다. 3D 직접법이 메모리에서 먼저 죽는 이유가 이 지수다. 2D에서 거의 선형이던 채움이 3D에서 $N^{4/3}$ 로 뛰면서, 수백만 자유도를 넘는 3D 문제가 반복법·다중격자법 쪽으로 넘어가는 손익분기가 여기서 결정된다.

4. 분리자 정리 — 격자가 아니어도 된다

정규 격자는 분리자를 손으로 그을 수 있지만, 실제 메시 생성이 내놓는 비정렬 격자는 그렇지 않다. 립턴·타잔(1979)의 평면 분리자 정리가 이 간극을 메웠다.⁴

정점 $n$ 개인 임의의 평면 그래프는, 크기 $2\sqrt{2}\,\sqrt n$ 이하의 정점 집합을 제거해 각 조각의 정점 수가 $2n/3$ 이하가 되게 나눌 수 있고, 그런 분리자는 선형 시간에 찾을 수 있다.

립턴·로즈·타잔(1979)은 이걸 받아 일반화 중첩절단을 만들었다. $O(\sqrt n)$ 분리자를 갖는 그래프 족(평면 그래프 전부 포함)이면 채움 $O(n \log n)$, 연산 $O(n^{3/2})$ 가 성립한다. 2D 비정렬 삼각형 격자도 이 범위에 들어간다. 3D 격자는 같은 논리로 $O(n^{2/3})$ 분리자를 가지므로(잘 성형된 격자 한정) 위의 3D 지수를 따른다.

여기서 조심할 점. 정리가 보장하는 상수 $2\sqrt 2$ 와 균형비 $2/3$ 는 증명용이고, 실무 품질은 결국 분리자를 얼마나 작게 찾느냐로 정해진다. 최소 분리자 찾기 자체는 NP-난해라서, 실무는 근사·휴리스틱으로 간다.

5. 실무 구현 — 이론과 다른 세 가지

하나, 분리자는 그래프 분할기가 찾는다. METIS의 METIS_NodeND, SCOTCH, 병렬판 ParMETIS·PT-Scotch가 표준이다. 다단계 코스닝 → 초기 이분 → 정련(FM/KL) 틀은 그래프 분할의 간선 절단 문제와 같고, 마지막에 간선 분리자를 정점 분리자로 바꾸는 단계가 붙는다(절단된 간선의 한쪽 끝점들 중 최소 정점 덮개를 고른다).⁵ 피들러 벡터를 쓰는 스펙트럴 이분도 가능하지만 다단계보다 느려서 지금은 주로 비교 기준으로 남았다.

둘, 재귀를 끝까지 내려가지 않는다. 조각이 수백 정점 이하로 작아지면 거기서 최소차수 순서화 계열로 마무리한다. 작은 그래프에서는 분리자를 찾는 비용과 분리자 주변의 낭비가 이득보다 크기 때문이다. 그래서 “METIS 순서”라고 부르는 것은 사실 상위는 ND, 하위는 최소차수인 하이브리드다.

셋, 진짜 이득은 병렬성이다. 중첩절단 순서의 소거 트리(elimination tree)는 분리자가 뿌리, 두 조각이 독립된 두 부분트리인 균형 잡힌 덤불 모양이다. 서로 다른 부분트리는 데이터 의존이 없어 동시에 분해할 수 있다. 반대로 최소차수 순서는 채움이 비슷하거나 더 적어도 트리가 길고 가느다래지는 경향이 있어 병렬 확장성이 떨어진다. 분산 메모리 직접 솔버(MUMPS·SuperLU_DIST·PARDISO의 병렬 모드)가 큰 문제에서 METIS/ParMETIS 순서를 기본으로 쓰는 이유의 절반은 채움, 나머지 절반은 이 트리 모양이다.

6. 검산 — 작은 문제에서는 최소차수가 이긴다

이론 지수만 보면 중첩절단이 늘 이길 것 같지만, 실측은 상수항 때문에 다르게 나온다. 5점 라플라시안 $k \times k$ 격자와 7점 $k^3$ 격자에서 심볼릭 촐레스키로 $\operatorname{nnz}(L)$ 과 연산량 지표 $\sum_j c_j^2$ ($c_j$ 는 $L$ 의 $j$ 열 비영 개수)를 직접 셌다. ND는 가장 긴 축을 반으로 자르는 기하학적 분리자를 끝까지 재귀한 순수형, MD는 동점 시 작은 번호를 고르는 정확 최소차수, RCM은 역 커스힐-맥키다.

격자	$N$	자연 순서 nnz(L)	RCM	최소차수	중첩절단
2D 20×20	400	8,019	5,910	3,729	4,867
2D 40×40	1,600	64,039	45,020	21,504	28,227
2D 63×63	3,969	250,109	172,578	69,090	86,408
3D 10³	1,000	91,909	—	34,570	47,077
3D 15³	3,375	715,289	—	226,236	293,801

연산량 지표로 보면 3D 10³ 에서 MD 2.73e6 대 ND 3.53e6(ND가 1.29배 비쌈)이던 것이 15³ 에서 4.65e7 대 4.83e7(1.04배)로 좁혀진다. 크기가 커질수록 ND가 따라잡는 추세가 보이고, 이것이 점근 지수의 차이가 실제로 작동하기 시작하는 모습이다. 자연 순서의 연산량은 2D에서 $1.65\times10^5 \to 2.6\times10^6 \to 1.59\times10^7$ 로, $N^2$ 와의 비가 1.03 → 1.02 → 1.01 로 거의 정확히 $O(N^2)$ 를 따랐다.

교훈은 두 가지다. 수천 미지수 수준이면 AMD 하나로 충분하고 ND를 고집할 이유가 없다. 그리고 순수 기하학적 ND는 분리자 주변 낭비가 있어서, 실무 ND가 하위 단계를 최소차수로 넘기는 하이브리드 설계가 괜히 생긴 게 아니다. 이 표의 2D 20×20 행은 희소 직접 솔버 문서 시뮬레이션의 숫자와 같은 문제다(자연 순서 8,019·최소차수 3,729 일치, ND는 분리자 선택이 달라 그쪽은 5,062).⁶

7. 관련 문서

• 희소 직접 솔버 · 최소차수 순서화 · 촐레스키 분해 · LU 분해
• METIS · 그래프 분할 · 피들러 벡터 · 역 커스힐-맥키
• 슈어 보수 · 영역 분할법 · 소거 트리 · 분할 정복
• 희소행렬 · 강성행렬 · 유한요소법 · 병렬 컴퓨팅

8. Footnotes

1. 조지는 이 아이디어를 박사과정 시절부터 다듬었고, 이후 조지프 류(Joseph Liu)와 함께 쓴 교과서 Computer Solution of Large Sparse Positive Definite Systems(1981)가 한 세대의 희소 직접법 교과서가 됐다. 순서화 바닥에서 “조지”라는 이름이 나오면 거의 이 사람이다. ↩

2. 이 정리 덕분에 실제 숫자 계산 없이 그래프만 보고 $L$ 의 패턴을 미리 다 알 수 있다. 이게 “심볼릭 분해”가 수치 분해와 분리되는 근거이고, 직접 솔버가 메모리를 한 번에 정확히 잡아 둘 수 있는 이유다. ↩

3. 같은 학술지 같은 호에 조지의 상한 논문과 이 하한 논문이 나란히 실렸다. 알고리즘과 그 알고리즘이 최적이라는 증명이 같은 날 배달된, 이론가 입장에서는 꽤 깔끔한 엔딩이다. ↩

4. 평면 분리자 정리는 희소 행렬 말고도 그래프 알고리즘 전반에서 분할 정복의 주춧돌로 쓰인다. 선형대수 문제가 그래프 이론 정리를 하나 낳은 드문 경우다. ↩

5. 이 변환에서 대개 분리자가 조금 커진다. 그래서 간선 절단 품질이 좋은 분할기라도 순서화 품질은 따로 재 봐야 한다 — “분할 잘하는 도구 = 순서화 잘하는 도구”가 늘 성립하지는 않는다. ↩

6. 작은 격자에서 ND가 지는 걸 보고 “논문이 거짓말했다”고 결론 내리면 곤란하다. 점근 표기는 상수를 숨기고, 상수는 늘 작은 $N$ 에서 복수한다. ↩