ブロックランチョスアルゴリズム

コンピュータサイエンスにおいて、ブロック ランチョス アルゴリズムは、行列と細長い行列の乗算のみを使用して、有限体上の行列の零空間を見つけるアルゴリズムです。このような行列は、有限体エントリの組のベクトルと見なされるため、アルゴリズムの説明では「ベクトル」と呼ばれる傾向があります。

ブロック ランチョス アルゴリズムは、二次ふるいや数体ふるいなどの整数因数分解アルゴリズムの最終段階であるヌル空間を見つけるための最も効率的な方法の 1 つとして知られており、その開発は完全にこのアプリケーションによって推進されてきました。

これは、大規模な疎行列の固有値を求めるランチョスアルゴリズムに基づいており、非常によく似ています。 ^[1]

このアルゴリズムは本質的に並列ではありません。行列と「ベクトル」の乗算を分散させることはもちろん可能ですが、各反復の最後での組み合わせステップにベクトル全体を使用できる必要があるため、計算に関係するすべてのマシンが同じ高速ネットワーク上にある必要があります。特に、ベクトルを広げて、ベクトルのスライスを異なる独立したマシンに分散させることはできません。

ブロックヴィーデマン アルゴリズムは、各システムが最終段階まで独立して実行できるため、マトリックス全体を保持できる大きさの複数のシステムが利用できるコンテキストでより便利です。