0

我正在尝试测试矩阵乘法的朴素和施特拉森方法。

然而，Strassen 算法的工作速度比天真的方法慢得多。对于 1024 大小的矩阵，朴素方法在 3542 毫秒内完成，而 Strassen 在 83602 毫秒内完成。（Strassen 不使用截断/幼稚的方法）这是我正在使用的 Strassen 代码。LEAF SIZE 是它切换到幼稚方法的数字：

int n = A.length;

if (n <= LEAF_SIZE) {
    return ikjAlgorithm(A, B);
} else {
    // initializing the new sub-matrices
    int newSize = n / 2;
    int[][] a11 = new int[newSize][newSize];
    int[][] a12 = new int[newSize][newSize];
    int[][] a21 = new int[newSize][newSize];
    int[][] a22 = new int[newSize][newSize];

    int[][] b11 = new int[newSize][newSize];
    int[][] b12 = new int[newSize][newSize];
    int[][] b21 = new int[newSize][newSize];
    int[][] b22 = new int[newSize][newSize];

    int[][] aResult = new int[newSize][newSize];
    int[][] bResult = new int[newSize][newSize];

    // dividing the matrices in 4 sub-matrices:
    for (int i = 0; i < newSize; i++) {
        for (int j = 0; j < newSize; j++) {
            a11[i][j] = A[i][j]; // top left
            a12[i][j] = A[i][j + newSize]; // top right
            a21[i][j] = A[i + newSize][j]; // bottom left
            a22[i][j] = A[i + newSize][j + newSize]; // bottom right

            b11[i][j] = B[i][j]; // top left
            b12[i][j] = B[i][j + newSize]; // top right
            b21[i][j] = B[i + newSize][j]; // bottom left
            b22[i][j] = B[i + newSize][j + newSize]; // bottom right
        }
    }

    // Calculating p1 to p7:
    aResult = add(a11, a22);
    bResult = add(b11, b22);
    int[][] p1 = strassenR(aResult, bResult);
    // p1 = (a11+a22) * (b11+b22)

    aResult = add(a21, a22); // a21 + a22
    int[][] p2 = strassenR(aResult, b11); // p2 = (a21+a22) * (b11)

    bResult = subtract(b12, b22); // b12 - b22
    int[][] p3 = strassenR(a11, bResult);
    // p3 = (a11) * (b12 - b22)

    bResult = subtract(b21, b11); // b21 - b11
    int[][] p4 = strassenR(a22, bResult);
    // p4 = (a22) * (b21 - b11)

    aResult = add(a11, a12); // a11 + a12
    int[][] p5 = strassenR(aResult, b22);
    // p5 = (a11+a12) * (b22)

    aResult = subtract(a21, a11); // a21 - a11
    bResult = add(b11, b12); // b11 + b12
    int[][] p6 = strassenR(aResult, bResult);
    // p6 = (a21-a11) * (b11+b12)

    aResult = subtract(a12, a22); // a12 - a22
    bResult = add(b21, b22); // b21 + b22
    int[][] p7 = strassenR(aResult, bResult);
    // p7 = (a12-a22) * (b21+b22)

    // calculating c21, c21, c11 e c22:
    int[][] c12 = add(p3, p5); // c12 = p3 + p5
    int[][] c21 = add(p2, p4); // c21 = p2 + p4

    aResult = add(p1, p4); // p1 + p4
    bResult = add(aResult, p7); // p1 + p4 + p7
    int[][] c11 = subtract(bResult, p5);
    // c11 = p1 + p4 - p5 + p7

    aResult = add(p1, p3); // p1 + p3
    bResult = add(aResult, p6); // p1 + p3 + p6
    int[][] c22 = subtract(bResult, p2);
    // c22 = p1 + p3 - p2 + p6

    // Grouping the results obtained in a single matrix:
    int[][] C = new int[n][n];
    for (int i = 0; i < newSize; i++) {
        for (int j = 0; j < newSize; j++) {
            C[i][j] = c11[i][j];
            C[i][j + newSize] = c12[i][j];
            C[i + newSize][j] = c21[i][j];
            C[i + newSize][j + newSize] = c22[i][j];
        }
    }
    return C;
}

private static int[][] add(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++) {
            C[i][j] = A[i][j] + B[i][j];
        }
    }
    return C;
}

private static int[][] subtract(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++) {
            C[i][j] = A[i][j] - B[i][j];
        }
    }
    return C;
}

叶子大小在 32 左右，它确实执行得更快（这是天真的算法开始的截止点）

这是Java语言。代码来自互联网，但或多或​​少所有的实现都是相似的。

没有切入点，仅凭 Strassen 就无法击败幼稚吗？任何想法，将不胜感激。谢谢你。

编辑添加了加法和减法。

EDIT2从代码中创建新子矩阵的最大开销是什么？如果是这样，可以应用什么方法来消除尽可能多的开销？如果在 java 中什么都做不了，我不反对使用 c++。

EDIT3任何人都可以提出一种方法来减少这里使用的内存分配吗？将不胜感激的建议。

4

0 回答 0