計算効率：スパース対フル

Question

行列がほぼ満たされている場合、それをスパースに格納すると計算時間が長くなることが分かりました。

疎な形で完全な行列を保存するのは簡単ですが、この事実の背後にある理由を知りたいだけです。

私の推測では、疎なインデックスはコンピューティング時間の主な要因になると私は推測しています。他の優雅な考え？

Answer 1

ほとんど完全なスパース行列が、フル行列を使用するよりも計算上高価ないくつかの理由があります。あなたが指摘したように、最も一般的なスパース行列については、MatlabがCompressed Row Storageスキームを使用していると考えられます。

プロセッサのベクトル化とパイプライン化によるものです。完全に格納されたマトリックスの場合、データはきちんとした線形フォーマットであるため、操作は容易にベクトル化できます。 CRSのような記憶スキームの場合、特にMatrix * Vector演算（これは、反復ソルバーを使用して方程式系を解くときなど）で使用される傾向があります。 CRS方式では、行列の行全体を動かすことが素早く素早くプロセッサに伝えることができますが、行列が乗算されるベクトルから引き出された要素は飛びます。

Answer 2

以下密行列考慮してください。私は連続したブロックに格納した場合

1 2 3 
4 5 6 
7 8 9 

を：

1 2 3 4 5 6 7 8 9 

I直接一部で行と列の番号を与えられた行列の要素にアクセスすることができます基本算術。

は今、この疎行列を考えてみます。

それは今

1 2 3 

になった。しかし、これは明らかに十分な情報ではないので、効率的にこの行列を格納するために

1 0 0 
0 0 2 
0 3 0 

、私は非ゼロ要素を破棄行列ベクトル乗算のような演算を行う！したがって、行列から要素を抽出するには、additional informationを追加する必要があります。行列 の構造を保つために

しかし、あなたはそれに関係なく使用する記憶法の見ることができ、我々は

1. に必要な要素にアクセスするために余計な作業を行う
2. 店の詳細

   このように、ストレージの利点は、行列の構造を保存するために保存する余分な情報を補うために、行列に十分なゼロがある場合にのみ発生します。たとえば、Yale formatでは、非ゼロ（NNZ）値の数が(m(n − 1) − 1)/2より小さい場合は、m =行数、n =列数の場合にのみメモリに保存されます。