カスタム化された行列ライブラリに大きく依存しているコードを最適化しています（これはどこにでもあるのでプロジェクトから除外されません。 ...）多くの計算が10〜20行と列の行列で行われ、多くの計算が、私は多くの場合、Aが希薄であることに気づき、私はこの事実を利用したいと思いスパース行列を使用した2次形式の行列乗算のアルゴリズム
C = A*B*A'
のような二次形式が含まれます。だから私はこのケースを処理するアルゴリズムを探しています。数値的安定性が重要です。私が使用できるものはありますか？ （私はライブラリを書いていないので、考慮すべき落とし穴があるかどうかはわかりません）
単純なO（n^3）乗法は、数値的な安定性が必要でマトリックスがあまり大きくないので、StrassenのアルゴリズムとCoppersmith-Winogradのアルゴリズムは、私が探しているアルゴリズムではないと思います。代わりに、それはちょうどAのゼロをチェックできる方法での二次形式の乗算です。
ありがとうございました！
this紙が存在し、高速スパース行列乗算を扱います。開発されたアルゴリズムは、疎行列を2つの部分に分割します。稠密と疎で、高速乗法アルゴリズムを適用します。だから私にとっては、Strassenに関して言及したように、行列のサイズに依存しないように見えますが、それはまばらであるという事実です。
密行列よりも凝縮された形で疎行列を実装する方法があります。次のように私はそれを行う1つの方法である：
[0 0 0 0 0]
[0 1 2 0 9]
[0 0 0 2 0]
[0 1 0 0 0]
は、非ゼロ要素
typedef struct {
int row;
int col;
double entry;
} Element;
typedef SparseMatrix Element*;
の線形アレイはそうマトリックスは現在代わりOのO（N）（の空間複雑性を有するとなりますA^Bの場合、AとBが行列である場合、一致する要素（つまり、a-> row == b-> col & & a-> col == b->行）、おそらくいくつか一緒に追加する（内積）。 このアルゴリズムは、O（n^3）ではなくO（n^2）の複雑さです。これは、ゼロになる内積を取るという些細な操作をスキップすることができるからです。
スペースは、要素数（n）ではなく、非ゼロ要素の数に比例します。 – vitaut
「クローズ」に投票した人は誰ですか？私はこの質問が完全に有効であり、プログラミングに関連していることを知ります – nacho4d
私はあなたが小さな行列でスパース性を利用することから多くの利益を得ることは確かではありません。 –