Mathematics

計算について

スパース演算の計算の複雑さは、行列の中の非ゼロ要素の数nnzに比例します。計算の複雑さは、行列の行サイズmと列サイズnに線形に依存します。しかし、ゼロ要素数と非ゼロ要素数の和、すなわち、全要素数m*nには独立です。

スパース線形方程式の解のようなかなり込み入った演算の複雑さは、前の節で議論したorderingやfill-inのようなファクタを含んでいます。しかし、一般に、スパース行列演算に必要な計算時間は、非ゼロの量に対して働きかける演算回数に比例します。これが、"時間がフロプスに比例する"法則です。

スパース行列の演算

標準数学演算