algorithm - スパース行列を効率的に解く

Question

予備行列を解くには、

一般に、マトリックスはどのくらいの大きさでなければなりませんか（経験則として）

学群降下のような方法がブルート フォース ソルバー (スパース性を利用しない) よりも高速になるには?

Answer 1

これは、行列のサイズだけでなく、それらがどの程度疎であるか、どのような疎構造を持っているかにも依存します。明らかに、三重対角システムは、行列全体にランダムに分散された同じ数のゼロ以外のエントリを持つシステムよりもはるかに高速に解くことができます。

High-Performance Mark が指摘したように、CG は疎行列だけでなく密行列にも機能するため、質問したい質問は、「行列を処理することでソルバーが利益を得る前に、行列がどれくらい大きく、どれだけ疎である必要があるか」という線に沿ったものです。たまたま多くのゼロを含む密行列ではなく、疎行列として」.

これに対する答えは、前述したように、疎構造に依存します。最初の推測では、10% 埋まっている特別な構造のないマトリックスでは、マトリックスがキャッシュをいっぱいにするまで高密度メソッドを使用します (最新のコモディティ ハードウェアでは、約 1000 x 1000 になります)。行列が大幅にまばらであるか、操作を容易にする特別な構造 (ゼロ以外のデータの密集したブロック、またはバンド構造など) を持っている場合、そのしきい値ははるかに小さくなります。

あなたが取り組んでいる特定の問題について、より詳しい情報を教えていただけますか?

Answer 2

共役勾配ソルバーと「ブルートフォース」ソルバーの間の二分法が役立つかどうかはわかりません。たとえば、CG は密行列と疎行列の両方に適用できます。この本が役に立つかもしれません。