행렬 내에서 부분 행렬을 참조하는 방법

Question

저는 nxn 행렬 A를 가지고 있습니다. 여기서 n은 2의 거듭 제곱입니다. 행렬 A는 4 개의 동일한 크기의 부분 행렬로 나뉩니다. 자바에서 서브 매트릭스 A11, A12, A21 및 A22를 어떻게 참조 할 수 있습니까? I은 분열을 시도하고 행렬 곱셈 알고리즘 (쉬트 라쎈)

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

EDIT 정복하고 : 매트릭스 정수 어레이로 저장된다 값 int [] [].

Answer 1

음, i 및 j이 색인 인 경우 i = 0 .. (n/2) -1, j = 0 .. (n/2) -1에 대해 A11이 얻어집니다. 그러면 A12는 i = 0 .. (n/2) -1 및 j = n/2..n-1 등입니다.

이들을 '참조'하려면 'i_min, i_max, j_min, j_max'가 필요하며 0에서 n-1까지 인덱스를 실행하는 대신 min에서 max까지 실행하십시오.

Answer 2

매번 서브 매트릭스의 내용을 복사할지 또는 어드레싱을 계산할지 결정해야한다고 생각합니다. 귀하의 질문은 귀하의 부분 집합이 쪼개지 않고 연속적이라는 것을 의미합니다 (미성년자 및 보조자와의 차이를 계산할 때 - http://mathworld.wolfram.com/Determinant.html처럼). 당신이 이것을하고 싶은 이유, 이미 겪었던 성능의 히트가 있는지, 그리고 더 작은 매트릭스에 대한 재귀가 있는지 여부를 알려주지 않았기 때문에 복사의 단순성과 복잡성 사이의 균형을 결정할 수 있다고 생각합니다 재귀 적 어드레싱 그러나 이미 도서관이 있기를 기대하며 http://commons.apache.org/math/을 확인합니다.

Answer 3

이것은 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(); 
    } 
}