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の三重対角実対称行列T=VAVを出力する。m=nの場合、Vはユニタリであり、A=VTVとなる。Lanczos反復は数値的不安定性を起こしやすいため、非厳密な算術で実行する場合、結果の妥当性を保証するために追加の対策（後続の節で概説）を講じるべきである。
このアルゴリズムは、Krylov部分空間の基底を形成する正規直交ベクトルv1、v2、...、vmの列を生成することによって進行する。ノルム1の任意のベクトルv1から開始し、各ステップで行列Aを適用し、前のベクトルに対して直交化し、正規化することによって新しいベクトルを計算する。係数αjとβjは、三重対角行列Tの対角成分と非対角成分を形成し、その固有値はAの固有値を近似する。
数値的安定性と再直交化
元のLanczosアルゴリズムは、浮動小数点の丸め誤差による直交性の喪失に悩まされ、スプリアス固有値や不正確な固有ベクトルを引き起こした。1970年のOjalvoとNewmanによる安定化は、完全な再直交化を導入した。すなわち、新しく生成された各ベクトルは、以前に生成されたすべてのベクトルに対して直交化される。これによりLanczosベクトルが精製され、数値的安定性が回復するが、計算オーバーヘッドの増加という代償を伴う。1970年代初頭のPaigeの誤差解析は、丸め誤差の影響に関する理論的限界を提供し、再直交化アプローチを正当化した。
機械学習への応用
機械学習において、Lanczosアルゴリズムは、PCAにおける共分散行列の最大固有値の計算やスペクトルクラスタリングなど、大規模な固有値問題に使用される。また、深層学習では、ニューラルネットワークのヘッセ行列スペクトルを近似するために用いられ、最適化や汎化解析に役立つ。このアルゴリズムは行列とベクトルの積のみを必要とするため、明示的な行列の格納が不可能な大規模言語モデルや生成AIシステムで生じる非常に大規模な行列に適している。
関連手法と拡張
Lanczosアルゴリズムは、線形方程式を解くための共役勾配法と密接に関連しており、両者ともKrylov部分空間を構築する。また、非エルミート行列に対するArnoldi反復とも関連している。ブロックLanczosアルゴリズムなどの変種は複数の開始ベクトルを扱い、暗黙的再起動Lanczos法（ARPACKで使用）は収束とメモリ使用量を改善する。これらの拡張はLAPACKやSciPyなどの数値ライブラリに実装されており、このアルゴリズムを科学計算における標準的なツールにしている。
歴史的影響と現代での使用
安定化以来、Lanczosアルゴリズムは構造工学、量子化学、信号処理に応用されてきた。人工知能の文脈では、データ分析やモデル圧縮に使用される多くのスペクトル法の基盤となっている。このアルゴリズムの効率性と堅牢性は、数値線形代数の要となっており、現代のハードウェア、すなわちGPUや専用AIアクセラレータ向けの安定性と並列化の改善に関する研究が進行中である。
関連項目
- 冪乗法
- 固有値分解
- Krylov部分空間
- 共役勾配法