language-agnostic - 帯対角行列を解くための最適なアルゴリズムは何ですか?

Question

五角行列を解く最善の方法を見つけようとしています。ガウス消去法より速いものはありますか?

Answer 1

行列がエルミート正定値であるかどうかに応じて、行列の LU またはコレスキー分解を実行してから、因子で逆置換を行う必要があります。これは本質的には単なるガウス消去法ですが、より優れた数値特性を持つ傾向があります。LAPACK を使用することをお勧めします。これらの実装は、最も高速で最も堅牢な傾向があるためです。_GBSVルーチンを見てください。空白は、数値の種類に応じて、s、d、c、z のいずれかです。

編集：ファクター/ソルブ（ガウス消去）法よりも高速なアルゴリズムがあるかどうかを尋ねている場合は、ありません。帯行列の特殊な因数分解ルーチンは、約 4n*k^2 操作 (k は帯域幅) を要しますが、後方置換は約 6*n*k 操作を要します。したがって、固定帯域幅の場合、n の線形時間よりも優れた処理を行うことはできません。