c++ - matriz - factorizacion pa=lu matlab

¿Cómo factorizar una matriz para un producto de matrices de kernel?

Question

Planteamiento del problema:

Digamos que tenemos un conjunto de matrices cuadradas de kernel = {K1, K2, .., Kn}. Dada una matriz A, encuentre el producto que involucre la menor cantidad de multiplicaciones de matrices que da: A = Ki * Kj * ... * Kz

Ejemplo:

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)

¿Existe alguna biblioteca C o C ++ que pueda usar para encontrar la solución? Si no, ¿hay algún algoritmo / heurística conocido?

PS: esta no es una pregunta de tarea o una pregunta teórica o alguna otra cosa del trolly. Este es un problema real que necesito resolver para un proyecto paralelo en el que estoy trabajando en mi trabajo diario.

Answer 1

Creo que lo que quieres es una herramienta para hacer operaciones matriciales. Eigen puede ser adecuado para usted. http://eigen.tuxfamily.org/index.php?title=Main_Page

Answer 2

Puede ver el rastro y el determinante de la matriz. Dado que la traza y el determinante de un producto se pueden calcular de manera más eficiente que una multiplicación completa, pueden ayudarlo a descartar combinaciones de manera eficiente.

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

Answer 3

Creo que este artículo aborda su problema: http://en.wikipedia.org/wiki/Matrix_chain_multiplication

Answer 4

La idea de trazar para combinaciones reductoras es buena, excepto que tr (A * B) no es igual a tr (A) * tr (B), por lo que debe usar determinante en lugar det (A * B) = det (A) * det (B).

Una factorización entera de det (M) puede ayudarte a reducir el combinatorio, a menos que tu kernel tenga algo det (Ki) = + / - 1 ...