8

問題文：

カーネル正方行列の集合 = {K1, K2, .., Kn} があるとします。行列 A が与えられたとき、行列の掛け算の最小量を含む積を見つけます。これにより、A = Ki * Kj * ... * Kz が得られます。

例：

Say we have these two matrices in the set of Kernel matrices:
K1 = (1 2)    K2 = (5 6)
     (3 4)         (7 8)

Then we have a solution for A=K1*K2=(19 22) and also for B=K1*K1*K2=(105 122)
                                    (43 50)                         (229 266)

解決策を見つけるために使用できる既存の C または C++ ライブラリはありますか? そうでない場合、既知のアルゴリズム/ヒューリスティックはありますか?

PSこれは宿題の質問でも、理論的な質問でも、その他のトロッコ的なものでもありません。これは、私が本業で取り組んでいるサイド プロジェクトで解決しなければならない実際の問題です。

4

3 に答える 3

1

行列のトレースと行列式を見ることができます。積のトレースと行列式は、完全な乗算よりも効率的に計算できるため、組み合わせを効率的に除外するのに役立ちます。

http://en.wikipedia.org/wiki/Trace_(linear_algebra)#Trace_of_a_product http://en.wikipedia.org/wiki/Determinant#Multiplicativity_and_matrix_groups

于 2012-05-31T22:40:27.443 に答える
0

tr（A * B）がtr（A）* tr（B）と等しくないことを除いて、組み合わせを減らすためのトレースのアイデアは良いので、代わりに行列式を使用する必要がありますdet（A * B）= det（A） * det（B）。

カーネルにdet（Ki）= +/- 1 ..がない限り、det（M）の素因数分解は組み合わせを減らすのに役立つ可能性があります。

于 2012-06-05T22:59:37.573 に答える
0

あなたが欲しいのは、行列演算を行うためのツールだと思います。Eigenがあなたに合っているかもしれません。http://eigen.tuxfamily.org/index.php?title=Main_Page

于 2012-05-31T21:47:48.773 に答える