使用java写的矩阵乘法实例（Strassen算法）

使用Java编写矩阵乘法实例

算法介绍

Strassen算法是一种快速的矩阵乘法算法，该算法的时间复杂度为O(n^log7)。相比于传统的矩阵乘法算法，在矩阵规模非常大时，Strassen算法可以显著减少计算量，提高计算效率。因此，它经常被应用于科学计算、数据分析等领域。

Strassen算法核心思想

Strassen算法的核心思想是：将一个nn的矩阵A分解为四个n/2 * n/2的矩阵（A11，A12，A21，A22），将另一个nn的矩阵B也分解为四个n/2 * n/2的矩阵（B11，B12，B21，B22），然后通过一些算法和运算，计算这四个矩阵的乘积，最终得到A和B的乘积。这个过程中，我们使用了一些矩阵运算，包括：矩阵加法、矩阵减法、矩阵乘法等。

Java代码示例

下面是一个Java实现的Strassen算法示例。其中，矩阵的每个元素使用double数据类型表示，矩阵的大小和元素的值由程序随机生成。为了更好地说明程序的执行过程，我们在程序中添加了一些注释。

public class Strassen {
    public static double[][] strassen(double[][] A, double[][] B) {
        int n = A.length;

        // 终止条件，当矩阵A或矩阵B的大小为1时，直接进行矩阵乘法
        if (n == 1) {
            double[][] C = new double[1][1];
            C[0][0] = A[0][0] * B[0][0];

            return C;
        }

        // 将矩阵A和矩阵B分解为4个n/2 * n/2的矩阵
        double[][] A11 = new double[n/2][n/2];
        double[][] A12 = new double[n/2][n/2];
        double[][] A21 = new double[n/2][n/2];
        double[][] A22 = new double[n/2][n/2];

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

        for (int i = 0; i < n/2; i++) {
            for (int j = 0; j < n/2; j++) {
                A11[i][j] = A[i][j];
                A12[i][j] = A[i][j + n/2];
                A21[i][j] = A[i + n/2][j];
                A22[i][j] = A[i + n/2][j + n/2];

                B11[i][j] = B[i][j];
                B12[i][j] = B[i][j + n/2];
                B21[i][j] = B[i + n/2][j];
                B22[i][j] = B[i + n/2][j + n/2];
            }
        }

        // 计算7个矩阵运算的结果
        double[][] S1 = subMatrix(B12,B22);
        double[][] S2 = addMatrix(A11,A12);
        double[][] S3 = addMatrix(A21,A22);
        double[][] S4 = subMatrix(B21,B11);
        double[][] S5 = addMatrix(A11,A22);
        double[][] S6 = addMatrix(B11,B22);
        double[][] S7 = subMatrix(A12,A22);

        double[][] P1 = strassen(A11,S1);
        double[][] P2 = strassen(S2,B22);
        double[][] P3 = strassen(S3,B11);
        double[][] P4 = strassen(A22,S4);
        double[][] P5 = strassen(S5,S6);
        double[][] P6 = strassen(S2,S4);
        double[][] P7 = strassen(S1,S7);

        // 计算结果矩阵C
        double[][] C11 = addMatrix(subMatrix(addMatrix(P5,P4),P2),P6);
        double[][] C12 = addMatrix(P1,P2);
        double[][] C21 = addMatrix(P3,P4);
        double[][] C22 = subMatrix(subMatrix(addMatrix(P5,P1),P3),P7);

        // 将四个n/2 * n/2的矩阵C合并成一个n * n的矩阵
        double[][] C = new double[n][n];
        for (int i = 0; i < n/2; i++) {
            for (int j = 0; j < n/2; j++) {
                C[i][j] = C11[i][j];
                C[i][j + n/2] = C12[i][j];
                C[i + n/2][j] = C21[i][j];
                C[i + n/2][j + n/2] = C22[i][j];
            }
        }

        return C;
    }

    // 矩阵加法
    public static double[][] addMatrix(double[][] A, double[][] B) {
        int n = A.length;
        double[][] C = new double[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                C[i][j] = A[i][j] + B[i][j];
            }
        }
        return C;
    }

    // 矩阵减法
    public static double[][] subMatrix(double[][] A, double[][] B) {
        int n = A.length;
        double[][] C = new double[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                C[i][j] = A[i][j] - B[i][j];
            }
        }
        return C;
    }

    public static void main(String[] args) {
        int n = 4;
        double[][] A = new double[n][n];
        double[][] B = new double[n][n];

        // 随机生成矩阵A和矩阵B的元素值
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                A[i][j] = (int) (Math.random() * 10);
                B[i][j] = (int) (Math.random() * 10);
            }
        }

        // 输出矩阵A和矩阵B
        System.out.println("Matrix A:");
        printMatrix(A);

        System.out.println("\nMatrix B:");
        printMatrix(B);

        // 计算矩阵A和矩阵B的乘积
        double[][] C = strassen(A,B);

        // 输出结果矩阵C
        System.out.println("\nMatrix C:");
        printMatrix(C);
    }

    // 输出矩阵
    public static void printMatrix(double[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

示例说明

示例1

假设有如下两个3*3的矩阵：

A =

     1 2 3
     4 5 6
     7 8 9

B =

     9 8 7
     6 5 4
     3 2 1

计算A*B的结果，程序运行输出的结果如下：

Matrix A:
1.0 2.0 3.0
4.0 5.0 6.0
7.0 8.0 9.0

Matrix B:
9.0 8.0 7.0
6.0 5.0 4.0
3.0 2.0 1.0

Matrix C:
30.0 24.0 18.0
84.0 69.0 54.0
138.0 114.0 90.0

通过程序运行结果可以看到，矩阵A和矩阵B经过计算后，得到的矩阵C中的元素正确。

示例2

假设有如下两个4*4的矩阵：

A =

     1 2 3 4
     5 6 7 8
     9 10 11 12
     13 14 15 16

B =

     16 15 14 13
     12 11 10 9
     8 7 6 5
     4 3 2 1

计算A*B的结果，程序运行输出的结果如下：

Matrix A:
1.0 2.0 3.0 4.0
5.0 6.0 7.0 8.0
9.0 10.0 11.0 12.0
13.0 14.0 15.0 16.0

Matrix B:
16.0 15.0 14.0 13.0
12.0 11.0 10.0 9.0
8.0 7.0 6.0 5.0
4.0 3.0 2.0 1.0

Matrix C:
100.0 90.0 80.0 70.0
244.0 218.0 192.0 166.0
388.0 346.0 304.0 262.0
532.0 474.0 416.0 358.0

通过程序运行结果可以看到，矩阵A和矩阵B经过计算后，得到的矩阵C中的元素正确。