¿Cuál es el mejor algoritmo de multiplicación de matrices? ¿Qué significa 'lo mejor' para mí? Significa el más rápido y listo para las máquinas de hoy.¿Cuál es el mejor algoritmo de multiplicación de matrices?
Por favor, proporcione enlaces a pseudocódigo si puede.
BLAS es la mejor biblioteca de multiplicación de matrices eficiente lista para usar. Hay muchas implementaciones diferentes. He aquí un punto de referencia que hice para algunas implementaciones en un MacBook Pro con doble núcleo Intel Core 2 Duo a 2,66 GHz:
También existen otras implementaciones comerciales que no he probado aquí:
Hay un algoritmo llamado Cannon's algorithm un algoritmo de multiplicación de matriz distribuida. Más here
¿Por qué pseudocódigo? ¿Por qué implementarlo tú mismo? Si la velocidad es su problema, hay algoritmos altamente optimizados disponibles que incluyen optimizaciones para conjuntos de instrucciones específicos (por ej. SIMD), implementarlos por sí solo no ofrece ningún beneficio real (aparte de tal vez aprender),
Eche un vistazo a BLAS implementaciones, como:
También vería cublas si tiene una tarjeta gráfica de gran tamaño disponible. (También hay envoltorios en muchos idiomas si c no es lo suyo). –
el mejor algoritmo de multiplicación de matrices es la que alguien con conocimientos de arquitectura detallada ya ha sintonizado a mano para su objetivo pl atform.
Hay muchas buenas bibliotecas que ofrecen implementaciones sintetizadas de multiplicación de matriz. Usa uno de ellos.
Probablemente haya otros mejores, pero estos son los que tengo a la cabeza (mejor que el algoritmo de complejidad cúbica estándar).
Strassen's - O (N^2,8)
Coppersmith Winograd - O (N^2.376)
Estos tienen una mejor complejidad asintótica que el algoritmo "estándar" O (N^3), pero la constante es (al menos para Coppersmith-Winograd) es prohibitivamente grande para matrices de tamaño moderado. Ver esta publicación en mathoverflow: http://mathoverflow.net/questions/1743/what-is-the-constant-of-the-coppersmith-winograd-matrix-multiplication-algorithm – celion
Excelente punto. Eso me hace preguntarme si las bibliotecas de matriz mencionadas por Jim adaptan el algoritmo basado en el tamaño de entrada. –
Según tengo entendido, puedes dividir la multiplicación en bloques, de manera que todos los datos en los que trabajes encajen en la memoria caché, lo que te da una aceleración constante buena. ATLAS realmente se mide a sí mismo para ajustar sus parámetros. – celion
No hay "mejor algoritmo" para todas las matrices de todas las CPU modernas.
Necesitará investigar un poco sobre los muchos métodos disponibles, y luego encontrará la solución más adecuada para los problemas particulares que está calculando en el hardware particular con el que está tratando.
Por ejemplo, la forma "más rápida" en su plataforma de hardware puede ser usar un algoritmo "lento" pero solicite a su GPU que lo aplique a 256 matrices en paralelo. O usar un algoritmo "rápido" de propósito general (mxn) puede producir resultados mucho más lentos que usar un multiplicador de matriz optimizado de 3x3. Si realmente quiere que sea rápido, puede considerar bajar al nivel básico para asegurarse de que hace el mejor uso de las funciones específicas de la CPU, como instrucciones SIMD, predicción de bifurcación y coherencia de caché, a expensas de la portabilidad.
Depende del tamaño de la matriz, si es escasa o no.
Para matrices densas pequeñas a medianas, creo que alguna variación en la O "ingenua" (N^3) algoritmo es una victoria, si se presta atención a la caché de coherencia y el uso de la plataforma de instrucciones vectoriales
La distribución de datos es importante: para los casos en que el diseño de matriz estándar es poco amigable (por ejemplo, column-major * row-major), debe probar la descomposición binaria de la multiplicación de matrices, incluso si no use los algoritmos de Strassen u otros algoritmos "rápidos", este orden de operaciones puede producir un algoritmo "caché ajeno" que automáticamente hace un buen uso de cada nivel de caché.Si tiene el lujo de reorganizar sus matrices, puede intentar combinar esto con un orden intercalado de bits (o "orden Z") de elementos de datos.
Finalmente, recuerde: la optimización prematura es la raíz de todo mal. Y cuando no lo es prematuro más, siempre perfil & referencia antes, durante y después de la optimización ....
Aquí es algoritmos curso del MIT y la conferencia de multiplicación de matrices
matriz multiplicación - O (n^3)
de Strassen algoritmo - O (n^2,8) http://en.wikipedia.org/wiki/Strassen_algorithm
Coppersmith-Winograd - O (n^2.376) http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm
¿Cómo multiplicar una matriz a mano? –
¿Desea uno para matrices generales, o tiene alguna restricción útil en las matrices, como triangular superior o diagonal? –
¿Esto es para un programa, o algo así como el trabajo escolar? La multiplicación de matrices es bastante simple; 1) compruebe que las dimensiones coincidan (por ejemplo, 3x3 * 3x1 y no 3x3 * 1x3), 2) multiplique los campos correspondientes y añádalos para llegar al campo final. http://en.wikipedia.org/wiki/Matrix_multiplication – Eaglebird