다중격자법

1. 개요

다중격자법 Multigrid Method
분류	대규모 선형계 최적 해법
핵심 3요소	완화(smoothing), 제한(restriction), 연장(prolongation)
사이클	V-사이클, W-사이클, F-사이클
변종	기하학적(GMG), 대수적(AMG)
뿌리	Fedorenko 1961~64 · Brandt 1977
복잡도	O(N) — 반복수가 격자 크기에 무관
대표 구현	hypre BoomerAMG · PETSc PCMG · Trilinos MueLu

오차가 안 줄어드는 이유는, 네가 그 오차를 볼 수 있는 격자에서 안 보고 있기 때문이다.

다중격자법(Multigrid Method)은 여러 해상도의 격자를 오르내리며 오차의 모든 파장 성분을 각자 가장 잘 보이는 격자에서 제거하는, 선형계 반복 해법이다. 미지수 개수 $N$에 대해 연산량이 $O(N)$으로, 이론적으로 도달 가능한 최적 복잡도를 달성하는 몇 안 되는 방법이라 “성배(holy grail)“라 불린다.

발상의 뿌리는 이 관찰이다. 가우스-자이델 같은 단순 반복법은 오차의 고주파(짧은 파장) 성분은 몇 번 만에 싹 지우지만, 저주파(긴 파장) 성분은 지겹도록 안 줄인다. 그런데 저주파 오차는 격자를 성기게 만들면 상대적으로 고주파처럼 보인다. 그러니 격자를 갈아타면서 각 파장을 “그 파장이 고주파로 보이는 격자”에서 처리하면 되지 않겠나 — 이게 다중격자의 전부다.¹

2. 완화 — 반복법의 재발견

다중격자에서 단순 반복법은 이제 “방정식을 푸는 도구”가 아니라 오차를 매끄럽게 다듬는 도구로 재해석된다. 그래서 이 단계를 완화(smoothing) 또는 스무더(smoother)라 부른다.

가우스-자이델이나 가중 Jacobi를 두세 번만 돌리면 오차의 삐죽삐죽한 고주파 성분이 순식간에 사라지고, 밋밋하고 완만한 저주파 오차만 남는다. 여기서 반복을 더 돌려봐야 저주파는 안 줄어드니 시간 낭비.

이 “고주파를 얼마나 잘 지우는가”는 숫자로 못 박을 수 있다. 1차원 포아송 방정식 모형문제에서 가중 Jacobi의 고유값은

$$\lambda_j = 1 - 2\omega \sin^2\!\left(\frac{j\pi h}{2}\right)$$

이고, 성긴 격자가 볼 수 없는 고주파 모드($n/2 \le j \le n$)에 대한 최대 증폭률을 완화 인자(smoothing factor) $\mu$라 부른다. 이 $\mu$를 최소화하는 가중치가 정확히 $\omega = 2/3$이고, 그때

$$\mu = \max_{n/2 \le j \le n} |\lambda_j| = \frac{1}{3}$$

이 된다.² 즉 완화 한 번에 고주파 오차가 격자 크기와 무관하게 1/3로 줄어든다. 반면 가장 매끄러운 모드($j=1$)의 증폭률은 $1 - O(h^2)$라 격자를 키울수록 1에 붙는다 — 단순 반복법이 대규모 문제에서 죽는 이유이자, 그 모드를 성긴 격자로 떠넘겨야 하는 이유다. 가우스-자이델은 같은 문제에서 $\mu = 1/2$ 정도로, 가중 Jacobi보다 조금 못하지만 가중치 튜닝이 필요 없다.

그러니 완화를 더 돌리는 대신, 이 매끄러워진 오차를 성긴 격자로 넘겨버리는 게 영리하다. 완화의 목표는 “정확히 푸는 것”이 아니라 “다음 격자로 넘기기 좋게 오차를 다듬는 것”이라는 발상의 전환이 핵심이다.

3. 제한과 연장 — 격자 사이의 다리

격자를 오르내리려면 두 개의 전송 연산자가 필요하다.

• 제한(Restriction, $I_h^{2h}$): 촘촘한 격자의 잔차를 성긴 격자로 내려보낸다. 보통 주변 값을 가중 평균하는 방식. 다운샘플링이라 보면 된다.
• 연장(Prolongation, $I_{2h}^h$): 성긴 격자에서 구한 보정량을 촘촘한 격자로 올려보낸다. 보통 선형 보간. 업샘플링이다.

성긴 격자에서는 원래 방정식이 아니라 잔차 방정식 $A_{2h}\mathbf{e}_{2h} = \mathbf{r}_{2h}$를 푼다. 이게 가능한 이유는 오차와 잔차가 원래 연산자로 정확히 묶여 있기 때문이다. $\mathbf{e} = \mathbf{x} - \mathbf{x}^{(k)}$, $\mathbf{r} = \mathbf{b} - A\mathbf{x}^{(k)}$라 두면 $A\mathbf{e} = \mathbf{r}$이 근사 없이 성립한다. 해 자체가 아니라 오차(보정량)를 구해서 되돌려 더하는 것. 이 잔차 보정(residual correction) 구조 덕에 성긴 격자에서의 계산이 촘촘한 격자의 오차를 그대로 깎아낸다. 제한과 연장이 서로 전치(transpose) 관계를 이루도록 잡으면 이론적 성질이 깔끔해진다.³

4. V-사이클과 W-사이클

이 요소들을 어떤 순서로 밟느냐가 사이클이다. 가장 기본은 V-사이클: 촘촘한 격자에서 시작해 완화 → 제한을 반복하며 가장 성긴 격자까지 쭉 내려갔다가(하강), 거기서 문제를 직접 풀고, 다시 연장 → 완화를 반복하며 원래 격자로 올라온다(상승). 격자 레벨을 세로축에 그리면 궤적이 알파벳 V를 그린다고 해서 붙은 이름.

$$\text{완화} \to \text{제한} \to \cdots \to \text{직접 풀이} \to \cdots \to \text{연장} \to \text{완화}$$

V-사이클 한 번의 비용은 생각보다 싸다. 3차원에서 격자를 반으로 성기게 하면 점 개수가 $1/8$로 줄므로, 전 레벨을 합쳐도 최미세 격자 완화 비용의 $1/(1 - 2^{-d})$배 — 2차원이면 $4/3$배, 3차원이면 $8/7$배에 불과하다. “격자를 몇 단계나 내려가는데 왜 안 비싸냐”는 첫 질문의 답이 이 등비급수다.

W-사이클은 성긴 격자 쪽에서 하강·상승을 두 번씩 반복해 궤적이 W처럼 생겼다. 성긴 격자를 더 야무지게 훑어서 수렴은 좋지만 그만큼 비싸다. F-사이클은 그 중간쯤 되는 타협안. 여기에 “처음부터 가장 성긴 격자에서 시작해 점점 촘촘한 격자로 올라오며 좋은 초기값을 만들어가는” FMG(Full Multigrid)를 얹으면, 단 한 번의 순회로 이산화 오차 수준의 정확도에 도달하는 진정한 $O(N)$을 실현한다.⁴

사이클	성긴 격자 방문	수렴	비용
V-사이클	한 번	무난	저렴
W-사이클	여러 번	강력	비쌈
F-사이클	중간	중상	중간

5. 기하학적 vs 대수적 (AMG)

지금까지 설명한 건 실제 성긴 격자를 손으로 만들어 쓰는 기하학적 다중격자(Geometric Multigrid, GMG)다. 문제는 유한요소법의 복잡한 비정렬 격자나 형상이 지저분한 실무 문제에서는 “성긴 격자를 어떻게 만들지?”부터가 악몽이라는 것.

그래서 등장한 게 대수적 다중격자(Algebraic Multigrid, AMG)다. AMG는 격자 기하 정보를 아예 안 본다. 오직 행렬 $A$의 성분 크기(연결 강도)만 보고, 어떤 미지수들을 뭉쳐 성긴 레벨을 만들지 순수 대수적으로 결정한다. 고전 루게-스튀벤(Ruge-Stüben) AMG의 판정 기준은 단순하다 — 미지수 $i$가 $j$에 강하게 연결됐다는 건

$$|a_{ij}| \ge \theta \max_{k \ne i} |a_{ik}|$$

를 만족한다는 뜻이고, 임계값 $\theta$는 보통 0.25를 쓴다. 이 강한 연결 그래프에서 조립(coarsening)과 보간 가중치가 자동으로 나온다. 격자가 뭐든 행렬만 던져주면 알아서 다중격자 계층을 뽑아내니, 전산유체역학이나 구조해석의 실전 코드에서 사실상 표준으로 자리 잡았다. 대신 셋업(setup) 단계에서 계층을 구성하는 비용이 만만치 않다는 게 흠. hypre의 BoomerAMG, Trilinos의 ML 같은 라이브러리가 유명하다.

다만 AMG도 만능은 아니다. 이론적 보장은 대칭 양정치(SPD) 타원형 문제에 붙어 있고, 강한 이방성·대류 지배 문제에서는 점 단위 완화가 한 방향의 오차를 못 지워 수렴이 무너진다. 이럴 땐 선(line) 완화나 반조립(semi-coarsening)으로 완화·조립 방향을 문제에 맞춰줘야 한다. 수치확산이 큰 상류차분 대류항에 AMG가 의외로 잘 붙는 것도, 그 이산화가 행렬을 대각지배로 만들어주기 때문이다.

실무에서 다중격자는 단독 솔버로도 쓰지만, 압도적으로 많은 경우 크리로프 부분공간법의 전처리기로 투입된다. “AMG로 전처리한 CG/GMRES”는 대규모 타원형 문제에서 격자를 아무리 키워도 반복 횟수가 거의 안 늘어나는, 사실상 반칙급 조합이다.⁵

6. 관련 문서

• 크리로프 부분공간법 · 켤레기울기법 · GMRES
• 전처리기 · 반복법 · 조건수
• 유한요소법 · 유한체적법
• 격자 · 희소행렬 · 포아송 방정식
• 국소 푸리에 해석 · 영역 분할법
• 구조해석
• 전산유체역학

7. Footnotes

1. 이 통찰을 처음 체계화한 사람은 러시아의 라디 페도렌코(R. P. Fedorenko, 1961~64)이고, 1970년대에 아히 브란트(Achi Brandt)가 실용적 다중격자로 꽃피웠다. 브란트의 1977년 논문은 지금도 인용 폭탄을 맞고 있다. ↩

2. 이런 식으로 완화 인자를 손으로 계산해보는 걸 국소 푸리에 해석(local Fourier analysis, LFA)이라 한다. 브란트가 다중격자를 “설계”할 수 있게 만든 도구가 바로 이것이다. 감으로 스무더를 고르는 것과, $\mu$를 계산해놓고 고르는 것의 차이는 생각보다 크다. ↩

3. 이 조건을 갈러킨(Galerkin) 조건이라 하며, 성긴 격자 행렬을 $A_{2h} = I_h^{2h} A_h I_{2h}^h$로 정의한다. 대칭 문제에서는 여기에 $I_h^{2h} = c\,(I_{2h}^h)^{\mathsf T}$($c$는 스케일 상수)를 얹어야 $A_{2h}$가 대칭성을 물려받는다. AMG는 격자가 없으니 이 대수적 정의를 아예 성긴 레벨 행렬의 “정의” 그 자체로 삼는다. ↩

4. 여기서 재밌는 지점. FMG는 “정확히 푸는 것”이 목표가 아니다. 어차피 이산화 자체가 오차를 갖는데, 그 이산화 오차보다 더 정밀하게 선형계를 푸는 건 낭비다. FMG는 딱 이산화 오차 수준까지만 풀고 손을 턴다. 과유불급의 수치해석 버전. ↩

5. 그래서 다중격자를 처음 접한 사람들은 “$O(N)$이면 격자 100배 키워도 100배 시간이면 끝난다고?”에 감탄하다가, 셋업 비용과 스무더 튜닝의 늪에 빠져 현생을 잃는다. 성배는 아무나 드는 게 아니다. 그래도 한 번 세팅해두면 그 성능은 정말 마약 같다. ↩