Problemstellung:
Nehmen wir an, wir haben eine Menge von Kernquadratmatrizen = {K1, K2, .., Kn}. Gegeben eine Matrix A finde das Produkt mit der geringsten Menge an Matrix Multiplikationen, die ergeben: A = Ki * Kj * ... * Kz
Beispiel:
%Vor%Gibt es eine vorhandene C- oder C ++ - Bibliothek, mit der ich die Lösung finden kann? Wenn nicht, gibt es bekannte Algorithmen / Heuristiken?
P.S. Dies ist keine Hausaufgabe oder eine theoretische Frage oder eine andere Trolly-Sache. Dies ist ein echtes Problem, das ich für ein Nebenprojekt lösen muss, an dem ich gerade arbeite.
Sie können sich die Spur und Determinante der Matrix ansehen. Da Trace und Determinante eines Produkts effizienter berechnet werden können als eine vollständige Multiplikation, können sie Ihnen dabei helfen, Kombinationen effizient auszuschließen.
Ссылка http://en.wikipedia.org/wiki/Determinant#Multiplicativity_and_matrix_groups
Die Idee von trace zur Reduktion von Kombinationen ist gut, außer dass tr (A * B) nicht gleich tr (A) * tr (B) ist, also muss man Determinante anstelle von det (A * B) = det verwenden (A) * det (B).
Eine ganzzahlige Faktorisierung von det (M) kann Ihnen helfen, das Kombinatorische zu reduzieren, es sei denn, Ihr Kernel hat det (Ki) = + / - 1 ...
Tags und Links math c++ linear-algebra matrix