영역 분할법

수치해석 시뮬레이션 마지막 수정: 2026-08-06 05:29:41

1. 개요[편집]

영역 분할법 Domain Decomposition Method (DDM)
기원	H. A. Schwarz 교대법 (1870)
두 갈래	중첩형(슈바르츠) · 비중첩형(슈어 여인자 / FETI · BDDC)
확장성 조건	조대 공간(coarse space) 필수 — 없으면 반복수가 부분영역 수에 따라 증가
조건수	2단계 가법 슈바르츠 $\kappa \lesssim C(1+H/\delta)$, BDDC/FETI-DP $C(1+\log(H/h))^2$
구현	PETSc `PCASM`·`PCGASM`·`PCBDDC`, hypre

분할 정복은 쉽다. 어려운 건 정복한 조각들이 서로 말을 맞추게 하는 것이다.

영역 분할법(domain decomposition method)은 큰 편미분방정식 문제의 계산 영역을 여러 부분영역으로 쪼개 각각을 (가능하면 병렬로) 풀고, 부분영역 경계에서 해가 서로 이어지도록 반복적으로 맞춰 가는 방법론이다. 오늘날 대형 유한요소법·유한체적법 해석의 전처리기는 사실상 전부 이 계열이며, 병렬 컴퓨팅 관점에서는 “데이터도 나누고 알고리즘도 나누는” 유일하게 자연스러운 방식이다.

뿌리는 1870년 헤르만 슈바르츠까지 올라간다. 원과 직사각형을 겹쳐 붙인 영역에서 라플라스 방정식의 해가 존재함을 보이려고, 한쪽 영역을 풀어 얻은 값을 다른 쪽의 경계조건으로 넘기는 절차를 반복해 수렴을 증명했다.¹ 컴퓨터가 없던 시절의 존재성 증명 도구가 100년 뒤 병렬 솔버의 뼈대가 되었다.

2. 중첩형 — 슈바르츠 교대법[편집]

영역 $\Omega$ 를 서로 겹치는 $\Omega_1, \dots, \Omega_N$ 으로 덮고, 겹침 폭을 $\delta$ 라 하자. 슈바르츠 교대법은 각 $\Omega_i$ 에서 국소 문제를 풀되 인접 부분영역의 현재 해를 디리클레 경계값으로 받아 쓴다. 갱신 순서에 따라 두 판본이 갈린다.

승법 슈바르츠(multiplicative): 순차적으로 갱신하며 방금 계산한 값을 즉시 반영한다. 가우스 소거법 계열의 가우스-자이델과 같은 구조라 수렴은 빠르지만 본질적으로 직렬이다. 색칠(coloring)로 부분 병렬화한다.
가법 슈바르츠(additive, ASM): 모든 부분영역을 동시에 풀고 보정을 더한다. 자코비형이라 수렴은 느리지만 완벽히 병렬이고, 무엇보다 대칭 선형 연산자이므로 크리로프 부분공간법의 전처리기로 쓸 수 있다.

겹침 폭 $\delta$ 가 성능을 지배한다. 두 부분영역만 있는 고전적 해석에서 슈바르츠 교대법의 수렴률은 겹침이 넓을수록 기하급수적으로 좋아지는 반면, $\delta \to 0$ 이면 수렴이 멈춘다. 반대로 겹침을 넓히면 국소 문제가 커지고 통신량도 늘어난다. 실무에서는 격자 몇 층(요소 1~2겹) 정도의 겹침이 국룰인데, 이게 이론이 요구하는 $\delta \sim H$ 와는 한참 거리가 있어서 조대 공간이 더더욱 필수가 된다.

전처리기로서의 형태가 유명한 그 식이다. $R_i$ 를 $\Omega_i$ 자유도로의 제한 연산자, $A_i = R_i A R_i^{T}$ 를 국소 강성행렬이라 하면

M_{\mathrm{ASM}}^{-1} = \sum_{i=1}^{N} R_i^{T} A_i^{-1} R_i

이다. 반복법 관점에서 이것은 “겹치는 블록 자코비”에 지나지 않는다. 실무 기본값은 오히려 제한 가법 슈바르츠(RAS)로, 보정을 되돌릴 때 겹침 부분을 중복 계산하지 않는 $\tilde{R}_i^{T}$ 를 쓴다. 이론적 대칭성을 잃는 대신 통신량이 줄고 반복수도 대개 더 적다는, 1999년 카이-사르키스의 다소 얄미운 발견이다.²

3. 비중첩형 — 슈어 여인자, FETI, BDDC[편집]

겹치지 않게 자르면 자유도가 부분영역 내부 $I$ 와 계면 $\Gamma$ 로 깔끔히 나뉜다. 내부 자유도를 소거하면 계면만의 문제가 남는다.

S = A_{\Gamma\Gamma} - \sum_i A_{\Gamma i} A_{ii}^{-1} A_{i\Gamma}

이 $S$ 가 슈어 여인자이며, 미지수 개수가 원래보다 훨씬 적고 조건수도 $O(h^{-1})$ 로 원래 문제의 $O(h^{-2})$ 보다 낫다. $S$ 를 명시적으로 만들 필요는 없다 — 벡터 하나 곱하는 데 부분영역당 국소 디리클레 문제 한 번이면 되므로 행렬-프리로 CG를 돌린다. 이 접근이 구조해석에서 오래 쓰인 부분구조법(substructuring)과 같은 뿌리다.

여기에 붙는 전처리기가 노이만-노이만 계열이고, 그 현대적 완성형이 두 가지다.

FETI(1991, 파라·루). 부분영역 사이의 연속성을 라그랑주 승수법으로 부과하고, 원래 변수를 소거해 얻은 쌍대 문제를 승수에 대해 푼다. 부분영역이 떠 있으면(부유 부분영역) 국소 강성행렬이 특이해지는데, 그 영강체 모드들이 자연스럽게 조대 공간을 만들어 준다. 개량형 FETI-DP(2001)는 코너 자유도를 전역적으로 공유해 특이성을 없앤다.
BDDC(2003, 도어만). 국소 노이만 문제 + 코너·에지 평균 같은 원시(primal) 구속으로 만든 조대 문제를 결합한다. FETI-DP와 BDDC의 전처리된 연산자는 0과 1을 제외한 고유값이 완전히 일치한다는 것이 만델·도어만·테자우르(2005)의 결과로, 두 계열이 사실상 같은 방법의 원시/쌍대 표현임이 밝혀졌다.

4. 조대 공간 없이는 확장성도 없다[편집]

이 분야의 핵심 정리는 한 문장으로 요약된다. 조대 공간이 없으면 반복수가 부분영역 개수에 따라 늘어난다.

이유는 정보 전파 속도다. 타원형 방정식의 해는 전역적으로 결합되어 있어 한쪽 끝의 경계값이 반대쪽 해에 즉시 영향을 준다. 그런데 1단계 슈바르츠 반복은 매 스텝 이웃 부분영역과만 정보를 주고받는다. 부분영역 크기가 $H$ 인 영역을 가로지르려면 최소 $O(1/H)$ 번의 반복이 필요하고, 실제로 1단계 가법 슈바르츠의 조건수 추정은 $\kappa \lesssim C/(H\delta)$ 로 $H \to 0$ 에서 발산한다. 코어를 열 배 늘려 부분영역을 열 배 잘게 쪼개면 반복수가 늘어 병렬 이득이 상쇄되는, 전형적인 약확장성(weak scaling) 붕괴다.

해법은 부분영역당 자유도 하나 정도의 아주 성긴 조대 문제를 하나 더 푸는 것이다. 2단계 가법 슈바르츠의 조건수는

\kappa(M^{-1}A) \le C\left(1 + \frac{H}{\delta}\right)

로 격자 크기 $h$ 와 부분영역 개수에 독립이 된다. 겹침 폭이 부분영역 크기에 비례( $\delta \sim H$ )하면 상수로 유지된다. 비중첩형에서는 BDDC와 FETI-DP가 $\kappa \le C(1+\log(H/h))^2$ 로, 로그 제곱이라 사실상 상수다.

조대 보정이 본질이라는 점에서 이 방법론은 다중격자법과 같은 이야기를 한다. 실제로 2단계 슈바르츠는 “겹치는 블록 완화 + 매우 공격적인 조대화를 가진 2격자 방법”으로 읽을 수 있다. 다중격자가 격자 계층을 재귀적으로 쌓는 데 비해 영역 분할은 조대화를 한두 단계로 끊고 국소 solver를 강하게 쓰는 쪽으로 무게를 옮겼을 뿐이다. 계수가 심하게 불연속인 문제에서는 국소 고유값 문제를 풀어 조대 공간을 자동 생성하는 스펙트럴 조대 공간(GenEO 등)이 쓰이는데, 여기서 고유값 문제 솔버가 전처리기 내부로 들어온다.³

5. 실무에서[편집]

소프트웨어. PETSc의 PCASM(중첩 ASM), PCGASM(부분영역이 프로세서 경계를 넘는 일반화 판), PCBDDC가 대표적이고, hypre·Trilinos도 동등한 기능을 제공한다. 대부분 국소 문제를 정확히 풀지 않고 불완전 LU 정도로 근사한다 — 어차피 전처리기다.
분할 품질. 부분영역은 메시 생성 후 그래프 분할기(METIS/ParMETIS)로 나눈다. 목표는 두 가지, 부하 균형(요소 수를 고르게)과 계면 최소화(통신량을 줄이게)이며 이건 그 자체로 NP-난해한 조합 최적화 문제다. 길쭉하거나 연결이 끊긴 부분영역이 나오면 조건수 상수가 조용히 나빠진다.
어려운 문제. 헬름홀츠 방정식처럼 부호가 불명확한 문제에서는 고전 슈바르츠가 수렴하지 않는다. 계면 전달조건을 디리클레 대신 로빈형·흡수형으로 바꾸는 최적화 슈바르츠 방법이나 소스 전파를 흉내 내는 스위핑 전처리기가 필요하다.
비선형과 시간. 뉴턴 반복 안쪽의 선형계만 분할하는 것이 표준이지만, 국소 비선형성이 심하면 뉴턴 자체가 전역적으로 느려진다. 이때 각 부분영역에서 비선형 문제를 먼저 풀어 전처리하는 ASPIN(가법 슈바르츠 전처리 부정확 뉴턴) 계열이 쓰인다. 시간 방향으로 자르는 판본도 있어서, 부분영역마다 시간 구간 전체를 풀고 계면에서 시간 이력을 주고받는 슈바르츠 파형 완화나 시간 병렬 기법(파라리얼)이 같은 계보에 속한다.
혼동 주의. 유체-구조 연성의 분할(partitioned) 접근과는 다른 이야기다. 그쪽은 서로 다른 물리를 다른 솔버에 맡기고 계면에서 힘·변위를 주고받는 것이고, 영역 분할법은 같은 연산자를 기하학적으로 자른 것이다. 반복 구조가 닮아 보이지만 수렴 이론이 공유되지 않는다.⁴

6. 관련 문서[편집]

그 유명한 “슈바르츠 교대법”. 참고로 이 슈바르츠는 코시-슈바르츠 부등식과 슈바르츠 보조정리의 그 슈바르츠이고, 슈어 분해의 슈어와는 다른 사람이다. 독일어권 수학자 이름이 겹칠 때 성이 아니라 세기를 먼저 보는 습관을 들이면 편하다. ↩
대칭성을 버렸는데 더 잘 되는 사례라 처음 나왔을 때 “이게 왜 되냐”는 반응이 많았다. 지금도 PETSc의 PCASM 기본 타입은 RESTRICT이고, 정직하게 대칭인 BASIC을 굳이 켜는 사람은 CG의 이론적 보증이 꼭 필요할 때뿐이다. ↩
여담으로 영역 분할 커뮤니티는 1987년부터 매년 국제 학회(DD conference)를 열고 있는데, 회차 번호가 그대로 방법 이름에 붙는 문화 덕분에 “DD27에서 발표된 조대 공간”처럼 연도 대신 회차로 인용하는 경우가 많다. ↩
물론 둘을 겹쳐 쓰는 경우도 흔하다. FSI 해석에서 유체 도메인 내부를 다시 수백 개 부분영역으로 자르는 식. 이때 바깥 루프는 물리 분할, 안쪽 루프는 기하 분할이며, 수렴이 안 될 때 어느 쪽 루프가 범인인지 가려내는 것이 현생이다. ↩