번치-카우프만 피벗

1. 개요

번치-카우프만 피벗 Bunch–Kaufman Pivoting
대상	대칭 부정치 행렬의 PAPT = LDLT
피벗	1×1 또는 2×2 대각 블록
탐색 비용	단계당 열 최대 2개, 전체 O(n2) 비교
판정 상수	α = (1+√17)/8 ≈ 0.6404
성장 상계	(1+1/α)n−1 ≈ 2.57n−1
구현	LAPACK xSYTRF·xSYSV, xHETRF

촐레스키는 음수를 싫어하고, 부분 피벗 LU 는 대칭을 버린다. 대칭을 지키면서 0 피벗을 피하려면 “두 칸짜리 피벗”을 허용하면 된다. 남은 문제는 언제 두 칸을 쓰느냐다.

번치-카우프만 피벗(Bunch–Kaufman pivoting)은 대칭 부정치 행렬을 $PAP^{\mathsf T} = LDL^{\mathsf T}$ ($D$ 는 1×1·2×2 블록 대각)로 분해할 때, 단계마다 많아야 열 두 개만 살펴보고 1×1 피벗을 쓸지 2×2 피벗을 쓸지, 어느 행을 끌어올지를 정하는 규칙이다. 번치와 카우프만이 1977년에 발표했고, 부분 피벗팅 가우스 소거법과 같은 $O(n^2)$ 탐색 비용으로 비슷한 수준의 원소 성장 상계를 얻는다. LAPACK 의 대칭 부정치 솔버 xSYTRF 가 이 규칙이다.

LDL 분해 문서가 왜 2×2 블록이 필요한지, 피벗 전략의 계보(번치-파렛·번치-카우프만·룩·아센), 관성 계산을 개괄했다. 이 문서는 번치-카우프만 하나를 해부한다 — 네 갈래 판정, 상수 $\alpha$ 가 그 값인 이유, 실측, 그리고 $L$ 이 커질 수 있다는 알려진 약점.

2. 알고리즘 — 네 갈래

현재 남은 부분행렬을 $A$ 라 하고(첫 열을 처리하는 단계), $\alpha = (1+\sqrt{17})/8$ 로 둔다.

1. 첫 열의 최대 비대각 크기 $\lambda = \max_{i>1} |a_{i1}|$ 와 그 행 번호 $r$ 을 찾는다. $\lambda = 0$ 이면 이미 소거할 게 없으니 $a_{11}$ 을 1×1 블록으로 두고 넘어간다.
2. $|a_{11}| \ge \alpha\lambda$ 이면 $a_{11}$ 을 1×1 피벗으로 쓴다. (대각이 열에서 충분히 크다.)
3. 아니면 $r$ 번째 열의 최대 비대각 $\sigma = \max_{j\ne r} |a_{jr}|$ 를 구한다(두 번째 열 탐색). $|a_{11}|\,\sigma \ge \alpha\lambda^2$ 이면 그래도 $a_{11}$ 을 1×1 피벗으로 쓴다.
4. 아니고 $|a_{rr}| \ge \alpha\sigma$ 이면 1행과 $r$ 행을 맞바꿔 $a_{rr}$ 을 1×1 피벗으로 쓴다.
5. 셋 다 아니면 2행과 $r$ 행을 맞바꿔 $\begin{pmatrix} a_{11} & a_{r1} \\ a_{r1} & a_{rr} \end{pmatrix}$ 을 2×2 피벗으로 쓴다.

마지막 경우 2×2 블록 $E$ 의 행렬식은 $a_{11}a_{rr} - \lambda^2$ 인데, 앞 조건들이 실패했다는 건 $|a_{11}a_{rr}| < \alpha^2 \lambda^2$ 라는 뜻이라 $|\det E| \ge (1-\alpha^2)\lambda^2 > 0$ 이다. 2×2 블록은 결코 특이하지 않다.¹ 대칭 행렬이니 행·열 교환을 함께 해 대칭을 유지하고, 하삼각 절반만 저장하며, 연산량은 촐레스키와 같은 $n^3/3$ 이다(LU 의 절반).

번치-파렛(1971)의 완전 피벗팅이 단계마다 남은 부분행렬 전체를 뒤지는 것($O(n^3)$ 비교)에 비해, 여기선 첫 열과 $r$ 열만 본다. 정보는 덜 쓰지만 판정 상수를 잘 고르면 성장 보장이 크게 나빠지지 않는다는 게 이 논문의 요점이다.

3. 왜 α = (1+√17)/8 인가

단계 하나에서 남은 부분행렬의 최대 원소가 몇 배까지 자랄 수 있는지 보자. $\mu$ 를 현재 최대 원소 크기라 하면, 번치-카우프만의 분석은 대략 이렇게 묶는다.

• 1×1 피벗 한 번: 성장 $\le 1 + 1/\alpha$ 배.
• 2×2 피벗 한 번(열 두 개를 한꺼번에 소거): 성장 $\le 1 + 2/(1-\alpha)$ 배.

공정하게 비교하려면 2×2 한 번을 1×1 두 번과 견줘야 하므로, 열당 성장률이 같도록

$$\Bigl(1 + \frac1\alpha\Bigr)^2 = 1 + \frac{2}{1-\alpha} \quad\Longleftrightarrow\quad 4\alpha^2 - \alpha - 1 = 0$$

을 풀면 양의 근이 $\alpha = (1+\sqrt{17})/8 \approx 0.6404$ 다. 실제로 이 값에서 $1 + 1/\alpha = 2.5616$ 이고 $1 + 2/(1-\alpha) = 6.5616 = 2.5616^2$ 이다. 그래서 전체 성장 상계는

$$\rho_n \le (1 + 1/\alpha)^{n-1} \approx 2.57^{\,n-1}$$

이다. 부분 피벗팅 LU 의 $2^{n-1}$ 보다 조금 크지만 같은 「지수적이되 실제로는 안 일어나는」 부류다. 대칭 3중대각 행렬 전용 판(번치 1974)은 같은 논리로 $\alpha = (\sqrt5 - 1)/2 \approx 0.618$ 을 쓴다².

4. 검산

피벗 없음 vs 번치-카우프만. $A = \begin{pmatrix} \varepsilon & 1 & 0 \\ 1 & \varepsilon & 1 \\ 0 & 1 & 1 \end{pmatrix}$, 정해 $\mathbf x = \mathbf 1$ 인 우변으로 풀었다.

$\varepsilon$	피벗 없는 $LDL^{\mathsf T}$ 최대 오차	그때 $\max\lvert\ell_{ij}\rvert$	LAPACK dsysv 최대 오차
$10^{-4}$	$2.2\times10^{-16}$	$10^{4}$	$2.2\times10^{-16}$
$10^{-8}$	$1.5\times10^{-8}$	$10^{8}$	$2.2\times10^{-16}$
$10^{-12}$	$1.0\times10^{-4}$	$10^{12}$	$0$

조건수는 셋 다 평범한데(행렬 원소가 전부 1 이하다) 피벗을 안 하면 $L$ 원소가 $1/\varepsilon$ 로 자라 그만큼 자릿수를 잃는다. 번치-카우프만은 첫 단계에서 $|a_{11}| = \varepsilon$ 이 $\alpha\lambda = 0.64$ 보다 작고, $a_{rr} = \varepsilon$ 도 작으니 5번 갈래로 가서 $\begin{pmatrix} \varepsilon & 1 \\ 1 & \varepsilon \end{pmatrix}$ 을 2×2 블록으로 잡는다. 그 블록의 행렬식은 $\varepsilon^2 - 1 \approx -1$ 이라 아무 문제가 없다.

실제 성장. 원소가 표준정규인 $100\times100$ 대칭 행렬 200개를 분해해 $\max|D| / \max|A|$ 를 재 보면 최댓값이 15.6 이었다. 상계 $2.57^{99}$ 와는 비교도 안 되게 작다. 부분 피벗팅 LU 처럼 지수적 성장은 일부러 만든 행렬에서나 나온다.

5. 약점 — L 이 묶이지 않는다

번치-카우프만이 보장하는 건 ”$D$ 와 남은 부분행렬의 원소 성장”이다. 정작 $L$ 의 원소는 묶이지 않는다. 3번 갈래에서 $|a_{11}|$ 이 $\alpha\lambda$ 보다 작은데도 $|a_{11}|\sigma \ge \alpha\lambda^2$ 라서 $a_{11}$ 을 피벗으로 쓰면, $\ell_{r1} = a_{r1}/a_{11}$ 이 $\lambda/|a_{11}|$ 만큼 커질 수 있다. 하이엄(1997)은 그래도 해 $\mathbf x$ 의 계산이 노름 의미로 후진 안정함을 증명했으므로, 연립방정식 하나 푸는 데는 문제가 없다.

문제는 $L$ 자체를 쓰는 경우다. 애슈크래프트·그라임스·루이스(1998)는 최적화·내점법에서 나오는 카루시-쿤-터커 조건의 안장점 행렬처럼 $L$ 을 반복해서 재사용하거나 $L$ 로 다른 양을 계산할 때 $\lVert L\rVert$ 이 터지는 예를 보이고, 행과 열을 번갈아 더듬어 “자기 행·열에서 최대인” 원소를 찾는 룩 피벗팅(bounded Bunch–Kaufman)을 제안했다. 이 경우 $|\ell_{ij}| \le \max\{1/(1-\alpha),\ 1/\alpha\}$ 같은 상수로 묶인다. 탐색이 열 2개에서 「필요한 만큼」으로 늘지만 실제로는 몇 열이면 끝난다. LAPACK 에는 xSYTRF_ROOK 으로 들어가 있다.

6. 어디서 쓰이나

• 대칭 부정치 직접 풀이. 구조 해석의 좌굴·이동된 고유값 문제($K - \sigma M$), 비압축성 유동·혼합 유한요소의 안장점 시스템 등. 부분 피벗 LU 보다 메모리·연산이 절반이고 대칭을 유지한다.
• 관성 세기. $D$ 의 블록별 고유값 부호를 세면 실베스터 관성 법칙에 의해 $A$ 의 양·음 고유값 개수가 나온다(2×2 블록은 위에서 본 대로 행렬식이 음수라 양·음 하나씩). 이동 $\sigma$ 를 바꿔 가며 세면 고유값 구간 개수를 이분법으로 찾는 스텀 수열식 계산이 된다.
• 내점법의 관성 보정. IPOPT 같은 비선형 내점법 솔버는 KKT 행렬을 대칭 부정치 분해하고, 관성이 “양수 $n$ 개, 음수 $m$ 개”가 아니면 헤세 블록에 $\delta I$ 를 더해 다시 분해한다. 희소 솔버(MA27·MA57 등)는 번치-카우프만을 희소 행렬용 임계 피벗으로 바꾼 1×1/2×2 전략을 쓴다³.

7. 관련 문서

• LDL 분해 · 촐레스키 분해 · LU 분해 · 가우스 소거법 · LAPACK
• 실베스터 관성 법칙 · 스텀 수열 · 후진 오차 해석 · 성장 인자
• 내점법 · 카루시-쿤-터커 조건 · 안장점 문제 · 희소 직접 솔버

8. Footnotes

1. 1×1 피벗이 작아서 피했는데 2×2 로 바꿨더니 그것도 특이하면 대참사다. 판정 조건 세 개가 실패한 사실 자체가 행렬식의 하한이 되도록 짜 놓은 게 이 알고리즘의 은근한 킬포다. ↩

2. 0.618 은 황금비의 역수다. 3중대각은 이웃이 둘뿐이라 볼 게 적고, 그래서 상수도 더 단순한 무리수로 떨어진다. 수치해석에서 황금비가 튀어나오면 대개 “두 경우의 최악을 같게 맞췄다”는 뜻이다. ↩

3. 희소 행렬에서는 “열에서 가장 큰 놈”을 피벗으로 끌어오면 채움(fill-in) 순서가 박살난다. 그래서 “충분히 큰 놈이면 원래 자리 그대로” 쓰는 임계값을 넣고, 안 되면 피벗을 미룬다. 안정성과 희소성의 줄다리기는 이 동네의 영원한 현생이다. ↩