전처리기

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

전처리기 Preconditioner
목적	조건수 개선 → 반복 해법 가속
대표 기법	Jacobi, ILU, SOR, 다중격자 전처리
주된 짝	크리로프 부분공간법
모토	같은 답, 더 빠르게

1. 개요[편집]

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

전처리기(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$ 와 닮았으면서 뒤집기 쉬운” 절묘한 타협점을 찾는 게 전처리기 설계의 전부다.¹

2. 왜 필요한가 — 조건수의 저주[편집]

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

\kappa(A) \sim O(h^{-2})

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

3. 고전 전처리기[편집]

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

Jacobi 전처리 ( $M = D$ ): 대각 성분만 뽑아 쓴다. 대각 행렬의 역은 그냥 역수라서 이보다 쌀 수 없다. 대신 효과도 딱 그만큼. 대각 지배(diagonally dominant)가 강한 행렬에서나 쓸만하다. 병렬화가 완벽하다는 게 최대 매력.
SOR / 가우스-자이델 전처리: 하삼각까지 포함해( $M = D + L$ ) Jacobi보다 정보를 더 쓴다. 그만큼 세지만 순차적 의존성이 생겨 병렬화가 까다롭다.
ILU (불완전 LU 분해): $A$ 를 $LU$ 로 분해하되, 원래 성긴 자리에 채워지는 성분(fill-in)을 적당히 버려서 $L, U$ 를 성기게 유지한다. 완전한 LU 분해는 정확하지만 메모리를 잡아먹으니, 정확도를 조금 포기하고 저장을 아끼는 것. ILU(0)는 $A$ 와 똑같은 희소 패턴만 허용하는 가장 짠돌이 버전이다. 비대칭 문제에서 OpenFOAM이나 상용 전산유체역학 코드가 즐겨 쓰는 국민 전처리기.³

대칭 양정치 행렬이라면 ILU 대신 그 사촌인 불완전 촐레스키 분해(IC)를 쓴다. 대칭성을 살려 저장과 연산을 반으로 줄이는 알뜰함.

4. 다중격자 전처리[편집]

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

다중격자는 여러 해상도의 격자를 오르내리며 오차의 모든 파장 성분을 골고루 잡아내는데, 이걸 크리로프 해법의 $M^{-1}$ 자리에 통째로 끼워 넣으면 마법 같은 일이 벌어진다. 격자를 아무리 촘촘하게 해도 반복 횟수가 거의 일정하게 유지되는 것. 이론적으로 최적( $O(N)$ )에 가까운 성능이다. 대규모 타원형/포아송 문제에서 “다중격자로 전처리한 CG(또는 GMRES)“는 현존 최강 조합으로 통한다. 물론 구현 난이도와 셋업 비용이라는 대가가 따른다. 세상에 공짜 점심은 없다.

5. 좌·우 전처리와 트레이드오프[편집]

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

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

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

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

6. 관련 문서[편집]

이 긴장 관계를 두고 흔히 “좋은 전처리기는 $A^{-1}$ 을 근사하되 $A^{-1}$ 을 계산하지 않는 것”이라 표현한다. 선문답 같지만 이게 전부다. $M$ 은 $A^{-1}$ 의 값싼 그림자여야 한다. ↩
조건수를 격자와 무관한 상수로 만드는 것을 “최적 전처리(optimal preconditioning)” 혹은 “ $h$ -독립성”이라 부른다. 이 성배를 실제로 달성하는 대표 주자가 다중격자다. 나머지 전처리기들은 대부분 격자 앞에서 조금씩 무릎을 꿇는다. ↩
ILU에는 fill-in을 얼마나 허용하느냐로 ILU(0), ILU(1), ILUT 등 레벨이 있다. 레벨을 올리면 세지지만 무거워진다. “일단 ILU(0)로 돌려보고 안 되면 레벨 올린다”가 현장의 국룰. 그리고 대부분 ILU(0)에서 이미 답이 나온다. ↩
그래서 PETSc, hypre, AMGCL 같은 라이브러리들이 온갖 전처리기를 뷔페처럼 깔아놓고 “골라 쓰세요” 한다. 초심자는 이 메뉴판 앞에서 길을 잃고, 고수는 문제 보고 세 개쯤 후보를 추린 뒤 벤치마크를 돌린다. 감으로 찍는 게 아니라 재보는 게 정석이다. ↩