쌍켤레 기울기법

1. 개요

쌍켤레 기울기법 Biconjugate Gradient (BiCG)
푸는 것	정칙 비대칭 선형계 Ax = b
반복당	A 곱 1회 + AT 곱 1회, 내적 2회
메모리	벡터 7~8개 (반복 수와 무관)
조건	잔차 ⟂ 그림자 크리로프 공간 (페트로프-갤러킨)
약점	잔차 비단조, 두 종류의 붕괴, AT 필요
계보	란초스(1952) → 플레처(1976) → CGS · QMR · BiCGSTAB

CG 가 대칭행렬에서 누리던 짧은 점화식을 비대칭에서도 갖고 싶다. 대가는 “최소화”를 포기하고, 거울 속 쌍둥이 시스템 하나를 같이 굴리는 것이다.

쌍켤레 기울기법(biconjugate gradient method, BiCG)은 비대칭 행렬 $A$ 에 대해 $A$ 와 $A^{\mathsf T}$ 로 두 크리로프 부분공간을 동시에 키우면서, 잔차가 그림자 공간에 직교하도록 해를 고르는 반복법이다. 켤레기울기법(CG)의 3항 점화식 구조를 그대로 물려받아 반복당 비용과 메모리가 상수이고, $A$ 가 대칭 양정치면 CG 와 정확히 같아진다. 뿌리는 란초스(1952)의 비대칭 란초스 과정이고, 오늘날의 형태는 플레처(1976)가 정리했다.

BiCGSTAB 문서가 BiCG→CGS→BiCGSTAB 계보와 안정화 다항식을 다뤘다. 이 문서는 그 출발점 BiCG 자체 — 알고리즘, 쌍직교성, 두 종류의 붕괴, 그리고 왜 아직도 쓸 이유가 있는지 — 를 다룬다.

2. 아이디어 — 최소화를 버리고 직교를 택하다

CG 는 대칭 양정치 $A$ 에서 $A$-노름 오차를 크리로프 공간 위에서 최소화한다. 비대칭이면 $A$-노름이 노름이 아니라 이 길이 막힌다. 남은 선택은 둘이다.

• 잔차 최소화를 지킨다 → GMRES. 매 반복 모든 이전 기저와 직교화해야 해서 메모리·연산이 반복 수에 비례해 는다.
• 짧은 점화식을 지킨다 → BiCG. 최소화 대신 페트로프-갤러킨 조건

$$\mathbf r_k = \mathbf b - A\mathbf x_k \;\perp\; \mathcal K_k(A^{\mathsf T}, \hat{\mathbf r}_0) = \mathrm{span}\{\hat{\mathbf r}_0, A^{\mathsf T}\hat{\mathbf r}_0, \dots\}$$

을 건다. $\hat{\mathbf r}_0$ 는 임의로 고르는 그림자 잔차(대개 $\hat{\mathbf r}_0 = \mathbf r_0$)다. 이 조건이면 비대칭 란초스 알고리즘이 만드는 두 기저가 서로 쌍직교(biorthogonal)해지고, 그 덕에 3항 점화식이 살아난다. 파버-만토이펠 정리가 말하듯 비대칭 행렬 일반에 대해 “짧은 점화식 + 최적성”은 함께 가질 수 없으니, 이건 의식적인 맞교환이다¹.

3. 알고리즘

$\mathbf x_0$ 에서 $\mathbf r_0 = \mathbf b - A\mathbf x_0$, $\hat{\mathbf r}_0$ 선택, $\mathbf p_0 = \mathbf r_0$, $\hat{\mathbf p}_0 = \hat{\mathbf r}_0$.

$$\begin{aligned} \alpha_k &= \frac{(\hat{\mathbf r}_k, \mathbf r_k)}{(\hat{\mathbf p}_k, A\mathbf p_k)}, \\ \mathbf x_{k+1} &= \mathbf x_k + \alpha_k \mathbf p_k, \\ \mathbf r_{k+1} &= \mathbf r_k - \alpha_k A\mathbf p_k, \qquad \hat{\mathbf r}_{k+1} = \hat{\mathbf r}_k - \alpha_k A^{\mathsf T}\hat{\mathbf p}_k, \\ \beta_k &= \frac{(\hat{\mathbf r}_{k+1}, \mathbf r_{k+1})}{(\hat{\mathbf r}_k, \mathbf r_k)}, \\ \mathbf p_{k+1} &= \mathbf r_{k+1} + \beta_k \mathbf p_k, \qquad \hat{\mathbf p}_{k+1} = \hat{\mathbf r}_{k+1} + \beta_k \hat{\mathbf p}_k. \end{aligned}$$

CG 와 한 줄씩 대응한다. 다른 점은 내적의 한쪽이 그림자 벡터라는 것, 그리고 $A^{\mathsf T}$ 곱으로 그림자 쪽을 같이 갱신한다는 것뿐이다. 정확한 산술에서 다음이 성립한다.

$$(\hat{\mathbf r}_i, \mathbf r_j) = 0,\qquad (\hat{\mathbf p}_i, A\mathbf p_j) = 0 \qquad (i \ne j).$$

앞의 것이 쌍직교성, 뒤의 것이 이름의 유래인 쌍켤레성이다. 아래 검산 문제에서 처음 10개 잔차로 정규화한 $(\hat{\mathbf r}_i, \mathbf r_j)$ 행렬을 만들면 비대각 최댓값이 $2.6\times10^{-16}$ 이다.

덤: 쌍대 시스템이 공짜다. $\hat{\mathbf r}_0 = \hat{\mathbf b} - A^{\mathsf T}\hat{\mathbf x}_0$ 으로 잡고 $\hat{\mathbf x}_{k+1} = \hat{\mathbf x}_k + \alpha_k \hat{\mathbf p}_k$ 를 한 줄 추가하면 $A^{\mathsf T}\hat{\mathbf x} = \hat{\mathbf b}$ 도 같이 풀린다. 수반법으로 목표 함수의 민감도나 목표 지향 오차 추정을 할 때 원 문제와 수반 문제가 한 번에 나온다는 뜻이고, 이게 BiCG 가 $A^{\mathsf T}$ 를 요구하는 단점을 상쇄하는 거의 유일한 장면이다.

4. 두 종류의 붕괴

나눗셈이 두 군데 있으니 0으로 나누는 길도 둘이다.

• 란초스 붕괴 — $(\hat{\mathbf r}_k, \mathbf r_k) = 0$ 인데 $\mathbf r_k \ne 0$. 두 공간이 서로를 못 보게 된 경우다. 고치려면 룩어헤드 란초스(파렛-테일러-류 1985, 프로인트-구트크네히트-나흐티갈 1993)처럼 여러 스텝을 블록으로 묶어 건너뛴다.
• 피벗 붕괴 — $(\hat{\mathbf p}_k, A\mathbf p_k) = 0$. 내부적으로 삼중대각 행렬을 피벗 없이 LU 분해하다 0 피벗을 만난 것과 같다.

후자는 아주 작은 예로 바로 재현된다. $A = \begin{pmatrix}0&1\\1&0\end{pmatrix}$ (대칭이지만 부정치), $\mathbf b = (1, 0)^{\mathsf T}$, $\mathbf x_0 = 0$, $\hat{\mathbf r}_0 = \mathbf r_0$ 이면 첫 분모가 $\mathbf r_0^{\mathsf T} A \mathbf r_0 = 0$ 이라 첫 스텝에서 죽는다. 해 $(0,1)^{\mathsf T}$ 는 멀쩡히 있는데도. 정확히 0 은 드물지만 거의 0 은 흔하고, 그게 다음 절의 들쭉날쭉함의 원인 중 하나다².

5. 검산 — 대류-확산 방정식

$[0,1]^2$ 의 대류-확산 방정식을 $40\times40$ 내부 격자($n = 1600$)에서 5점 중앙차분하고, 대각 방향 흐름의 격자 페클레 수 $\mathrm{Pe}_h$ 를 바꿔 가며 $\mathbf b = \mathbf 1$, $\mathbf x_0 = 0$ 을 상대 잔차 $10^{-10}$ 까지 풀었다. ($\mathrm{Pe}_h < 2$ 이므로 행렬은 모두 M-행렬이다 — “착한” 행렬이다.)

$\mathrm{Pe}_h$	BiCG 반복	참 잔차 / 재귀 잔차	GMRES(전체)	BiCGSTAB
0 (대칭)	82 (CG 도 82)	—	—	—
0.5	146	$2.7\times10^{-11}$	—	—
1.0	152	$3.2\times10^{-9}$ / $7.9\times10^{-11}$	94	78
1.2	247	$1.1\times10^{-7}$ / $8.0\times10^{-11}$	—	—
1.5	3000 회에도 미수렴	오히려 커짐	87	83

읽을 것 세 가지.

• 대칭이면 CG 와 같다. $\mathrm{Pe}_h = 0$ 에서 반복 수까지 똑같이 82다.
• 잔차가 비단조다. $\mathrm{Pe}_h = 1$ 에서 152 스텝 중 65 스텝이 잔차를 키웠고, 한 스텝에 69배 튄 적도 있다. 이 큰 중간 잔차가 반올림을 키워 재귀로 갱신한 잔차와 실제 $\mathbf b - A\mathbf x$ 가 벌어진다($\mathrm{Pe}_h = 1.2$ 에서 세 자릿수 차이). 수렴 판정을 재귀 잔차로만 하면 속는다.
• 비정규성이 세지면 무너진다. $\mathrm{Pe}_h = 1.5$ 에서는 GMRES·BiCGSTAB 가 90회 안팎에 끝나는데 BiCG 는 유한 정밀도에서 쌍직교성을 잃고 수렴하지 못했다(직접 구현과 SciPy bicg 가 같은 거동). 행렬 자체는 M-행렬이고 조건수도 나쁘지 않은데 이렇다는 게 요점이다.

비용 환산도 해 두자. BiCG 는 반복당 행렬-벡터 곱이 2회($A$, $A^{\mathsf T}$)라 $\mathrm{Pe}_h = 1$ 에서 304회, BiCGSTAB 도 반복당 2회라 156회다. GMRES 는 94회로 가장 적지만 기저 벡터 94개를 들고 직교화 비용이 반복 수의 제곱으로 는다.

6. 후손들과 지금의 쓰임

BiCG 의 두 약점(들쭉날쭉한 잔차, $A^{\mathsf T}$ 곱)을 각각 고친 게 후손들이다.

• QMR(프로인트-나흐티갈 1991): 같은 란초스 기저 위에서 잔차를 “준최소화”해 곡선을 매끄럽게 하고, 룩어헤드로 붕괴도 피한다. 여전히 $A^{\mathsf T}$ 가 필요하다. 전치 없는 판 TFQMR(1993)이 뒤따랐다.
• CGS(소네벨트 1989): 잔차 다항식을 제곱해 $A^{\mathsf T}$ 를 없앴지만 들쭉날쭉함도 제곱됐다.
• BiCGSTAB(판데르포르스트 1992)·IDR(s): 제곱 대신 국소 최소화 인자를 곱해 다림질한다. 오늘날 실무 기본값이다.

그래서 순수 BiCG 를 기본 솔버로 쓰는 일은 드물다. 그래도 남는 자리가 있다 — 원·수반 문제를 동시에 풀어야 할 때, 그리고 전처리기를 붙인 BiCG 가 내부적으로 만드는 비대칭 란초스 삼중대각 행렬에서 고유값 추정을 덤으로 뽑을 때다. 또 모든 후손의 계수가 BiCG 계수에서 나오므로, 후손의 붕괴를 디버깅하려면 결국 이 문서의 점화식을 들여다봐야 한다³.

7. 관련 문서

• 켤레기울기법 · BiCGSTAB · GMRES · 크리로프 부분공간법 · 란초스 알고리즘
• QMR · IDR(s) · 전처리기 · 수반법
• 대류-확산 방정식 · M-행렬 · 비정규 행렬 · 희소행렬

8. Footnotes

1. 파버-만토이펠(1984)은 “고정된 짧은 점화식으로 어떤 내적에서의 최적성을 갖는 크리로프 방법”이 가능한 행렬을 사실상 정규 행렬 계열로 좁혔다. 비대칭 세계에서 공짜 점심은 법으로 금지돼 있다. ↩

2. 그림자 잔차를 난수 벡터로 잡으면 정확한 붕괴 확률은 0에 가까워진다. 그렇다고 “거의 붕괴”까지 사라지진 않는다. 거울을 아무리 잘 닦아도 거울 속의 나와 눈이 안 마주치는 순간은 온다. ↩

3. “BiCGSTAB 가 이상해요” 하고 열어 보면 $\rho = (\hat{\mathbf r}_0, \mathbf r_k)$ 가 $10^{-30}$ 쯤에서 놀고 있는 경우가 태반이다. 손자 병의 원인은 할아버지 유전자다. ↩