Cómo hacer referencia a submatrices dentro de una matriz

Question

Tengo una matriz nxn A donde n es una potencia de 2. La matriz A está dividida en 4 submatrices del mismo tamaño. ¿Cómo puedo hacer referencia a las matrices de las submatrices A11, A12, A21 y A22 en java? Estoy intentando un divide y vencerás algoritmo de multiplicación de matrices (Strassen)

  A11 | A12 
    A --> --------- 
      A21 | A22 

EDIT: La matriz se almacena como matriz de enteros: int [] [].

Answer 1

Bueno, si i y j son sus índices, entonces A11 se obtiene para i = 0 .. (n/2) -1, j = 0 .. (n/2) -1. Entonces, A12 es para i = 0 .. (n/2) -1 y j = n/2..n-1 y así sucesivamente.

Para 'referenciarlos', solo necesita un "i_min, i_max, j_min, j_max" y en lugar de ejecutar índices de 0 a n-1, ejecútelos de min a max.

Answer 2

Creo que tiene que decidir si copia los contenidos de cada submatriz cada vez o si realiza operaciones aritméticas en el direccionamiento. Sus preguntas implican que sus submatrices son contiguas en lugar de divididas (como en el cálculo de los contaminantes con menores y cofactores - http://mathworld.wolfram.com/Determinant.html). Como no ha dado una indicación de por qué desea hacer esto, qué resultados de rendimiento ya ha encontrado, y si hay recursión en matrices más pequeñas, creo que solo usted puede decidir sobre el equilibrio entre la simplicidad de la copia o la complejidad de direccionamiento recursivo. Pero esperaba que ya hubiera bibliotecas y verificaría http://commons.apache.org/math/.

Answer 3

Esta es una implementación de la Strassen algorithm for matrix multiplication

import java.io.*; 

public class MatrixMultiplication { 

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

    public MatrixMultiplication() throws IOException { 
     int n; 
     int[][] a, b; 

     System.out.print("Enter the number for rows/colums: "); 
     n = Integer.parseInt(br.readLine()); 

     a = new int[n][n]; 
     b = new int[n][n]; 

     System.out.print("\n\n\nEnter the values for the first matrix:\n\n"); 
     for (int i = 0; i < n; i++) { 
      for (int j = 0; j < n; j++) { 
       System.out.print("Enter the value for cell("+(i+1)+","+(j+1)+"): "); 
       a[i][j] = Integer.parseInt(br.readLine()); 
      } 
     } 
     System.out.print("\n\n\nEnter the values for the second matrix:\n"); 
     for (int i = 0; i < n; i++) { 
      for (int j = 0; j < n; j++) { 
       System.out.print("Enter the value for cell ("+(i+1)+","+(j+1)+"): "); 
       b[i][j] = Integer.parseInt(br.readLine()); 
      } 
     } 

     System.out.print("\n\nMatrix multiplication using standard method:\n"); 
     print(multiplyWithStandard(a, b)); 

     System.out.print("\n\nMatrix multiplication using Strassen method:\n"); 
     print(multiplyWithStandard(a, b)); 
    } 

    public int[][] multiplyWithStandard(int[][] a, int[][] b) { 
     int n = a.length; 
     int[][] c = new int[n][n]; 

     for (int i = 0; i < n; i++) { 
      for (int j = 0; j < n; j++) { 
       for (int k = 0; k < n; k++) { 
        c[i][j] += a[i][k] * b[k][j]; 
       } 
      } 
     } 
     return c; 
    } 

    public int[][] multiplyWithStrassen(int [][] A, int [][] B) { 
     int n = A.length; 
     int [][] result = new int[n][n]; 

     if (n == 1) { 
      result[0][0] = A[0][0] * B[0][0]; 
     } else if ((n%2 != 0) && (n != 1)) { 
      int[][] a1, b1, c1; 
      int n1 = n+1; 
      a1 = new int[n1][n1]; 
      b1 = new int[n1][n1]; 
      c1 = new int[n1][n1]; 

      for (int i = 0; i < n; i++) { 
       for (int j = 0; j < n; j++) { 
        a1[i][j] = A[i][j]; 
        b1[i][j] = B[i][j]; 
       } 
      } 
      c1 = multiplyWithStrassen(a1, b1); 
      for (int i = 0; i < n; i++) { 
       for (int j = 0; j < n; j++) { 
        result[i][j] = c1[i][j]; 
       } 
      } 
     } else { 
      int [][] A11 = new int[n/2][n/2]; 
      int [][] A12 = new int[n/2][n/2]; 
      int [][] A21 = new int[n/2][n/2]; 
      int [][] A22 = new int[n/2][n/2]; 

      int [][] B11 = new int[n/2][n/2]; 
      int [][] B12 = new int[n/2][n/2]; 
      int [][] B21 = new int[n/2][n/2]; 
      int [][] B22 = new int[n/2][n/2]; 

      divideArray(A, A11, 0 , 0); 
      divideArray(A, A12, 0 , n/2); 
      divideArray(A, A21, n/2, 0); 
      divideArray(A, A22, n/2, n/2); 

      divideArray(B, B11, 0 , 0); 
      divideArray(B, B12, 0 , n/2); 
      divideArray(B, B21, n/2, 0); 
      divideArray(B, B22, n/2, n/2); 

      int [][] M1 = multiplyWithStrassen(add(A11, A22), add(B11, B22)); 
      int [][] M2 = multiplyWithStrassen(add(A21, A22), B11); 
      int [][] M3 = multiplyWithStrassen(A11, subtract(B12, B22)); 
      int [][] M4 = multiplyWithStrassen(A22, subtract(B21, B11)); 
      int [][] M5 = multiplyWithStrassen(add(A11, A12), B22); 
      int [][] M6 = multiplyWithStrassen(subtract(A21, A11), add(B11, B12)); 
      int [][] M7 = multiplyWithStrassen(subtract(A12, A22), add(B21, B22)); 

      int [][] C11 = add(subtract(add(M1, M4), M5), M7); 
      int [][] C12 = add(M3, M5); 
      int [][] C21 = add(M2, M4); 
      int [][] C22 = add(subtract(add(M1, M3), M2), M6); 

      copyArray(C11, result, 0 , 0); 
      copyArray(C12, result, 0 , n/2); 
      copyArray(C21, result, n/2, 0); 
      copyArray(C22, result, n/2, n/2); 
     } 
     return result; 
    } 

    public int[][] add(int [][] A, int [][] B) { 
     int n = A.length; 
     int [][] result = new int[n][n]; 

     for (int i = 0; i < n; i++) { 
      for (int j = 0; j < n; j++) 
       result[i][j] = A[i][j] + B[i][j]; 
      } 
     return result; 
    } 

    public int[][] subtract(int [][] A, int [][] B) { 
     int n = A.length; 
     int [][] result = new int[n][n]; 

     for (int i = 0; i < n; i++) { 
      for (int j = 0; j < n; j++) { 
       result[i][j] = A[i][j] - B[i][j]; 
      } 
     }  
     return result; 
    } 

    private void divideArray(int[][] parent, int[][] child, int iB, int jB) { 
     for (int i1 = 0, i2 = iB; i1 < child.length; i1++, i2++) { 
      for (int j1 = 0, j2 = jB; j1 < child.length; j1++, j2++) { 
       child[i1][j1] = parent[i2][j2]; 
      } 
     } 
    } 

    private void copyArray(int[][] child, int[][] parent, int iB, int jB) { 
     for(int i1 = 0, i2 = iB; i1 < child.length; i1++, i2++) { 
      for(int j1 = 0, j2 = jB; j1 < child.length; j1++, j2++) { 
       parent[i2][j2] = child[i1][j1]; 
      } 
     } 
    } 

    public void print(int [][] array) { 
     int n = array.length; 

     System.out.println(); 
     for (int i = 0; i < n; i++) { 
      for (int j = 0; j < n; j++) { 
       System.out.print(array[i][j] + "\t"); 
      } 
      System.out.println(); 
     } 
     System.out.println(); 
    } 

    public static void main(String[] args) throws IOException { 
     new MatrixMultiplication(); 
    } 
}