란초스 알고리즘

수치해석 소프트웨어 마지막 수정: 2026-07-25 04:34:22

1. 개요[편집]

란초스 알고리즘 Lanczos Algorithm
제안	Cornelius Lanczos, 1950
적용 행렬	대칭(실) · 에르미트(복소)
핵심 구조	3항 점화식 → 삼중대각화
필요 연산	행렬-벡터 곱 $Av$ 하나
대표 구현	ARPACK, MATLAB `eigs`, SciPy `eigsh`
최대 약점	유한 정밀도에서의 직교성 붕괴

삼중대각으로 줄여놓고 나면, 나머지는 LAPACK이 알아서 한다.

란초스 알고리즘(Lanczos algorithm)은 대칭(또는 에르미트) 행렬 $A$ 를 행렬-벡터 곱 $A\mathbf{v}$ 만으로 삼중대각 행렬로 사영해, 극단(최대·최소)에 있는 고유쌍 몇 개를 빠르게 뽑아내는 크리로프 부분공간법 계열 반복 알고리즘이다. 1950년 코넬리우스 란초스가 “선형 미분·적분 연산자의 고유값 문제를 푸는 반복적 최소화 방법”이라는 제목으로 발표했다.

고유값 문제 문서가 알고리즘 지도를 그리고 크리로프 부분공간법 문서가 선형계 해법(CG·GMRES) 쪽을 다룬다면, 이 문서는 대칭 고유값 문제 전용 도구로서의 란초스를 파고든다. 행렬 원소를 저장할 필요조차 없이 “ $A$ 를 벡터에 곱하는 서브루틴” 하나만 있으면 $10^9$ 차원 희소행렬에서도 최저 고유값 수십 개를 건질 수 있다는 것이 이 알고리즘의 존재 이유다.¹

대역폭이 좁은 대칭 밴드 행렬(N=200)에 실제 란초스 반복을 돌려, 최저 고유쌍의 잔차 노름을 반복수 대비 log 스케일로 그린다. 비교용으로 같은 행렬에 대한 거듭제곱법(power iteration) 곡선이 함께 표시되며, 크리로프 부분공간을 쌓는 쪽이 단일 벡터를 반복 곱하는 쪽보다 훨씬 가파르게 떨어지는 것이 요점. 재직교화는 하지 않은 단순 구현이라 반복이 길어지면 곡선이 정체될 수 있다.

2. 3항 점화식과 삼중대각화[편집]

시작 벡터 $\mathbf{v}_1$ ( $\|\mathbf{v}_1\|=1$ )에서 출발해 크리로프 부분공간

\mathcal{K}_m(A, \mathbf{v}_1) = \mathrm{span}\{\mathbf{v}_1,\ A\mathbf{v}_1,\ \dots,\ A^{m-1}\mathbf{v}_1\}

의 정규직교 기저를 만든다. $A$ 가 대칭이면 그람-슈미트 계수 대부분이 정확히 0이 되어, 새 벡터를 직전 두 개하고만 직교화하면 되는 3항 점화식으로 붕괴한다.

\beta_j \mathbf{v}_{j+1} = A\mathbf{v}_j - \alpha_j \mathbf{v}_j - \beta_{j-1}\mathbf{v}_{j-1}, \qquad \alpha_j = \mathbf{v}_j^{\mathsf{T}} A \mathbf{v}_j

$\beta_j$ 는 우변 벡터의 노름으로 잡아 정규화한다. 여기서 $\alpha_j$ 를 대각, $\beta_j$ 를 부대각에 채운 $m \times m$ 삼중대각 행렬 $T_m$ 과 기저 행렬 $V_m = [\mathbf{v}_1 \cdots \mathbf{v}_m]$ 을 놓으면 알고리즘 전체가 한 줄로 요약된다.

A V_m = V_m T_m + \beta_m \mathbf{v}_{m+1}\mathbf{e}_m^{\mathsf{T}}

즉 거대한 $A$ 의 작용이 $\mathcal{K}_m$ 위에서는 조그만 삼중대각 $T_m$ 으로 압축되고, 그 밖으로 새는 성분은 마지막 열 하나에 몰려 있다. 저장 비용이 벡터 세 개뿐이라는 점이 결정적이다 — 아놀디 알고리즘이 기저 벡터를 전부 들고 있어야 하는 것과 대비된다.

3. 리츠값과 극단 고유값 우선 수렴[편집]

$T_m$ 의 고유쌍 $T_m \mathbf{y} = \theta \mathbf{y}$ 를 QR 분해 기반 삼중대각 전용 루틴으로 푼 뒤, $\theta$ 를 리츠값(Ritz value), $\mathbf{x} = V_m\mathbf{y}$ 를 리츠벡터라 부른다.² 위 관계식에 곧바로 대입하면 잔차 노름이 공짜로 나온다.

\|A\mathbf{x} - \theta\mathbf{x}\| = |\beta_m| \cdot |\mathbf{e}_m^{\mathsf{T}}\mathbf{y}|

$N$ 차원 벡터를 만들어보지도 않고 $\mathbf{y}$ 의 마지막 성분 하나로 수렴을 판정할 수 있다는 뜻이다. 실제 구현이 매 스텝 $A\mathbf{v}$ 한 번 값에 수렴 판정을 붙일 수 있는 이유가 여기 있다.

수렴은 스펙트럼 양 끝에서 먼저 일어난다. 카니엘-페이지(Kaniel–Paige) 이론은 최대 고유값 $\lambda_1$ 에 대한 리츠값 오차를 체비셰프 다항식으로 눌러 준다.

0 \le \lambda_1 - \theta_1^{(m)} \le (\lambda_1 - \lambda_N)\, \frac{\tan^2\angle(\mathbf{v}_1, \mathbf{u}_1)}{T_{m-1}(1+2\gamma)^2}, \qquad \gamma = \frac{\lambda_1-\lambda_2}{\lambda_2-\lambda_N}

직관은 단순하다. 크리로프 부분공간에서 고른다는 건 $A$ 의 다항식을 고른다는 뜻이고, 체비셰프 다항식은 스펙트럼 대부분을 눌러 놓고 양 끝만 폭발적으로 키우는 데 최적이다. 상대 간격 $\gamma$ 가 클수록, 즉 원하는 고유값이 나머지 무리에서 떨어져 있을수록 수렴이 지수적으로 빠르다. 반대로 스펙트럼 한복판의 고유값은 이 논리가 전혀 안 먹혀서, 시프트-역변환(shift-invert)으로 $(A-\sigma I)^{-1}$ 을 대신 돌려 원하는 구간을 스펙트럼 양 끝으로 끌어올린다.³

4. 유령 고유값 — 유한 정밀도의 배신[편집]

칠판 위에서 $V_m$ 의 열은 완벽히 직교한다. 부동소수점 연산 위에서는 아니다. 페이지(C. C. Paige)가 1971년 학위논문에서 밝혀낸 것은 이 붕괴가 무작위가 아니라는 사실이다. 직교성 손실은 정확히 어떤 리츠값이 수렴하는 순간에 시작되며, 새 란초스 벡터가 이미 수렴한 리츠벡터 방향으로 오염된다.⁴

결과가 그 악명 높은 유령 고유값(ghost eigenvalue, 또는 spurious copy)이다. 중복도 1인 고유값이 $T_m$ 의 스펙트럼에 두 번, 세 번 복제되어 나타난다. 아무 대책 없이 돌린 뒤 “축퇴가 3중이네요”라고 보고하면 그건 물리가 아니라 반올림 오차다.⁵ 진짜 축퇴와 유령을 구분하려면 리츠벡터끼리의 내적을 직접 확인하거나, 아래 처방 중 하나를 써야 한다.

완전 재직교화: 매 스텝 $\mathbf{v}_{j+1}$ 을 앞의 모든 기저 벡터에 대해 다시 직교화. 확실하지만 비용이 $O(m^2 N)$ 으로 뛰고 벡터를 전부 저장해야 해서, 3항 점화식의 메모리 이점이 사라진다.
선택적 재직교화(Parlett–Scott): 잔차 추정으로 “이미 수렴한” 리츠벡터만 골라 그 방향으로만 직교화. 페이지 이론이 오염 방향을 정확히 지목해 주기 때문에 가능한 절약이다.
부분 재직교화(Simon): 직교성 손실량 자체를 점화식으로 추정해, $\sqrt{\varepsilon}$ 수준을 넘길 때만 개입한다.
아예 방치(Cullum–Willoughby): 재직교화를 포기하는 대신 $T_m$ 과 첫 행·열을 지운 $\hat T_m$ 의 고유값을 비교해 겹치는 것을 유령으로 판정해 버리는 필터. 메모리가 극단적으로 귀할 때의 선택.

5. 재시작·블록 — 실전 구현의 모습[편집]

부분공간 차원 $m$ 을 무한정 키울 수는 없으니 실무 구현은 재시작한다. 소렌슨(D. Sorensen, 1992)의 암시적 재시작 란초스(IRLM)는 $m$ 차원까지 확장한 뒤 원치 않는 리츠값들을 시프트로 삼아 암시적 QR 스텝을 걸어, 그 성분만 걸러낸 $k$ 차원 크리로프 부분공간으로 접어 넣는다. 재시작 벡터를 다시 고르는 게 아니라 “필터를 통과시킨다”는 발상이라 정보 손실이 적다. 이 구현체가 바로 **ARPACK**이고, MATLAB의 eigs와 SciPy의 eigsh가 부르는 것도 결국 이 코드다. 최근에는 구현이 더 단순한 thick-restart Lanczos(Wu–Simon)도 널리 쓰인다.

블록 란초스는 벡터 대신 $N \times p$ 블록을 밀어 넣어 부분공간을 한 번에 $p$ 차원씩 키운다. 축퇴(중복 고유값)를 단일 벡터 란초스가 원리적으로 한 번에 하나씩밖에 못 잡는 문제를 정면으로 해결하고, 행렬-벡터 곱이 행렬-행렬 곱(BLAS-3)이 되어 캐시 효율까지 좋아진다. NASTRAN을 비롯한 상용 구조해석 코드의 기본 고유해석기가 블록 란초스인 이유다.

비대칭 행렬로 가면 3항 점화식이 성립하지 않아 완전한 그람-슈미트가 필요해지는데, 그 일반화가 아놀디 알고리즘이다. 즉 란초스는 아놀디의 대칭 특수화이며, 대칭성이라는 공짜 선물 하나로 저장 비용이 $O(mN)$ 에서 $O(N)$ 으로 내려간 것이다.

6. 어디에 쓰이는가[편집]

모드 해석·좌굴: $K\boldsymbol{\phi} = \omega^2 M \boldsymbol{\phi}$ 에서 저주파 모드 수십~수백 개만 필요하다. 시프트-역변환 블록 란초스가 사실상 산업 표준이며, 부분구조법이나 축소차수모델의 모드 기저도 여기서 나온다.
상태밀도: 헤이독(Haydock) 재귀법은 란초스 계수 $\alpha_j, \beta_j$ 를 연분수에 그대로 꽂아 그린 함수의 대각 성분을 얻는다. 고유벡터를 하나도 계산하지 않고 스펙트럼 분포만 뽑는 고전 기법.
DMRG와 대형 배치상호작용: 힐베르트 공간 차원이 $10^{10}$ 을 넘어 행렬을 저장할 수 없고, $H\mathbf{v}$ 만 on-the-fly로 만드는 상황. 다만 이 동네의 기본값은 대각 우세를 활용하는 데이비드슨 알고리즘이고, 란초스는 대각 우세가 약하거나 스펙트럼 함수(동적 상관함수)가 필요할 때 쓰인다.
특이값 분해: Golub–Kahan 이중대각화가 사실상 $A^{\mathsf{T}}A$ 에 대한 란초스라, 대규모 저랭크 SVD와 주성분 분석의 뼈대가 된다.

7. 관련 문서[편집]

이 성질을 “matrix-free”라 부른다. 밴드 구조 계산의 해밀토니안이나 강성행렬처럼 조립하면 메모리가 터지는 행렬도, 곱셈 루틴만 짜면 고유값을 뽑을 수 있다. 물론 그 곱셈 루틴을 짜는 게 논문 한 편 분량인 경우가 흔하다. ↩
참고로 레일리 몫 $\rho(\mathbf{x}) = \mathbf{x}^{\mathsf{T}}A\mathbf{x}/\mathbf{x}^{\mathsf{T}}\mathbf{x}$ 의 관점에서 보면, 리츠값은 크리로프 부분공간 위에서 레일리 몫을 정류(stationary)시키는 값이다. 란초스·데이비드슨 알고리즘·아놀디의 공통 뼈대가 전부 이 레일리-리츠 사영이다. ↩
공짜는 아니다. $(A-\sigma I)^{-1}\mathbf{v}$ 를 만들려면 매 반복마다 선형계를 풀어야 한다. 즉 스파스 LU 분해 한 방을 미리 해두든가, 반복 솔버를 안쪽에 또 하나 넣든가(inner-outer) 해야 한다. “고유값 하나 구하려다 LU 분해 메모리에 사망”은 진동 해석 현장의 단골 사인(死因)이다. ↩
란초스는 1950년 논문 이후 20년 가까이 “수치적으로 불안정한 방법”으로 낙인찍혀 사실상 폐기됐다가, 페이지가 1971년에 “무너지긴 하는데 무너지는 방식이 정확히 정해져 있다”를 증명하면서 부활했다. 알고리즘 하나가 학위논문 한 편으로 되살아난 드문 사례. ↩
유령을 진짜 축퇴로 착각하고 학회 발표까지 간 사례가 수치해석 교과서마다 하나씩 실려 있다. 반대로 진짜 축퇴를 유령으로 오해해 지워버리는 실수도 똑같이 흔하다. 판정 기준을 코드에 박아두고 살자 — 검증 및 확인은 이런 데서 밥값을 한다. ↩