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

trace 减少组合的想法很好，除了 tr(A*B) 不等于 tr(A)*tr(B)，所以你必须使用行列式而不是 det(A*B)=det(A) *det(B)。

det(M) 的整数因式分解可能会帮助您减少组合，除非您的内核有一些 det(Ki)=+/-1...

于 2012-06-05T22:59:37.573 回答
0

我认为您想要的是进行矩阵运算的工具。本征可能适合你。http://eigen.tuxfamily.org/index.php?title=Main_Page

于 2012-05-31T21:47:48.773 回答