크릴로프-슈어 방법

수치해석 시뮬레이션 마지막 수정: 2026-08-03 04:38:52

1. 개요[편집]

크릴로프-슈어 방법 Krylov–Schur method
제안	G. W. Stewart (2001)
해결한 문제	암시적 재시작 아놀디(IRAM)의 유한정밀도 취약성과 purging·locking의 번거로움
핵심 아이디어	아놀디 분해를 슈어형으로 재배열한 뒤 뒤를 그냥 잘라낸다
대칭 대응물	두꺼운 재시작 란초스(thick-restart Lanczos)
대표 구현	SLEPc `EPSKRYLOVSCHUR`(기본값), MATLAB `eigs`

원치 않는 방향을 정교하게 소거하려니 유한정밀도가 발목을 잡는다. 그러면 소거하지 말고 그냥 버리면 되잖아?

크릴로프-슈어 방법(Krylov–Schur method)은 아놀디 알고리즘의 분해를 슈어 형태로 재배열해, 원하는 리츠쌍을 앞쪽에 모은 뒤 뒤쪽 열을 단순히 잘라내는 것으로 재시작을 구현하는 고유값 해법이다. 2001년 G. W. 스튜어트가 제안했고, 오늘날 대형 비대칭 고유값 문제의 사실상 표준 재시작 전략이다.

배경은 이렇다. 크리로프 부분공간법으로 고유값을 뽑을 때 부분공간을 무한정 키울 수는 없으므로 언젠가 재시작해야 한다. 1992년 소렌센의 암시적 재시작 아놀디(IRAM)가 이 문제의 정답으로 자리 잡았고 ARPACK이라는 걸출한 구현을 낳았지만, 그 우아한 암시적 QR 시프트 메커니즘에는 유한정밀도에서의 약점과 구현상의 번거로움이 있었다. 크릴로프-슈어는 같은 부분공간을 만들면서 그 메커니즘만 안전한 것으로 갈아 끼운다. 수학적으로 새로운 고유값을 찾아주는 게 아니라, 이미 알던 것을 훨씬 덜 위험하게 하는 방법이다.¹

2. IRAM이 겪는 문제[편집]

$m$ 단계 아놀디는 다음 관계를 만든다.

A V_m = V_m H_m + h_{m+1,m}\, \mathbf{v}_{m+1} \mathbf{e}_m^{\mathsf{T}}

$V_m$ 은 정규직교, $H_m$ 은 상 헤센베르크, 그리고 잔차 항이 마지막 열에만 붙는다는 것이 아놀디 분해의 정의적 성질이다. IRAM은 $m = k + p$ 까지 확장한 뒤 원치 않는 리츠값 $p$ 개를 시프트로 삼아 암시적 QR 스텝을 $p$ 번 적용한다. 정확한 산술에서는 이 시프트가 해당 방향의 성분을 정확히 소거하고, 갱신된 분해의 앞 $k$ 열이 다시 온전한 $k$ 차 아놀디 분해가 된다. 아름답다. 문제는 유한정밀도다.

암시적 QR의 전방 불안정성. 시프트가 $H_m$ 의 실제 고유값에 매우 가까울 때 암시적 QR 스텝은 전방 불안정하다(파렛-르, 1993). 그런데 IRAM의 “정확 시프트(exact shift)” 전략은 원치 않는 리츠값을 그대로 시프트로 쓴다 — 즉 가장 위험한 조건을 알고리즘이 스스로 매 재시작마다 만들어낸다.² 소거되어야 할 성분이 깨끗이 사라지지 않고 반올림 수준의 찌꺼기로 남으면, 갱신된 행렬이 더 이상 의도한 부분공간의 헤센베르크 표현이 아니게 된다.
불변 부분공간 정리의 번거로움. 수렴한 고유쌍을 고정하고(locking) 원치 않는 수렴 성분을 걷어내는(purging) 작업을 IRAM에서 하려면, 헤센베르크 구조를 유지한 채 원소들을 옮겨야 한다. 헤센베르크는 부대각 하나에 정보가 매달린 취약한 구조라, 이 조작들은 르훅-소렌센(1996)의 별도 논문이 필요할 만큼 까다롭다.
부수적인 성가심. 실행렬의 복소 켤레 시프트는 이중 시프트 벌지 추적으로 처리해야 하고, 크기가 극단적인 시프트는 별도 방어가 필요하다.

정리하면 IRAM의 문제는 “방향을 소거한다”는 연산 자체가 취약하다는 데 있다.

3. 크릴로프 분해와 슈어 재배열[편집]

스튜어트의 첫 수는 아놀디 분해의 정의를 느슨하게 푸는 것이다. 크릴로프 분해를

A V_m = V_m B_m + \mathbf{v}_{m+1} \mathbf{b}^{\mathsf{T}}

로 정의한다. $B_m$ 은 헤센베르크일 필요가 없고, 잔차 벡터 $\mathbf{b}$ 도 $\mathbf{e}_m$ 의 상수배일 필요가 없다. 스튜어트가 보인 핵심 정리는 모든 크릴로프 분해는 같은 부분공간을 span하는 아놀디 분해와 동치라는 것이다(직교 유사변환과 정규직교화로 서로 옮겨 갈 수 있다). 즉 계산 도중에는 편한 형태를 쓰다가 필요할 때 아놀디로 되돌리면 된다. 이 자유도가 뒤의 모든 것을 가능하게 한다.

이제 $H_m$ 의 실 슈어 분해 $H_m = Q S Q^{\mathsf{T}}$ 를 계산하고(QR 분해를 반복하는 표준 QR 알고리즘, LAPACK의 dhseqr) $V_m \leftarrow V_m Q$ , $\mathbf{b}^{\mathsf{T}} \leftarrow h_{m+1,m}\mathbf{e}_m^{\mathsf{T}}Q$ 로 바꾼다.

A V_m = V_m S_m + \mathbf{v}_{m+1}\mathbf{b}^{\mathsf{T}}

이것이 크릴로프-슈어 분해다. $S_m$ 은 준상삼각(실수 켤레쌍만 $2\times 2$ 블록)이므로 리츠값이 대각에 그대로 노출되고, 잔차 정보는 전부 벡터 $\mathbf{b}$ 한 줄에 들어 있다. 다음으로 슈어 형태를 재배열해 원하는 리츠값 $k$ 개를 앞쪽으로 모은다. 이건 LAPACK dtrsen/dtrexc가 하는 완전히 표준적인 연산으로, 인접한 대각 블록을 직교 유사변환으로 맞바꾸는 것이다.³

4. 왜 잘라내는 것이 안전한가[편집]

재배열이 끝나면 앞 $k$ 열만 남기고 나머지를 버린다.

A V_k = V_k S_k + \mathbf{v}_{m+1}\mathbf{b}_k^{\mathsf{T}}

$S_m$ 이 블록 상삼각이므로 앞 $k$ 열의 상은 앞 $k$ 열만으로 표현된다 — 즉 위 식은 근사가 아니라 원래 관계식에서 그대로 떨어져 나온 정확한 항등식이다. 여전히 유효한 $k$ 차 크릴로프 분해이므로, 여기서 $\mathbf{v}_{m+1}$ 부터 아놀디 확장을 이어 붙이면 재시작 한 사이클이 완성된다.

안전성의 근거는 이 절차에 소거가 없다는 데 있다.

슈어 분해와 재배열은 전부 직교 유사변환이다. 직교변환은 후진 오차 해석 관점에서 후진안정하고 노름을 보존하므로, 누적 오차가 $O(u)\lVert A\rVert$ 수준에 머문다.
절단은 뺄셈이 아니라 열 삭제다. “거의 상쇄되는 두 수를 빼서 0을 만들어야 하는” 상황 자체가 없으므로 자리수 손실이 발생할 여지가 없다. 원치 않는 방향을 없애는 IRAM의 QR 시프트가 바로 그 위험한 뺄셈이었다.
정확한 산술에서는 정확 시프트를 쓴 IRAM과 같은 부분공간이 나온다. 즉 수렴 성질을 잃지 않으면서 위험한 단계만 교체한 것이다.

한 사이클을 정리하면 다섯 줄이다.

현재 $k$ 차 분해에서 아놀디로 $m$ 차까지 확장한다(수정 그람-슈미트 + 재직교화).
$H_m$ 의 실 슈어 분해를 계산하고 $V_m \leftarrow V_m Q$ 로 기저를 회전한다.
원하는 리츠값이 앞에 오도록 슈어 형태를 재배열한다.
잔차 벡터 $\mathbf{b}$ 의 성분으로 수렴 여부를 판정해 앞쪽 블록을 lock한다.
앞 $k$ 열만 남기고 절단한 뒤 1번으로 돌아간다.

전부 LAPACK의 조밀행렬 루틴과 $A\mathbf{v}$ 곱 하나로 구성된다. 큰 행렬을 건드리는 연산은 확장 단계의 행렬-벡터 곱과 재직교화뿐이고, 나머지는 $m \times m$ 짜리 작은 작업이라 비용에서 거의 보이지 않는다.

5. locking과 purging이 자명해진다[편집]

슈어 형태의 진짜 배당금은 여기서 나온다. 준상삼각 $S_k$ 에서 앞 $j$ 개 열이 이루는 공간은 정확히 $S_k$ 의 불변 부분공간이고, 그 슈어 벡터의 잔차 노름은 다름 아닌 $\lvert b_i \rvert$ — 잔차 벡터 $\mathbf{b}$ 의 해당 성분 하나다. 그래서

locking: $\lvert b_i \rvert \le \epsilon\lVert A\rVert$ 인 앞쪽 블록은 수렴했다고 선언하고 그냥 건드리지 않는다. 이후 확장에서 새 벡터를 이들에 직교화하기만 하면 된다. 헤센베르크 구조를 유지하려고 씨름할 필요가 없다.
purging: 원치 않는데 수렴해 버린 성분은 재배열로 뒤쪽에 보낸 뒤 절단에서 함께 사라진다. 별도의 알고리즘이 아니라 이미 하고 있는 절단의 부산물이다.

IRAM에서 각각 별도 논문급 처리가 필요했던 두 연산이, 슈어 형태에서는 “앞쪽은 냅두고 뒤쪽은 자른다”는 한 문장으로 합쳐진다. 크릴로프-슈어가 IRAM을 대체한 실질적 이유는 안정성보다도 오히려 이 구현 단순성이라는 평가가 많다.

6. 실무 — 어디에 들어 있나[편집]

SLEPc. EPSKRYLOVSCHUR가 기본 solver다. 대칭·비대칭, 일반화 문제, 시프트-역변환(역반복법의 스펙트럼 변환 판), 이차 고유값 문제까지 같은 뼈대로 처리한다.
ARPACK과의 관계. ARPACK은 IRAM/IRLM 구현이다. 즉 ARPACK과 크릴로프-슈어는 경쟁 소프트웨어가 아니라 같은 목표의 두 세대다. ARPACK이 잘못됐다는 뜻이 아니라 — 20년 넘게 과학계산의 주력이었다 — 재시작 메커니즘 쪽에 더 안전한 대안이 나왔다는 뜻이다. MATLAB의 eigs도 오래도록 ARPACK을 호출하다가 이후 크릴로프-슈어 기반 자체 구현으로 갈아탔다.
대칭인 경우. $A$ 가 대칭이면 $H_m$ 이 삼중대각이고 슈어형은 대각행렬이 된다. 절단 후 남는 것은 대각 + 마지막 행이 채워진 “화살촉(arrowhead)” 형태이고, 이게 우와 사이먼(2000)의 **두꺼운 재시작 란초스 알고리즘**과 정확히 같다. 두 방법이 독립적으로 같은 지점에 도달한 셈이다.
내부 고유값. 스펙트럼 안쪽을 노리면 표준 리츠 추출이 부실해지므로 하모닉 리츠값이나 시프트-역변환을 얹는다. 후자는 매 반복 희소행렬 선형계를 풀어야 하므로 인수분해 비용이 지배적이 된다. 전처리기를 자연스럽게 쓰고 싶으면 LOBPCG나 데이비드슨 알고리즘 계열이 다른 답이다.
파라미터 감각. 부분공간 최대 크기 $m$ 은 원하는 고유값 개수 $k$ 의 2~3배가 국룰이다. 너무 작으면 재시작이 잦아 수렴이 느려지고, 너무 크면 재직교화 비용이 $O(nm^2)$ 으로 부풀며 메모리도 함께 터진다.⁴

모드 해석에서 최저 진동수 다발을 뽑을 때, 축소차수모델의 지배 모드를 고를 때, 플러터나 정적 발산 같은 안정성 문제에서 우반평면 고유값을 감시할 때 — 뒤에서 도는 것은 대개 이 알고리즘이다. 사용자가 그 존재를 모른 채 지나가는 것이, 어쩌면 이 방법이 받은 최고의 찬사다.

7. 관련 문서[편집]

이런 종류의 논문이 사실 제일 좋은 논문이다. 새 기능을 하나도 추가하지 않으면서 기존 기능을 “이제 안 무섭게” 만들어 준다. 크릴로프-슈어를 쓰는 사람 대부분은 자기가 IRAM의 어떤 지뢰를 피해 갔는지 평생 모른 채 산다. ↩
파렛과 르가 지적한 전방 불안정성은 “QR 알고리즘이 후진불안정하다”는 뜻이 아니다. 최종 고유값 계산은 여전히 후진안정하다. 다만 중간 단계의 변환행렬 $Q$ 가 의도한 것과 크게 달라질 수 있다는 것이고, IRAM처럼 그 $Q$ 를 다른 곳(부분공간 갱신)에 재활용하는 순간 문제가 된다. ↩
슈어 형태 재배열(dtrexc)은 인접한 대각 블록 두 개를 맞바꾸는 연산을 반복하는 것으로, 그 자체가 오래전부터 제어이론에서 리아푸노프·리카티 방정식을 풀 때 쓰던 표준 도구였다. 새 도구를 발명한 게 아니라 옆 동네에서 이미 검증된 도구를 가져온 것이 이 방법의 실제 모습이다. ↩
" $m \approx 2k \sim 3k$ "는 이론이 아니라 경험칙이다. 그리고 SLEPc나 eigs가 자동으로 잡아 주는 기본값이 대개 이 범위다. 파라미터를 손대기 전에 기본값으로 한 번 돌려 보는 것이, 이 바닥에서 시간을 아끼는 가장 확실한 방법이다. ↩