Lanczos 알고리즘은 Cornelius Lanczos가 고안한 반복적 방법으로, 거듭제곱 방법을 적응시켜 n×n 에르미트 행렬의 m개의 "가장 유용한"(극단적으로 높거나 낮은 쪽으로 치우친) 고유값과 고유벡터를 찾는 데 사용된다. 여기서 m은 종종 n보다 훨씬 작지만 반드시 그런 것은 아니다. 원리적으로 계산 효율이 높지만, 초기에 공식화된 방법은 수치적 불안정성 때문에 실용적이지 못했다. 1970년, Ojalvo와 Newman은 이 방법을 수치적으로 안정적으로 만드는 방법을 보여주었고, 동적 하중을 받는 매우 큰 공학 구조물의 해석에 적용했다. 이는 Lanczos 벡터를 정제하는 방법(즉, 새로 생성된 각 벡터를 이전에 생성된 모든 벡터와 반복적으로 재직교화하는 방법)을 사용하여 임의의 정확도로 달성되었으며, 이를 수행하지 않으면 가장 낮은 고유 진동수와 관련된 벡터에 의해 심하게 오염된 일련의 벡터가 생성되었다.
이 저자들은 원래 연구에서 시작 벡터를 선택하는 방법(즉, 난수 생성기를 사용하여 시작 벡터의 각 요소를 선택)도 제안했으며, 감소된 벡터 수 m을 결정하는 경험적 방법(즉, 원하는 정확한 고유값 수의 약 1.5배로 선택해야 함)을 제안했다. 그 직후 Paige가 이들의 연구를 이어받아 오차 분석을 제공했다. 1988년, Ojalvo는 이 알고리즘의 더 상세한 역사와 효율적인 고유값 오차 검정을 제시했다.
알고리즘 개요
크기가 n×n인 에르미트 행렬 A를 입력하고, 선택적으로 반복 횟수 m(기본값은 m=n)을 입력한다. 엄밀히 말하면, 알고리즘은 명시적 행렬에 접근할 필요가 없으며, 행렬과 임의의 벡터의 곱을 계산하는 함수 v↦Av만 필요하다. 이 함수는 최대 m번 호출된다. 직교 정규 열을 가진 n×m 행렬 V와 크기가 m×m인 3중 대각 실대칭 행렬 T=VAV를 출력한다. m=n이면 V는 유니타리 행렬이고 A=VTV이다. Lanczos 반복은 수치적 불안정성에 취약하므로, 비정확 산술로 실행될 때는 결과의 유효성을 보장하기 위해 추가 조치(이후 섹션에서 설명)를 취해야 한다.
알고리즘은 Krylov 부분공간의 기저를 형성하는 직교 정규 벡터 v1, v2, ..., vm의 수열을 생성하는 방식으로 진행된다. 노름이 1인 임의의 벡터 v1에서 시작하여, 각 단계에서 행렬 A를 적용하고 이전 벡터에 대해 직교화한 후 정규화하여 새 벡터를 계산한다. 계수 αj와 βj는 3중 대각 행렬 T의 대각 및 부대각 요소를 형성하며, 그 고유값은 A의 고유값을 근사한다.
수치적 안정성과 재직교화
원래 Lanczos 알고리즘은 부동소수점 반올림으로 인한 직교성 상실로 인해 가짜 고유값과 부정확한 고유벡터가 발생했다. 1970년 Ojalvo와 Newman의 안정화는 완전 재직교화를 도입했다. 즉, 새로 생성된 각 벡터를 이전에 생성된 모든 벡터에 대해 직교화하는 것이다. 이는 Lanczos 벡터를 정제하고 수치적 안정성을 회복하지만, 계산 오버헤드가 증가하는 비용이 따른다. 1970년대 초 Paige의 오차 분석은 반올림의 영향에 대한 이론적 경계를 제공하고 재직교화 접근법을 정당화했다.
기계 학습에서의 응용
기계 학습에서 Lanczos 알고리즘은 대규모 고유값 문제, 예를 들어 PCA에서 공분산 행렬의 최상위 고유값 계산이나 스펙트럼 클러스터링에 사용된다. 또한 심층 학습에서 신경망의 헤시안 스펙트럼을 근사하는 데 사용되어 최적화 및 일반화 분석에 도움이 된다. 이 알고리즘은 행렬-벡터 곱만으로 작동할 수 있으므로, 명시적 행렬 저장이 불가능한 대규모 언어 모델 및 생성형 AI 시스템에서 발생하는 매우 큰 행렬에 적합하다.
관련 방법 및 확장
Lanczos 알고리즘은 선형 시스템을 푸는 켤레 기울기 방법과 밀접한 관련이 있으며, 둘 다 Krylov 부분공간을 구축한다. 또한 비에르미트 행렬에 대한 Arnoldi 반복과도 연결된다. 블록 Lanczos 알고리즘과 같은 변형은 여러 시작 벡터를 처리하며, 암시적 재시작 Lanczos 방법(ARPACK에서 사용)은 수렴과 메모리 사용을 개선한다. 이러한 확장은 LAPACK 및 SciPy와 같은 수치 라이브러리에 구현되어 있어, 이 알고리즘은 과학 계산의 표준 도구가 되었다.
역사적 영향과 현대적 사용
안정화 이후, Lanczos 알고리즘은 구조 공학, 양자 화학, 신호 처리에 적용되었다. 인공지능의 맥락에서, 이 알고리즘은 데이터 분석과 모델 압축에 사용되는 많은 스펙트럼 방법의 기반이 된다. 이 알고리즘의 효율성과 견고성은 수치 선형 대수의 초석이 되었으며, GPU 및 전문 AI 가속기와 같은 현대 하드웨어를 위한 안정성 및 병렬화 개선에 대한 지속적인 연구가 진행 중이다.
같이 보기
- 거듭제곱 반복
- 고유값 분해
- Krylov 부분공간
- 켤레 기울기