GMRES

1. 개요[편집]

GMRES Generalized Minimal RESidual
제안	Saad & Schultz, 1986
대상	일반 비대칭 정칙 $A$, $Ax=b$
최소화 대상	잔차 2-노름 (아핀 크릴로프 공간 위)
도구	아놀디 알고리즘 + 기븐스 회전
비용	저장 $O(mn)$, 직교화 $O(m^2 n)$
실전형	재시작 GMRES($m$) + 전처리기

잔차는 절대 늘지 않는다. 다만 안 줄어들 뿐이다.

GMRES(Generalized Minimal RESidual)는 비대칭 정칙 행렬에 대한 선형계 $Ax = b$를, 매 반복마다 아핀 크리로프 부분공간 $x_0 + \mathcal{K}_m(A, r_0)$ 안에서 잔차의 2-노름을 최소화하는 근사해를 골라 푸는 반복법이다. 1986년 유세프 사드(Yousef Saad)와 마틴 슐츠(Martin H. Schultz)가 발표했고, 대칭성이 깨진 문제 — 대류항이 지배적인 대류-확산 방정식 이산화, 압축성 유동의 암시적 시간적분, 회로·전자기 해석에서 나오는 비대칭 계 — 에서 사실상 표준 참조 해법이 되었다.

이름의 “최소 잔차”가 전부다. 켤레기울기법이 대칭 양정치라는 특권을 이용해 오차의 에너지 노름을 최소화한다면, GMRES는 그런 특권 없이도 통하는 유일하게 자연스러운 양 — 그냥 잔차 노름 — 을 최소화한다. 대가는 나중에 치른다. 짧은 점화식이 존재하지 않아 기저 벡터를 전부 들고 있어야 한다는 것.¹

2. 아놀디 관계에서 최소제곱으로[편집]

$r_0 = b - Ax_0$, $\beta = \|r_0\|_2$, $v_1 = r_0/\beta$로 두고 아놀디 알고리즘을 $m$스텝 돌리면 정규직교 기저 $V_m = [v_1 \cdots v_m]$와 $(m+1)\times m$ 상헤센베르크 행렬 $\tilde{H}_m$이 나온다.

$$A V_m = V_{m+1} \tilde{H}_m$$

근사해를 $x = x_0 + V_m y$로 두면 잔차가 아주 예쁘게 접힌다.

$$b - Ax = r_0 - AV_m y = V_{m+1}\left(\beta e_1 - \tilde{H}_m y\right)$$

$V_{m+1}$의 열이 정규직교이므로 노름이 그대로 보존되고, 결국 원래 문제는

$$y_m = \arg\min_{y \in \mathbb{R}^m} \left\| \beta e_1 - \tilde{H}_m y \right\|_2$$

라는 $(m+1)\times m$짜리 꼬마 최소제곱 문제로 줄어든다. $n$이 백만이든 억이든, 실제로 푸는 건 $m$이 수십인 이 작은 문제다. 큰 행렬 $A$는 행렬-벡터 곱으로만 등장하므로 명시적으로 저장할 필요조차 없다(희소행렬이든 함수든 상관없다).

3. 기븐스 회전 — 잔차를 공짜로 얻는 법[편집]

$\tilde{H}_m$은 헤센베르크라 부대각선 아래에 성분이 딱 한 줄만 남아 있다. 이 한 줄을 기븐스 회전 $m$개로 지우면 QR 분해가 끝난다. 하우스홀더 변환을 쓰면 이미 0인 자리까지 건드리게 되니, 여기서는 원소 하나씩 조준하는 기븐스가 압도적으로 싸다.

진짜 이득은 증분 갱신이다. $m$스텝의 QR은 $m-1$스텝의 QR에 회전 하나를 더 얹은 것이므로, 반복마다 처음부터 다시 분해할 필요가 없다. 회전들을 $\beta e_1$에도 같이 먹여 $\bar{g} = (g_1, \dots, g_m, \gamma_{m+1})^\top$을 유지하면

$$\left\| b - A x_m \right\|_2 = \left| \gamma_{m+1} \right|$$

이 성립한다. 즉 $x_m$을 만들어 보지도 않고 잔차 노름을 스칼라 하나로 읽을 수 있다. 수렴 판정에 행렬-벡터 곱을 한 번도 더 쓰지 않는다는 뜻이고, 그래서 GMRES 로그의 잔차 곡선은 공짜로 그려진다. 해 $x_m$은 판정이 통과한 뒤 딱 한 번, 삼각계 후진대입 + $V_m y_m$ 조합으로 만든다.

4. 잔차 단조성과 유한 종료[편집]

크릴로프 공간은 $\mathcal{K}_1 \subseteq \mathcal{K}_2 \subseteq \cdots$로 중첩되어 있다. 더 큰 집합에서 최솟값을 다시 찾는데 결과가 커질 수는 없으므로

$$\|r_0\|_2 \ge \|r_1\|_2 \ge \|r_2\|_2 \ge \cdots$$

가 정의만으로 따라 나온다. 증명 한 줄짜리 성질이지만 실무 감각으로는 크다 — 잔차가 튀어 오르면 그건 알고리즘이 아니라 코드가 틀린 것이다.

여기서 CG와의 차이를 짚어야 한다. 켤레기울기법이 최소화하는 것은 잔차가 아니라 오차의 $A$-노름 $\|e\|_A$이고, 이 양은 단조 감소한다(오차의 2-노름도 감소한다). 하지만 잔차 2-노름은 CG의 목적함수가 아니라서 반복 중 얼마든지 출렁일 수 있고, 실제로 출렁인다. BiCGSTAB에 이르면 아예 몇 자릿수씩 널을 뛴다. “잔차 그래프가 예쁜 것”은 GMRES가 좋은 근사해를 준다는 증거가 아니라, 단지 그 양을 목적함수로 삼았다는 사실의 동어반복이다.²

반대로 단조성은 GMRES가 나쁜 소식을 숨기지 않는다는 뜻이기도 하다. 잔차가 정확히 그대로면 그 스텝의 크릴로프 방향이 전혀 도움이 안 됐다는 것이고, 이것을 완전 정체(complete stagnation)라 한다. 잔차가 널을 뛰는 해법에서는 이 진단이 불가능하다.

정확 산술에서 GMRES는 늦어도 $n$스텝 안에 정확해에 도달한다. 도중에 $h_{m+1,m} = 0$이 되면 이것은 고장이 아니라 행운의 붕괴(happy breakdown)로, $\mathcal{K}_m$이 $A$-불변이 되었다는 뜻이고 $x_m$이 정확해다. 정칙 행렬에서 GMRES가 붕괴하는 경우는 이것뿐이다.

5. 재시작 GMRES(m)과 정체[편집]

문제는 비용이 반복수와 함께 자란다는 것이다.

항목	$m$스텝 누적	감각
기저 저장	$O(mn)$	$n=10^6$, $m=200$이면 배정도 1.6 GB
직교화 연산	$O(m^2 n)$	스텝당 내적이 $m$개까지 선형 증가
작은 QR·최소제곱	$O(m^2)$	무시 가능

$m$이 수백을 넘으면 행렬-벡터 곱보다 직교화가 더 비싸지고, 메모리는 그보다 먼저 죽는다. 그래서 실무는 $m$번마다 현재 해를 새 초기값으로 삼아 기저를 통째로 버리고 다시 시작하는 **재시작 GMRES(m)**을 쓴다. PETSc의 기본값이 GMRES(30)인 것이 이 타협의 표준 좌표다.

재시작의 대가는 정체(stagnation)다. 기저를 버리는 순간 그동안 쌓은 방향 정보가 날아가므로, 최소화가 더 이상 전역이 아니라 매 사이클 국소가 된다. 잔차가 어느 값에서 딱 멈춰 며칠이 지나도 안 내려가는 로그를 보게 되는데, 이때 반복 횟수를 늘리는 것은 아무 의미가 없다. $m$을 키우거나 전처리기를 갈아 끼워야 한다. 심지어 $m$을 키우면 반드시 나아진다는 보장도 없어서, GMRES(10)이 GMRES(20)보다 빠른 반례가 알려져 있다.³

정체의 전형적 원인은 원점 근처의 고유값 몇 개다. 사이클마다 그 방향이 다시 살아나 잔차를 붙잡는다. 그래서 나온 것이 사이클 사이에 정보를 조금 물려주는 디플레이션 재시작이다.

• GMRES-DR(Deflated Restarting, Morgan 2002) — 사이클마다 작은 크기의 하모닉 리츠 벡터 몇 개를 계산해, 다음 사이클의 크릴로프 공간에 초기 부분공간으로 끼워 넣는다. 작은 고유값 방향을 사이클 사이에 보존하므로 정체가 크게 완화된다.
• 재순환(recycling, GCRO-DR) — 우변만 바뀌는 선형계를 연달아 풀 때(비정상 유동의 시간 전진, 뉴턴 반복의 내부 계) 이전 계에서 얻은 부분공간을 다음 계로 넘긴다. 뒤로 갈수록 반복 횟수가 줄어드는 게 눈에 보인다.

전체 GMRES가 사이클 하나로 끝나는 것과, 같은 총 반복수를 짧은 사이클로 쪼갠 것 사이의 격차가 정확히 “버린 정보의 값”이다.

6. 수렴 이론 — 고유값이 말해 주지 않는 것[편집]

$x_0 + \mathcal{K}_m$ 위의 최소화는 다항식 최소화와 같은 말이다. $r_m = p_m(A) r_0$이고 $p_m$은 차수 $\le m$, $p_m(0)=1$인 다항식 전체를 훑는다.

$A$가 정규행렬이면($AA^H = A^HA$, 즉 유니터리 대각화 가능) 이야기가 깔끔하다. 고유벡터 행렬이 유니터리라 조건수가 1이고, 따라서

$$\frac{\|r_m\|_2}{\|r_0\|_2} \le \min_{\substack{\deg p \le m \\ p(0)=1}} \max_{i} \left| p(\lambda_i) \right|$$

가 성립하며 이 한계는 (최악의 $b$에 대해) 날카롭다. 고유값이 원점에서 멀리, 한 덩어리로 뭉쳐 있으면 낮은 차수 다항식으로도 전부 눌러 죽일 수 있어 빠르게 수렴하고, 스펙트럼이 원점을 둘러싸면 그런 다항식이 존재하지 않아 느리다.

정규행렬에서도 이미 최악은 처참하다. $A$가 순환 자리이동 순열행렬이고 $b = e_1$이면 고유값은 단위원 위의 $n$제곱근으로 완벽하게 흩어져 있고 조건수는 1인데, $p(0)$이 그 근들에서의 평균값이라는 사실 때문에 $\max_i|p(\lambda_i)| \ge 1$이 강제된다. 결과는 $k < n$ 동안 잔차가 1도 안 줄고 $n$스텝째에 0으로 떨어지는 완전 정체. “조건수가 좋으면 빨리 수렴한다”는 직관은 여기서 이미 무너진다.

그리고 비정규 행렬에서는 위 부등식 자체가 성립하지 않는다. 대각화가 되더라도 고유벡터 행렬의 조건수 $\kappa(V)$가 곱해져 $\kappa(V)\min_p\max_i|p(\lambda_i)|$가 되는데, 이 값이 $10^{10}$이면 한계는 아무 정보도 주지 않는다. 결정적인 것은 그린바움·프타크·스트라코시(1996)의 정리다.

임의의 비증가 양수열 $f_0 \ge f_1 \ge \cdots \ge f_{n-1} > 0$과 임의의 0 아닌 복소수 $n$개가 주어졌을 때, 고유값이 정확히 그 $n$개이면서 GMRES 잔차가 정확히 $\|r_k\|_2 = f_k$인 행렬 $A$와 우변 $b$가 존재한다.

즉 스펙트럼과 수렴 곡선은 서로 아무것도 구속하지 않는다. 고유값을 완벽하게 뭉쳐 놓고도 $n-1$스텝까지 정체시킬 수 있고, 고유값을 원점 주위에 흩뿌려 놓고도 두 스텝에 수렴시킬 수 있다. 그래서 비정규 문제에서 “고유값 분포를 보니 수렴이 잘 되겠다”는 판단은 근거가 없다. 봐야 하는 것은 의사스펙트럼이나 수치적 치역(field of values) 같은 다른 양이다. 대칭부 $\tfrac{1}{2}(A+A^\top)$이 양정치이면 그로부터 나오는 엘만(Elman) 한계가 실제로 유효한 수렴률을 주는데, 대류가 세지면 이 조건부터 깨진다.⁴

7. 전처리와 변형[편집]

위 정리의 실무적 결론은 하나다. GMRES는 전처리기 없이 쓰는 물건이 아니다. 후보 메뉴판(ILU, 대수적 다중격자법, 영역 분할법 기반 슈바르츠)과 고르는 요령은 전처리기 문서에 있으니 여기서는 GMRES에만 걸리는 두 가지만 짚는다.

첫째, 좌 전처리를 쓰면 최소화 대상이 바뀐다. $M^{-1}Ax = M^{-1}b$를 풀면 GMRES가 줄이는 것은 참 잔차가 아니라 $\|M^{-1}(b-Ax)\|_2$이고, 기븐스에서 공짜로 나오는 $|\gamma_{m+1}|$도 그 값이다. $M$이 나쁘면 “수렴했다”는 로그가 그대로 거짓말이 된다. 우 전처리 $AM^{-1}u=b$는 최소화 대상이 참 잔차 그대로라 판정이 정직하고, 그래서 GMRES의 실무 기본값이다.

둘째, 전처리기가 반복마다 달라져도 되는 변형이 따로 있다. 아래 목록의 FGMRES가 그것이다.

• FGMRES(Flexible GMRES, Saad 1993) — 안쪽에 또 다른 반복법(또는 사이클 수가 유동적인 다중격자)을 전처리기로 끼우면 $M$이 매 반복 달라진다. 표준 GMRES는 이 경우 무너지지만, FGMRES는 전처리된 기저 $Z_m = [M_1^{-1}v_1 \cdots M_m^{-1}v_m]$를 따로 저장해 $x = x_0 + Z_m y$로 복원한다. 대가는 저장 두 배.

• MINRES — $A$가 대칭이면 헤센베르크가 삼중대각으로 붕괴해 3항 점화식이 살아난다. 저장이 $O(n)$으로 떨어지므로, 대칭 부정치 문제에 GMRES를 쓰는 것은 낭비다.

• DQGMRES / 절단 GMRES — 직교화를 최근 $k$개 벡터로만 제한한다. 저장은 고정되지만 잔차 최소성이 깨진다.

• GCR / ORTHODIR — 같은 최소잔차 원리의 다른 구현. 수학적으로는 동치지만 수치적 성질과 붕괴 조건이 다르다.

8. 구현과 로그 읽기[편집]

• 직교화. 고전 그람-슈미트를 쓰면 유한 정밀도에서 직교성이 빠르게 무너진다. 수정 그람-슈미트(MGS)가 기본이고, MGS-GMRES는 직교성이 상당히 망가진 뒤에도 후진 안정성이 유지된다는 것이 증명되어 있다(Paige–Rozložník–Strakoš, 2006). 다만 MGS는 축차 내적이라 분산 환경에서 스텝당 $m$번의 전역 축약(all-reduce)이 필요하고, 이게 통신 병목이 된다. 그래서 고전 GS를 두 번 돌리는 CGS2(축약을 한 번에 묶을 수 있다)나 하우스홀더 변환 기반 GMRES를 일부러 택하기도 한다. 통신 회피 계열은 아예 $s$스텝치 기저를 먼저 만들고 한꺼번에 직교화하는데, 그 중간 기저가 병적으로 나빠지지 않게 하는 것이 관건이다.
• 정지 조건. $|\gamma_{m+1}| \le \varepsilon\,\|b\|_2$ 처럼 상대 잔차로 잡는 것이 국룰이다. 절대 잔차로 잡으면 문제 스케일이 바뀔 때마다 기준이 흔들린다. 좌 전처리를 쓰고 있다면 이 값이 참 잔차가 아니라는 점을 이미 앞에서 봤다.
• 참 잔차 확인. 수렴 선언 뒤에는 $\|b - Ax_m\|_2$를 실제로 한 번 계산해 보는 것이 좋다. 재귀적으로 갱신된 $|\gamma_{m+1}|$과 참 잔차는 반올림 때문에 어긋날 수 있고, 특히 잔차를 $10^{-12}$ 아래로 몰아붙일 때 격차가 드러난다.
• 행렬 없는 구현. GMRES가 $A$에 요구하는 것은 “벡터를 넣으면 벡터가 나온다”뿐이다. 그래서 야코비안을 만들지 않고 $Av \approx (F(x+\epsilon v) - F(x))/\epsilon$로 대체하는 야코비안-프리 뉴턴-크릴로프(JFNK)가 성립한다. 뉴턴-랩슨법의 내부 선형 풀이를 GMRES로 하고, 그 정확도를 바깥 뉴턴 잔차에 맞춰 느슨하게 잡는(inexact Newton, Eisenstat–Walker 조건) 조합이 대규모 비선형 해석의 표준 골격이다.
• 로그 읽는 법. 잔차가 처음 몇 스텝 확 떨어졌다가 평평해지면 스펙트럼의 바깥쪽만 잡히고 원점 근처가 남았다는 신호 — 디플레이션이나 더 강한 전처리기가 답이다. 처음부터 아예 안 내려가면 재시작 주기 문제이거나 전처리기가 헛돌고 있다는 뜻이다. 잔차가 올라가면 그건 GMRES가 아니다. 코드를 의심해라.

9. 관련 문서[편집]

• 크리로프 부분공간법 · 아놀디 알고리즘 · 란초스 알고리즘
• 전처리기 · 다중격자법 · 영역 분할법
• 기븐스 회전 · QR 분해 · 하우스홀더 변환 · 최소자승법
• 비정규 행렬 · 의사스펙트럼 · 조건수
• 희소행렬 · 반복법 · PETSc
• 대류-확산 방정식 · 나비에-스토크스 방정식

10. Footnotes[편집]

1. 파버-만테펠(Faber–Manteuffel, 1984) 정리가 이걸 못 박았다. 최소잔차성을 유지하면서 짧은 점화식으로 굴러가는 크릴로프 해법은 사실상 대칭(정확히는 저차 정규) 행렬에서만 존재한다. 즉 GMRES의 메모리 폭식은 구현이 게을러서가 아니라 정리에 의해 금지된 최적화다. 억울하면 행렬을 대칭으로 만들어 오든가. ↩

2. 그래서 솔버 비교 논문에서 “잔차 곡선이 매끄럽다”를 장점처럼 파는 그림을 조심해야 한다. GMRES의 곡선이 매끄러운 건 물리적 정확도와 아무 관계가 없다. 진짜로 비교해야 하는 축은 반복 횟수도 아니고 벽시계 시간 대 참 오차다. ↩

3. 엠바리 등이 보인 반례들이 있다. 재시작 주기를 늘리면 사이클당 정보는 늘지만 사이클 수가 줄어드는 상충이 있어서, 두 효과의 곱이 단조롭지 않다. 결국 $m$은 이론이 아니라 메모리 예산과 몇 번의 실험으로 정한다. “일단 30으로 돌려” 가 국룰이 된 데는 이유가 있다. ↩

4. 트레페던-엠브리의 Spectra and Pseudospectra는 이 대목을 통째로 한 장에 걸쳐 다룬다. 요약하면 “비정규 행렬에게 고유값만 묻고 수렴을 예측하는 것은 점을 보는 것과 통계적으로 구분되지 않는다”쯤 된다. ↩