Как ссылаться на подматрицы в матрице

Question

У меня есть nxn матрица A, где n - степень 2. Матрица A разделена на 4 субматрицы одинакового размера. Как я могу ссылаться на матрицы подматриц A11, A12, A21 и A22 в Java? Я пытаюсь использовать алгоритм умножения матрицы «разделяй и властвуй» (Штрассен)

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

РЕДАКТИРОВАТЬ: матрица сохраняется в виде целочисленного массива: int [] [].

Answer 1

Ну, если i и j - ваши индексы, то A11 получается для i = 0 .. (n / 2) -1, j = 0 .. (n / 2) -1.Тогда A12 для i = 0 .. (n / 2) -1, j = n / 2..n-1 и т. Д., i_max, j_min, j_max "и вместо запуска индексов от 0 до n-1, запустите их от мин до макс.

Answer 2

Это реализация алгоритма Штрассена для умножения матриц

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

Answer 3

Я думаю, вы должны решить, копировать ли содержимое каждой подматрицы каждый раз или выполнять арифметику с адресацией. Ваши вопросы подразумевают, что ваши подматрицы являются смежными, а не расщепленными (как при расчете детерминантов с минорами и кофакторами - http://mathworld.wolfram.com/Determinant.html). Поскольку вы не указали, почему вы хотите это сделать, какие показатели производительности вы уже встречали и есть ли рекурсия к меньшим матрицам, я думаю, что только вы можете выбрать баланс между простотой копирования или сложностью рекурсивной адресации. Но я ожидаю, что библиотеки уже есть, и я бы проверил http://commons.apache.org/math/.