Wie Referenz Sub-Matrizen innerhalb einer Matrix

Question

Ich habe eine nxn-Matrix A, wobei n eine Potenz von 2 ist. Die Matrix A ist in 4 gleich große Sub-Matrizen unterteilt. Wie kann ich Matrizen die Submatrizen A11, A12, A21 und A22 in Java referenzieren? Ich bin ein divide Versuch und Matrixmultiplikationsalgorithmus (Strassen)

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

EDIT zu erobern: Die Matrix als Integer-Array gespeichert ist: int [] [].

Answer 1

Nun, wenn i und j Ihre Indizes sind, dann wird A11 für i = 0 .. (n/2) -1, j = 0 .. (n/2) -1 erhalten. Dann ist A12 für i = 0 .. (n/2) -1 und j = n/2..n-1 und so weiter.

Um sie zu "referenzieren", brauchen Sie nur ein "i_min, i_max, j_min, j_max" und statt Indizes von 0 bis n-1 laufen sie von min bis max.

Answer 2

Ich denke, Sie müssen entscheiden, ob Sie den Inhalt jeder Submatrix jedes Mal kopieren oder die Adressierung arithmetisch machen wollen. Ihre Fragen implizieren, dass Ihre Submatrizen zusammenhängend und nicht getrennt sind (wie bei der Berechnung von Detrminanten mit Minderjährigen und Cofaktoren - http://mathworld.wolfram.com/Determinant.html). Da Sie keinen Hinweis darauf gegeben haben, warum Sie dies tun möchten, welche Leistungshits Sie bereits kennengelernt haben und ob es eine Rekursion zu kleineren Matrizen gibt, denke ich, dass nur Sie die Balance zwischen der Einfachheit des Kopierens oder der Komplexität finden können rekursiver Adressierung. Aber ich würde erwarten, dass es schon Bibliotheken gibt und ich würde http://commons.apache.org/math/ überprüfen.

Answer 3

Dies ist eine Implementierung des 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(); 
    } 
}