c++ - 如何将矩阵因式分解为核矩阵的乘积？

Question

问题陈述:

Say we have a set of kernel square matrices = {K1, K2, .., Kn}. Given a matrix A find the product involving the least amount of matrix multiplications which gives: 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++ 库可供我用来寻找解决方案？如果没有，是否有任何已知的算法/启发式方法？

附言这不是家庭作业问题或理论问题或其他一些麻烦的事情。这是我在日常工作中从事的副业项目需要解决的实际问题。

Answer 1

您可能会查看矩阵的迹和行列式。由于可以比完全乘法更有效地计算乘积的迹和行列式，因此它们可以帮助您有效地排除组合。

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