다중격자법

수치해석 시뮬레이션 마지막 수정: 2026-07-05 04:31:07

다중격자법 Multigrid Method
분류	대규모 선형계 최적 해법
핵심 3요소	완화(smoothing), 제한(restriction), 연장(prolongation)
사이클	V-사이클, W-사이클, F-사이클
변종	기하학적(GMG), 대수적(AMG)

1. 개요[편집]

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

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

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

2. 완화 — 반복법의 재발견[편집]

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

가우스-자이델이나 가중 Jacobi를 두세 번만 돌리면 오차의 삐죽삐죽한 고주파 성분이 순식간에 사라지고, 밋밋하고 완만한 저주파 오차만 남는다. 여기서 반복을 더 돌려봐야 저주파는 안 줄어드니 시간 낭비. 대신 이 매끄러워진 오차를 성긴 격자로 넘겨버리는 게 영리하다. 완화의 목표는 “정확히 푸는 것”이 아니라 “다음 격자로 넘기기 좋게 오차를 다듬는 것”이라는 발상의 전환이 핵심이다.

3. 제한과 연장 — 격자 사이의 다리[편집]

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

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

성긴 격자에서는 원래 방정식이 아니라 잔차 방정식 $A_{2h}\mathbf{e}_{2h} = \mathbf{r}_{2h}$ 를 푼다. 해 자체가 아니라 오차(보정량)를 구해서 되돌려 더하는 것. 이 잔차 보정(residual correction) 구조 덕에 성긴 격자에서의 계산이 촘촘한 격자의 오차를 그대로 깎아낸다. 제한과 연장이 서로 전치(transpose) 관계를 이루도록 잡으면 이론적 성질이 깔끔해진다.²

4. V-사이클과 W-사이클[편집]

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

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

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

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

5. 기하학적 vs 대수적 (AMG)[편집]

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

그래서 등장한 게 대수적 다중격자(Algebraic Multigrid, AMG)다. AMG는 격자 기하 정보를 아예 안 본다. 오직 행렬 $A$ 의 성분 크기(연결 강도)만 보고, 어떤 미지수들을 뭉쳐 성긴 레벨을 만들지 순수 대수적으로 결정한다. 격자가 뭐든 행렬만 던져주면 알아서 다중격자 계층을 뽑아내니, 전산유체역학이나 구조해석의 실전 코드에서 사실상 표준으로 자리 잡았다. 대신 셋업(setup) 단계에서 계층을 구성하는 비용이 만만치 않다는 게 흠. hypre의 BoomerAMG, Trilinos의 ML 같은 라이브러리가 유명하다.

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

6. 관련 문서[편집]

이 통찰을 처음 체계화한 사람은 러시아의 라디 페도렌코(R. P. Fedorenko, 1961~64)이고, 1970년대에 아히 브란트(Achi Brandt)가 실용적 다중격자로 꽃피웠다. 브란트의 1977년 논문은 지금도 인용 폭탄을 맞고 있다. ↩
이 조건을 갈러킨(Galerkin) 조건이라 하며, 성긴 격자 행렬을 $A_{2h} = I_h^{2h} A_h I_{2h}^h$ 로 정의한다. AMG는 격자가 없으니 이 대수적 정의를 아예 성긴 레벨 행렬의 “정의” 그 자체로 삼는다. ↩
여기서 재밌는 지점. FMG는 “정확히 푸는 것”이 목표가 아니다. 어차피 이산화 자체가 오차를 갖는데, 그 이산화 오차보다 더 정밀하게 선형계를 푸는 건 낭비다. FMG는 딱 이산화 오차 수준까지만 풀고 손을 턴다. 과유불급의 수치해석 버전. ↩
그래서 다중격자를 처음 접한 사람들은 “ $O(N)$ 이면 격자 100배 키워도 100배 시간이면 끝난다고?”에 감탄하다가, 셋업 비용과 스무더 튜닝의 늪에 빠져 현생을 잃는다. 성배는 아무나 드는 게 아니다. 그래도 한 번 세팅해두면 그 성능은 정말 마약 같다. ↩