Block_Lanczos_algorithm
でコンピュータサイエンス、ブロックランチョスアルゴリズムがあるアルゴリズムの発見のための零空間の行列をかけ有限体、長い、細い行列によってのみ行列の乗算を使用して。このような行列は、有限体エントリのタプルのベクトルと見なされるため、アルゴリズムの説明では「ベクトル」と呼ばれる傾向が
ブロックランチョスアルゴリズムは、二次ふるい法や数体ふるい法などの整数因数分解アルゴリズムの最終段階であるヌルスペースを見つけるために知られている最も効率的な方法の1つであり、その開発は完全にこのアプリケーションによって推進されています。
並列化の問題
アルゴリズムは本質的に並列ではありません。もちろん、行列と「ベクトル」の乗算を分散することは可能ですが、各反復の最後にベクトル全体を結合ステップで使用できる必要があるため、計算に関与するすべてのマシンは次のようになります。同じ高速ネットワーク上。特に、ベクトルを広げたり、ベクトルのスライスを異なる独立したマシンに配布したりすることはできません。
ブロックヴィーデマンアルゴリズムは、そのアルゴリズムにシステムが終わりに最終段階まで独立して実行することができるので、いくつかのシステム全体の行列を保持するために、それぞれ十分な大きさが利用可能である状況において、より有用です。
参考文献
この線形代数関連
“