私が書いている論文では、次元nの密なベクトルを乗算するnxn行列を利用しています。自然な形では、この行列はO（n ^ 2）の空間の複雑さを持ち、乗算には時間O（n ^ 2）がかかります。
ただし、行列は対称であり、対角線に沿ってゼロ値を持つことが知られています。行列も非常にスパースです。非対角エントリの大部分はゼロです。
スパース対称行列表現を使用してO（nlogn）、またはスパース性が高い場合はO（n）に近づくアルゴリズム/紙/データ構造に誰かが私をリンクできますか？
2 に答える
1
TimDavisによるcsparseライブラリを見てみます。スパース行列アルゴリズムの全範囲を説明する対応する本もあります。
スパースの場合、A*x操作を複雑に実行することができますO(|A|)。つまり、行列内の非ゼロ要素の数が線形になります。
于 2011-09-24T10:11:07.387 に答える
1
この種の並列アルゴリズムに興味がありますか http://www.cs.cmu.edu/~scandal/cacm/node9.html
于 2011-09-13T05:45:09.963 に答える