불완전 촐레스키

1. 개요

불완전 촐레스키 Incomplete Cholesky (IC)
대상	대칭 양정치 희소행렬 A
만드는 것	A ≈ LLT, L 은 정해진 희소 패턴 안에서만
쓰임	켤레기울기법의 전처리기 (ICCG)
대표 변형	IC(0), IC(k), 문턱 IC(ICT), 수정 IC(MIC)
원형	마이어링크·반 데르 포르스트, 1977
약점	M-행렬이 아니면 분해 실패 가능, 삼각 풀이의 병렬화가 어려움

촐레스키 분해를 끝까지 하면 채움(fill-in)이 메모리를 잡아먹는다. 그럼 채움을 그냥 버리자. 틀린 분해지만, 틀린 만큼만 반복이 고쳐 주면 된다.

불완전 촐레스키 분해(incomplete Cholesky factorization, IC)는 대칭 양정치 희소행렬 $A$ 에 대해 촐레스키 분해를 수행하되, 미리 정한 희소 패턴 밖에 생기는 채움 원소를 버려서 $A \approx LL^{\mathsf T}$ 인 성긴 하삼각 $L$ 을 얻는 근사 분해다. 그 자체로는 연립방정식을 풀지 못하지만, $M = LL^{\mathsf T}$ 를 켤레기울기법의 전처리기로 쓰면 반복 수가 크게 준다. 이 조합이 ICCG 이고, 마이어링크와 반 데르 포르스트가 1977년 대칭 M-행렬에 대해 분해가 항상 존재함을 보이며 정립했다.

전처리기 문서가 IC 의 위치(ILU 의 대칭 사촌), 존재 조건(M-행렬), 시프트 처방까지 요약했다. 이 문서는 그 안쪽을 연다 — 무엇을 버리는지, 5점 라플라시안에서 분해가 벡터 하나로 줄어드는 이유, 버린 것을 대각에 되돌려 놓는 수정 IC 가 반복 수의 차수를 바꾸는 이유, 순서화가 성능을 바꾸는 방식, 그리고 GPU 시대에 IC 가 겪는 고생이다.

2. 무엇을 버리나

가우스 소거로 $k$ 번째 열을 제거하면 $L$ 의 $k$ 열이 0 이 아닌 행들 $i, j$ 사이에 $a_{ij} \leftarrow a_{ij} - l_{ik}l_{jk}$ 갱신이 일어난다. 원래 $a_{ij} = 0$ 이던 자리가 이렇게 채워지는 것이 채움이다. 완전 촐레스키는 이걸 다 받아들이고, IC 는 허용 패턴 $\mathcal S$ 밖이면 버린다. 패턴을 정하는 방식에 따라:

• IC(0): $\mathcal S$ = $A$ 의 하삼각 비영 패턴. 채움을 하나도 허용하지 않는다. $L$ 의 메모리가 $A$ 의 절반과 같다.
• IC($k$): 채움에 “레벨”을 매겨, 원래 비영은 레벨 0, 레벨 $p$·$q$ 원소로부터 생긴 채움은 레벨 $p+q+1$ 로 두고 $k$ 이하만 남긴다. 격자 위에서는 “몇 다리 건넌 이웃까지 허용하나”와 비슷하다.
• ICT / 문턱 IC: 위치가 아니라 크기로 자른다. 상대 크기가 문턱 $\tau$ 보다 작은 원소를 버리고, 행마다 최대 $p$ 개만 남기는 상한을 둔다. 비구조 격자처럼 위치 기반 레벨이 의미 없는 문제에서 강하다.

버린 원소를 모은 행렬을 $R$ 이라 하면 $A = LL^{\mathsf T} + R$ 이다. 전처리된 행렬 $L^{-1}AL^{-\mathsf T} = I + L^{-1}RL^{-\mathsf T}$ 의 고유값이 1 근처에 얼마나 모이느냐가 IC 의 성능 전부다.

3. 5점 라플라시안 — 분해가 벡터 하나로 줄어든다

2차원 포아송 방정식의 5점 스텐실, 자연 순서(행 우선)에서 IC(0) 를 써 보면 구조가 아름답다. 비영은 대각 4 와 서쪽·남쪽 이웃 $-1$ 뿐이고, 서쪽 이웃을 제거할 때 생기는 채움은 “서쪽의 북쪽” 같은 대각선 자리라 전부 버려진다. 그 결과 $L$ 의 비대각 원소는 $A$ 의 것을 그대로 쓰고, 새로 계산되는 건 대각 피벗 $d_{i,j}$ 뿐이다.

$$M = (\tilde D + L_A)\,\tilde D^{-1}(\tilde D + L_A^{\mathsf T}), \qquad d_{i,j} = 4 - \frac{1}{d_{i-1,j}} - \frac{1}{d_{i,j-1}}$$

여기서 $L_A$ 는 $A$ 의 순수 하삼각, $\tilde D = \mathrm{diag}(d_{i,j})$ 다. 저장할 것은 벡터 $d$ 하나고, 전처리 적용은 전진·후진 대입 한 번씩이다.¹ 격자 안쪽에서 $d$ 는 $d = 4 - 2/d$ 의 해 $2 + \sqrt2 \approx 3.414$ 로 수렴한다. 실측에서도 $127\times127$ 격자의 최소 피벗이 정확히 3.4142 였다 — 피벗이 0 근처로 가지 않으니 M-행렬에서 IC(0) 가 안전하다는 정리의 구체적 그림이다.

4. 수정 IC — 버린 것을 대각에 돌려준다

IC(0) 는 상수 벡터 같은 매끄러운 모드를 잘 못 잡는다. 그 모드에서 $A$ 는 작은 고유값(≈$h^2$)을 갖는데, 버린 채움 $R$ 이 그 모드에 대해 상대적으로 큰 오차를 만든다. 결과적으로 조건수가 여전히 $O(h^{-2})$ 이고, CG 반복 수는 상수배만 줄 뿐 $O(h^{-1})$ 로 자란다.

수정 불완전 촐레스키(MIC, 구스타프손 1978)는 버리는 원소를 그냥 버리지 않고 같은 행의 대각에 더한다. 그러면 $M$ 과 $A$ 의 행 합이 같아져서 상수 벡터에 대해 $M\mathbf 1 = A\mathbf 1$ 이 성립한다. 5점 라플라시안에서는 피벗 점화식이

$$d_{i,j} = 4 - \frac{2}{d_{i-1,j}} - \frac{2}{d_{i,j-1}}$$

가 되고(안쪽 점 기준), 극한 피벗은 $d = 4 - 4/d$ 의 중근 $d = 2$ 다. 구스타프손은 대각에 $O(h^2)$ 크기의 작은 섭동을 더한 MIC 가 조건수를 $O(h^{-1})$ 로 낮춰 CG 반복 수를 $O(h^{-1/2})$ 로 바꿈을 보였다. 상수배가 아니라 차수가 바뀐다.

4.1. 검산 — 격자를 조일 때 반복 수

정사각형 위 $-\Delta u = 1$, 5점 스텐실, 자연 순서, $\mathbf x_0 = 0$, 상대잔차 $10^{-8}$ 까지의 CG 반복 수:

내부 격자	미지수	CG	IC(0)-CG	MIC(0)-CG
$31\times31$	961	58	29	24
$63\times63$	3969	118	51	36
$127\times127$	16129	237	99	54
격자 2배당 증가		×2.0	×1.9	×1.5

IC(0) 는 CG 의 절반 남짓이지만 증가율은 똑같이 약 2 배($O(h^{-1})$)다. MIC(0) 의 증가율은 약 1.5 배로 $\sqrt2 \approx 1.41$ 쪽에 가깝다 — $O(h^{-1/2})$ 이론이 숫자로 보인다(여기서는 $O(h^2)$ 섭동 없이 순수 행 합 보정만 했다. MIC 피벗은 $127\times127$ 에서 최소 2.008 로, 극한값 2 에 다가가면서 $M$ 이 거의 특이해지는 것이 섭동을 넣는 이유다).

물론 이 차수 이득도 다중격자법의 “격자 무관 반복 수” 앞에서는 초라하다. 그래도 MIC 는 구현이 몇 줄이고 거의 모든 SPD 문제에 그대로 꽂힌다. 이게 수십 년째 살아남은 이유다.

5. 순서화가 성능을 바꾼다

완전 촐레스키에서 순서화(역 커스힐-맥키, 최소차수 순서화, 중첩절단)는 채움의 양을 바꾼다. IC 에서는 채움을 어차피 버리므로, 순서화가 바꾸는 것은 버려지는 정보의 양이다.

• 자연 순서는 각 점이 이미 처리된 이웃(서·남)을 둘 갖고, 그 정보가 분해를 따라 격자 전체로 전파된다.
• 적-흑 순서(체커보드)는 빨간 점끼리 서로 이웃이 아니라 빨간 블록이 대각 행렬이 된다. 병렬화에는 이상적이지만 IC(0) 의 정보 전파가 한 다리에서 끊긴다. $63\times63$ 실측에서 IC(0)-CG 가 자연 순서 51 회 → 적-흑 순서 59 회로 늘었다. 더 큰 격자와 더 많은 채움을 허용할수록 격차가 커진다는 것이 더프·뫼랑(1989)의 고전적 관찰이다.
• 비구조 격자에서는 RCM 순서가 IC 에도 대체로 좋다. 띠를 좁히면 버려지는 원소가 “가까운 이웃”이 되어 덜 아프기 때문이다.

6. 안 될 때 — 실패와 병렬화

분해 실패. M-행렬이 아니면 피벗이 음수가 될 수 있다는 것, 그리고 대각을 키우는 시프트 IC(만토이펠 1980)가 표준 처방이라는 것은 전처리기에 있다. 그 밖의 역사적 처방 둘:

• 음수 피벗을 양수로 바꿔치기(커쇼 1978) — 레이저 핵융합 코드에서 실제로 쓰인 실용적 땜질이다.² 정당화는 약하지만 잘 돌았다.
• 대각 보상(아지즈·제닝스 1984) — 버리는 원소 $r_{ij}$ 마다 $|r_{ij}|$ 를 두 대각($i$, $j$)에 더한다. 그러면 $R$ 이 음반정치가 되어 $A$ 가 SPD 이기만 하면 분해가 반드시 성공한다. 구조해석의 비 M-행렬 강성행렬에서 쓰인다.

병렬화. 전처리 적용의 핵심인 전진·후진 대입은 본질적으로 순차다 — $i$ 번째 값은 앞의 값들이 있어야 나온다. 처방은:

• 레벨 스케줄링: 의존 그래프에서 서로 독립인 행들을 묶어 한 레벨씩 병렬로 푼다. 5점 자연 순서라면 반대각선(웨이브프런트)이 한 레벨이다.
• 다색 순서화: 그래프 색칠로 같은 색끼리 완전 병렬. 대신 위의 적-흑 손해를 감수한다.
• 반복 근사: 삼각 풀이 자체를 야코비 몇 스텝으로 대충 푸는 방식(초우·파텔 2015 의 반복 ILU 와 함께)이 GPU 컴퓨팅에서 쓰인다. 수학적으로는 전처리기가 매번 조금씩 달라지지만, 병렬성이 그걸 이긴다.

GPU 수천 코어 위에서는 “반복 수는 많지만 완전 병렬인” 야코비·다항식 전처리나 대수적 다중격자가 IC 를 이기는 일이 흔하다. CPU 몇 코어의 중간 규모 SPD 문제에서는 여전히 IC 가 가성비 왕이다.³

7. 관련 문서

• 전처리기 · 켤레기울기법 · 촐레스키 분해 · LDL 분해
• 크리로프 부분공간법 · BiCGSTAB · 다중격자법 · 대수적 다중격자
• 희소행렬 · 역 커스힐-맥키 · 최소차수 순서화 · 중첩절단
• 포아송 방정식 · 그래프 색칠 · M-행렬

8. Footnotes

1. 이 “비대각은 원래 행렬 것을 그대로 쓰고 대각만 새로 저장” 형태는 아이젠슈타트(1981)의 트릭과 결합하면 전처리 CG 한 반복의 비용을 전처리 없는 CG 와 거의 같게 만들 수 있다. 공짜 점심에 가장 가까운 사례. ↩

2. 수학적으로는 무슨 짓인가 싶지만, 전처리기는 틀려도 되는 물건이라 통한다. 전처리기가 틀리면 반복 수가 늘 뿐 답이 틀리지는 않는다 — 이것이 이 바닥 모든 땜질의 면허증이다. ↩

3. 그래서 “IC 는 낡았다”는 말은 GPU 클러스터에서만 맞고, 연구실 워크스테이션에서 구조해석 모델을 돌리는 대학원생에게는 여전히 현생의 주력이다. ↩