Dividir y vencer la multiplicación de matrices

Tengo problemas para dividir y conquistar la multiplicación de matrices. Por lo que entiendo, dividir las matrices de tamaño nxn en cuadrantes (cada cuadrante es n/2) y luego lo hace:Dividir y vencer la multiplicación de matrices

C11 = A11⋅ B11 + A12 ⋅ B21 
C12 = A11⋅ B12 + A12 ⋅ B22 
C21 = A21 ⋅ B11 + A22 ⋅ B21 
C22 = A21 ⋅ B12 + A22 ⋅ B22

Mi salida para dividir y conquistar es realmente grande y estoy teniendo problemas para averiguar resolver el problema ya que no soy muy bueno con la recursividad.

ejemplo de salida:

original Matrix A:

A x A

clásica:

44 3 35 15 
56 20 24 35 
32 0 32 12 
29 5 21 17

divide y vencerás:

992 24 632 408 
1600 272 720 1232 
512 0 512 384 
460 17 405 497

¿Podría alguien decirme qué estoy haciendo mal para dividir y conquistar? Todas mis matrices son int[][] y el método clásico es la multiplicación de matriz de bucle 3 tradicional

Fuente

2011-01-31 Raptrex

qué es lo que quiere hacer la multiplicación de matrices de esta manera? Si está interesado en el rendimiento en bruto, hay bibliotecas numéricas disponibles que estoy seguro serían más rápidas de lo que podría escribir por su cuenta en un tiempo razonable. Si estás interesado en aprender sobre computación numérica, comenzaría con el mosaico de bucles (Wikipedia tiene un artículo) en lugar de una solución recursiva. – Samsdram

es para la tarea. – Raptrex

Usted está llamando de forma recursiva divideAndConquer en el camino equivocado. Lo que hace tu función es cuadrar una matriz. Para que la multiplicación de la matriz de dividir y conquistar funcione, debe ser capaz de multiplicar dos matrices potencialmente diferentes juntas.

Debe ser algo como esto:

private static int[][] divideAndConquer(int[][] matrixA, int[][] matrixB){ 
    if (matrixA.length == 2){ 
     //calculate and return base case 
    } 
    else { 
     //make a11, b11, a12, b12 etc. by dividing a and b into quarters  
     int[][] c11 = addMatrix(divideAndConquer(a11,b11),divideAndConquer(a12,b21)); 
     int[][] c12 = addMatrix(divideAndConquer(a11,b12),divideAndConquer(a12,b22)); 
     int[][] c21 = addMatrix(divideAndConquer(a21,b11),divideAndConquer(a22,b21)); 
     int[][] c22 = addMatrix(divideAndConquer(a21,b12),divideAndConquer(a22,b22)); 
     //combine result quarters into one result matrix and return 
    } 
}

Fuente

2011-01-31 16:10:51

Puede encontrar el artículo de Wiki en Strassen's algorithm útil.

Fuente

2011-01-31 01:44:32

Voy a implementar el algoritmo Strassens a continuación, pero también necesito dividir y conquistar. – Raptrex

Algunos enfoques para tratar la depuración:

probar algunas matrices de prueba muy simples como entrada (por ejemplo, todos los ceros, con uno o unos pocos indicadores estratégicos). Puede ver un patrón en los "fallos" que le mostrará dónde están sus errores.
Asegúrate de que tu enfoque "clásico" te esté dando respuestas correctas. Para las pequeñas matrices, puede utilizar Woflram Alfa en línea para poner a prueba respuestas: http://www.wolframalpha.com/examples/Matrices.html
Para la recursividad de depuración: añadir printf() declaraciones en la entrada y salida de su función, incluyendo los argumentos de invocación. Ejecute su matriz de prueba, escriba la salida en un archivo de registro y abra el archivo de registro con un editor de texto. Pase por cada caso, escriba sus notas al costado en el editor y asegúrese de que esté funcionando correctamente en cada paso. Agregue más declaraciones printf() y vuelva a ejecutar si es necesario.

¡Buena suerte con la tarea!

Fuente

2011-01-31 02:42:18 payne

mi enfoque clásico me da las respuestas correctas. Trataré de hacer una matriz de todos los 1 en vez de 0 porque dudo que una matriz de 0 funcione, ya que agregar o multiplicar con 0 será 0. – Raptrex

Sí, una matriz de todos los ceros te dará cero. Pero agregue algunos PUNTOS estratégicos (como todos en una columna, fila o diagonal) le darán mejores resultados. – payne

¿Podría alguien decirme qué estoy haciendo mal para dividir y conquistar?

Sí:

int[][] a = divideAndConquer(topLeft); 
    int[][] b = divideAndConquer(topRight); 
    int[][] c = divideAndConquer(bottomLeft); 
    int[][] d = divideAndConquer(bottomRight); 

    int[][] c11 = addMatrix(classical(a,a),classical(b,c)); 
    int[][] c12 = addMatrix(classical(a,b),classical(b,d)); 
    int[][] c21 = addMatrix(classical(c,a),classical(d,c)); 
    int[][] c22 = addMatrix(classical(c,b),classical(d,d));

Está pasando por una etapa extra de multiplicación aquí: usted no debe estar llamando tanto divideAndConquer() y classical().

Lo que está haciendo es efectivamente:

C11 = (A11^2)⋅(B11^2) + (A12^2)⋅(B21^2) 
C12 = (A11^2)⋅(B12^2) + (A12^2)⋅(B22^2) 
C21 = (A21^2)⋅(B11^2) + (A22^2)⋅(B21^2) 
C22 = (A21^2)⋅(B12^2) + (A22^2)⋅(B22^2)

cual no es correcto.

En primer lugar, eliminar los divideAndConquer() llamadas, y reemplazar a/b/c/d para el topLeft/topright/etc. Vea si le da los resultados adecuados.
Su método divideAndConquer() necesita un par de parámetros de entrada, por lo que puede usar A * B. Una vez que funcione, deshágase de las llamadas al classical() y use divideAndConquer(). (O guardarlos para matrices que no son un múltiplo de 2 en longitud.)

Fuente

2011-01-31 13:34:56

Dividir y vencer la multiplicación de matrices

Respuesta

Cuestiones relacionadas