전처리기

1. 개요

전처리기 Preconditioner
목적	조건수 개선 · 고유값 뭉치기 → 반복 해법 가속
대표 기법	Jacobi · SSOR · ILU/IC · SPAI · 다중격자 · 영역 분할
주된 짝	크리로프 부분공간법
성배	h-독립성 (격자를 조여도 반복 수 일정)
PCG 요구조건	M 은 SPD, 반복 중 불변
모토	같은 답, 더 빠르게

문제를 못 풀겠으면, 풀기 쉬운 문제로 바꿔서 풀어라.

전처리기(Preconditioner)는 선형계 $A\mathbf{x} = \mathbf{b}$를 반복법으로 풀 때, 해는 그대로 두면서 행렬의 스펙트럼만 확 개선해 수렴을 가속하는 보조 행렬 $M$이다. 원래 방정식 양변에 $M^{-1}$을 곱한 등가 문제를 대신 푼다.

$$M^{-1} A \mathbf{x} = M^{-1} \mathbf{b}$$

핵심은 $M$을 $A$와 최대한 비슷하게 잡되, $M^{-1}$을 곱하는 건 무진장 싸야 한다는 것. 만약 $M = A$로 잡으면 $M^{-1}A = I$가 되어 한 방에 풀리지만, 그건 원래 문제를 푸는 것과 똑같아서 반칙이다. 반대로 $M = I$면 아무것도 안 한 것. 그 사이 어딘가에서 “$A$와 닮았으면서 뒤집기 쉬운” 절묘한 타협점을 찾는 게 전처리기 설계의 전부다.¹

실무에서 전처리기의 무게는 아무리 강조해도 지나치지 않다. 대규모 해석에서 “솔버를 바꿨다”는 말은 십중팔구 “전처리기를 바꿨다”는 뜻이다. 크리로프 해법 자체(CG냐 GMRES냐)는 행렬의 대칭성이 정해 주는 거의 자동 선택이고, 실제로 계산 시간을 열 배 단위로 흔드는 손잡이는 $M$ 쪽에 달려 있다.

2. 왜 필요한가 — 조건수의 저주

크리로프 부분공간법의 수렴 속도는 조건수 $\kappa(A) = \lambda_{\max}/\lambda_{\min}$에 달려 있다. 문제는 격자를 촘촘하게 할수록 이산화 행렬의 조건수가 대책 없이 커진다는 것. 전형적인 2차 타원형 문제에서 조건수는 격자 간격 $h$에 대해 $\kappa(A) \sim O(h^{-2})$ 로 악화된다.

이건 어림이 아니라 정확히 계산할 수 있다. 단위정사각형 위 5점 차분 라플라시안(디리클레 경계, $n\times n$ 내부 격자, $h = 1/(n+1)$)의 고유값은 $\lambda_{j,k} = \frac{4}{h^2}\left[\sin^2\frac{j\pi h}{2} + \sin^2\frac{k\pi h}{2}\right]$ 이므로

$$\kappa(A) = \frac{\sin^2\frac{n\pi h}{2}}{\sin^2\frac{\pi h}{2}} = \cot^2\frac{\pi h}{2} \;\approx\; \frac{4}{\pi^2 h^2}$$

가 닫힌 형태로 나온다. 즉 격자를 두 배 촘촘하게 하면 조건수는 네 배로 뛴다. 해상도를 높일수록 정작 방정식은 더 안 풀리는 배은망덕한 상황. 순수 반복법만으로는 격자를 키우는 순간 반복 횟수가 폭발한다. 전처리기의 사명은 이 $\kappa$를 뭉개서, 가능하면 격자 크기와 무관한 상수로 만드는 것이다.²

2.1. 검산

위 식으로 실제 숫자를 찍어 보면 전처리기가 왜 선택이 아닌지 바로 보인다. 전처리 없는 켤레기울기법의 반복 수 상계는 $k \approx \tfrac12\sqrt{\kappa}\,\ln(2/\varepsilon)$ 이고, 아래는 $\varepsilon = 10^{-8}$ 기준이다.

격자	$h$	$\kappa = \cot^2(\pi h/2)$	CG 반복 상계
31×31	1/32	414	195
63×63	1/64	1,659	390
127×127	1/128	6,640	779
255×255	1/256	26,560	1,558

격자를 두 배 조일 때마다 반복 수가 정확히 두 배($\sqrt{\kappa} \propto 1/h$)로 늘어난다. 미지수는 네 배가 되는데 반복 수까지 두 배가 되니 총비용은 $O(N^{1.5})$ 로 커진다. 반면 $h$-독립 전처리기를 끼우면 마지막 열이 격자와 무관한 상수로 눕고 총비용이 $O(N)$ 에 수렴한다. 이 표의 마지막 열이 격자를 조일 때마다 두 배로 늘고 있다면, 그건 인내심이 아니라 전처리기가 부족하다는 신호다.

3. 고전 전처리기

가장 손쉬운 축이 행렬 $A$를 대각·하삼각·상삼각으로 쪼개($A = D + L + U$) 그중 일부만 역으로 쓰는 방식이다.

• Jacobi 전처리 ($M = D$): 대각 성분만 뽑아 쓴다. 대각 행렬의 역은 그냥 역수라서 이보다 쌀 수 없다. 대신 효과도 딱 그만큼 — 위 라플라시안처럼 대각이 균일한 행렬에서는 조건수가 전혀 안 줄어든다. 물성이 셀마다 크게 다른 문제(재료가 섞인 구조, 밀도비 큰 다상 유동)에서 스케일만 맞춰 줘도 값을 하는 것이 본령이다. 병렬화가 완벽하다는 게 최대 매력.
• SOR / 가우스-자이델 전처리: 하삼각까지 포함해($M = D + L$) Jacobi보다 정보를 더 쓴다. 그만큼 세지만 순차적 의존성이 생겨 병렬화가 까다롭다. 주의할 점은 $D+L$ 이 비대칭이라 PCG에 그대로 못 넣는다는 것. CG에 쓰려면 대칭화한 SSOR 형태 $M = (D+L)D^{-1}(D+U)$ 를 써야 한다.
• ILU (불완전 LU 분해): $A$를 $LU$로 분해하되, 원래 성긴 자리에 채워지는 성분(fill-in)을 적당히 버려서 $L, U$를 성기게 유지한다. 완전한 LU 분해는 정확하지만 메모리를 잡아먹으니, 정확도를 조금 포기하고 저장을 아끼는 것. ILU(0)는 $A$와 똑같은 희소 패턴만 허용하는 가장 짠돌이 버전이다. 비대칭 문제에서 OpenFOAM이나 상용 전산유체역학 코드가 즐겨 쓰는 국민 전처리기.³

대칭 양정치 행렬이라면 ILU 대신 그 사촌인 **불완전 촐레스키 분해(IC)**를 쓴다. 촐레스키 분해의 대칭성을 살려 저장과 연산을 반으로 줄이는 알뜰함으로, 마이어링크와 판 데르 포르스트(1977)가 CG와 묶어 제안한 ICCG가 그 원형이다.

여기에 함정이 하나 있다. IC/ILU 분해는 $A$ 가 M-행렬일 때만 존재가 보장된다. 그 조건을 벗어나면(비구조 격자의 뒤틀린 요소, 큰 대류항, 이방성 물성) 분해 도중 음수 피벗이 나와 그냥 실패하거나, 성공해도 $M$ 이 부정치가 되어 PCG를 터뜨린다. 표준 처방은 대각을 $\alpha$ 만큼 밀어 $A + \alpha\,\mathrm{diag}(A)$ 를 분해하는 시프트 IC이고, $\alpha$ 를 키울수록 분해는 안전해지지만 전처리 효과는 떨어진다.

4. 병렬 시대의 전처리기

ILU 계열의 근본 약점은 삼각 풀이가 본질적으로 순차적이라는 것이다. 코어 수가 늘어날수록 이 지점이 병목이 되므로, 병렬 코드는 다른 축을 쓴다.

• 블록 Jacobi / 가법 슈바르츠(ASM): 영역을 프로세서별로 쪼개 각자 자기 블록만 ILU 등으로 국소 처리한다. 통신이 거의 없어 확장성이 좋지만, 영역을 잘게 쪼갤수록 전처리 품질이 떨어져 반복 수가 늘어난다. 이웃 영역을 조금 겹쳐 주는(overlap) 것이 표준 보정이고, 더 근본적으로는 영역 분할법의 성긴 보정(coarse correction)을 얹어야 영역 수에 대한 확장성이 산다.
• 희소 근사 역행렬(SPAI): $\|AM - I\|_F$ 를 희소성 제약 아래 최소화해 $M \approx A^{-1}$ 을 명시적으로 만든다. 적용이 행렬-벡터곱 한 번이라 완전 병렬. 대신 셋업이 비싸고 패턴 선택이 까다로워 범용 기본값이 되지는 못했다.

5. 다중격자 전처리

고전 전처리기들은 조건수를 낮추긴 해도 여전히 격자 크기에 의존한다. 이 의존성 자체를 끊어버리는 물건이 다중격자법을 전처리기로 쓰는 방식이다.

다중격자는 여러 해상도의 격자를 오르내리며 오차의 모든 파장 성분을 골고루 잡아낸다. 완화(스무딩)가 고주파 오차만 빠르게 죽이고 저주파에는 무력하다는 사실을 역이용해, 저주파는 성긴 격자로 넘겨 거기서는 다시 고주파가 되게 만드는 구조다. 이걸 크리로프 해법의 $M^{-1}$ 자리에 통째로 끼워 넣으면 격자를 아무리 촘촘하게 해도 반복 횟수가 거의 일정하게 유지된다. 위 검산 표의 마지막 열이 195 → 390 → 779 로 두 배씩 뛰는 대신 10회 안팎에서 멈추는 것이다.

격자 계층을 기하학적으로 만들면 기하 다중격자(GMG), 행렬 성분만 보고 대수적으로 만들면 **대수적 다중격자(AMG)**다. AMG는 비구조 격자와 복잡한 물성에도 그냥 꽂을 수 있어 범용성이 높고, 대규모 압력 포아송 방정식의 표준 답안이 AMG-PCG인 이유가 이것이다. 물론 구현 난이도와 셋업 비용이라는 대가가 따른다. 셋업이 비싸도 같은 행렬로 여러 번 풀거나 시간전진 스텝마다 재사용하면 금방 본전을 뽑는다. 세상에 공짜 점심은 없지만 할인 쿠폰은 있다.

6. 좌·우 전처리와 트레이드오프

$M^{-1}$을 어느 쪽에 곱하느냐에 따라 좌전처리($M^{-1}A\mathbf{x} = M^{-1}\mathbf{b}$)와 우전처리($AM^{-1}\mathbf{y} = \mathbf{b}$, 이후 $\mathbf{x} = M^{-1}\mathbf{y}$)로 나뉜다. 좌전처리는 잔차가 전처리된 잔차 $M^{-1}\mathbf{r}$ 로 바뀌어 수렴 판정 기준이 달라지고, 우전처리는 원래 잔차를 그대로 보므로 GMRES에서 특히 선호된다. 사소해 보여도 수렴 로그를 해석할 때 발목을 잡는 디테일이다 — 로그의 잔차가 $10^{-10}$ 인데 참잔차가 $10^{-5}$ 인 상황의 절반은 좌전처리 탓이다.

대칭 문제에서는 제약이 하나 더 붙는다. $M^{-1}A$ 는 $M$ 과 $A$ 가 둘 다 SPD여도 일반적으로 대칭이 아니다. 그런데도 PCG가 성립하는 것은 $M$-내적 $\langle \mathbf{x},\mathbf{y}\rangle_M = \mathbf{x}^\top M \mathbf{y}$ 아래에서는 자기수반이기 때문이다. 그래서 PCG의 $M$ 은 SPD여야 하고, 반복 도중에 바뀌어도 안 된다. 내부에서 반복 해법을 근사로 돌리는 전처리기(안쪽 CG 몇 번, 수렴시키지 않은 AMG V-사이클)는 매 반복 다른 연산자가 되어 켤레성 가정을 깨뜨리므로, 유연 CG(FCG)나 FGMRES로 갈아타야 한다.

전처리기 선택은 결국 저울질이다.

관점	강한 전처리기 (예: 다중격자)	약한 전처리기 (예: Jacobi)
반복 횟수	적음	많음
반복 1회 비용	비쌈	쌈
셋업 비용	높음	거의 0
병렬화	까다로움	쉬움
격자 의존성	거의 없음	$O(h^{-1})$

“반복 횟수 × 반복당 비용 + 셋업 비용”의 총합을 최소화하는 지점이 정답인데, 이건 문제마다 다르고 하드웨어마다 다르다. 그래서 전처리기 고르기는 반쯤은 과학이고 반쯤은 손맛이다.⁴ 결국 뉴턴-랩슨법의 내부 선형 풀이든 유한요소법의 강성행렬이든, 전처리기를 뭘 끼우느냐가 해석 시간을 몇 배씩 좌우한다.

7. 고르는 순서

막막할 때 쓰는 현장의 결정 트리는 대략 이렇다.

1. 행렬이 SPD인가. 그렇다면 CG + IC(0)가 출발점이고, 타원형이면 곧장 AMG-PCG를 시도한다. 아니라면 GMRES/BiCGSTAB + ILU(0)다.
2. 반복 수가 격자와 함께 늘어나는가. 늘어난다면 전처리기가 $h$-의존이라는 뜻이니 다중격자나 영역 분할 쪽으로 올린다. 최대 반복 수를 키우는 것은 해결이 아니라 청구서 연기다.
3. 코어를 늘렸는데 안 빨라지는가. ILU의 순차 삼각 풀이가 범인일 가능성이 높다. 블록 Jacobi/ASM + 성긴 보정으로 바꾼다.
4. 분해가 아예 실패하는가. 음수 피벗이면 시프트를 넣고, 그래도 안 되면 문제 자체(격자 품질·물성 대비)를 의심한다. 전처리기는 나쁜 이산화를 구제해 주지 않는다.

8. 관련 문서

• 크리로프 부분공간법 · 켤레기울기법 · GMRES
• 다중격자법 · 영역 분할법 · 조건수
• 촐레스키 분해 · LU 분해 · 희소행렬
• 유한요소법 · 유한체적법 · 뉴턴-랩슨법
• 전산유체역학 · PETSc · OpenFOAM

9. Footnotes

1. 이 긴장 관계를 두고 흔히 “좋은 전처리기는 $A^{-1}$을 근사하되 $A^{-1}$을 계산하지 않는 것”이라 표현한다. 선문답 같지만 이게 전부다. $M$은 $A^{-1}$의 값싼 그림자여야 한다. ↩

2. 조건수를 격자와 무관한 상수로 만드는 것을 “최적 전처리(optimal preconditioning)” 혹은 “$h$-독립성”이라 부른다. 이 성배를 실제로 달성하는 대표 주자가 다중격자다. 나머지 전처리기들은 대부분 격자 앞에서 조금씩 무릎을 꿇는다. ↩

3. ILU에는 fill-in을 얼마나 허용하느냐로 ILU(0), ILU(1), ILUT 등 레벨이 있다. 레벨을 올리면 세지지만 무거워진다. ILU($p$)는 채움의 “레벨”이라는 조합적 기준으로 자르고, ILUT는 값의 크기가 문턱 아래면 버리는 수치적 기준으로 자른다. “일단 ILU(0)로 돌려보고 안 되면 레벨 올린다”가 현장의 국룰. 그리고 대부분 ILU(0)에서 이미 답이 나온다. ↩

4. 그래서 PETSc, hypre, AMGCL 같은 라이브러리들이 온갖 전처리기를 뷔페처럼 깔아놓고 “골라 쓰세요” 한다. 초심자는 이 메뉴판 앞에서 길을 잃고, 고수는 문제 보고 세 개쯤 후보를 추린 뒤 벤치마크를 돌린다. 감으로 찍는 게 아니라 재보는 게 정석이다. ↩