Java 實現任意尺寸矩陣乘法：Strassen 算法完整代碼與優化解析

Strassen 算法將矩陣乘法時間複雜度從 O(n³) 降至 O(n^log₂7) ≈ O(n^2.807)，適合大規模矩陣運算。本文提供處理非方陣、非 2^k 尺寸的通用 Java 實現。

核心策略

1. 方陣化：非方陣補零擴展為方陣。
2. 分塊：找到最大 l = 2^k (l < n)，核心區用 Strassen，邊緣區用暴力法。
3. 遞歸基例：n == 1 直接相乘。

關鍵代碼結構

public class StrassenMethod {
    // 核心遞歸：僅處理 2^k 方陣
    public double[][] strassenMultiplyMatrix(double[][] A, double[][] B, int n) {
        if (n == 1) return new double[][]{{A[0][0] * B[0][0]}};

        // 1. 分割為 4 個子矩陣
        int half = n / 2;
        double[][] A11 = subMatrix(A, 0, 0, half);
        // ... A12, A21, A22, B11...B22

        // 2. 計算 7 個中間矩陣 (Strassen 公式)
        double[][] S1 = subtract(B12, B22); // P1 = A11 * (B12 - B22)
        double[][] S2 = add(A11, A12);      // P2 = (A11 + A12) * B22
        // ... S3-S9

        double[][] P1 = strassenMultiplyMatrix(A11, S1, half);
        double[][] P2 = strassenMultiplyMatrix(S2, B22, half);
        // ... P3-P7

        // 3. 合併結果
        double[][] C11 = add(subtract(add(P4, P3), P1), P5);
        double[][] C12 = add(P1, P2);
        double[][] C21 = add(P3, P4);
        double[][] C22 = subtract(subtract(add(P4, P1), P2), P6);

        return combine(C11, C12, C21, C22);
    }
}

非標準尺寸處理

public double[][] multiplyRectMatrix(double[][] A, double[][] B, int aRow, int aCol, int bRow, int bCol) {
    // 1. 校驗 aCol == bRow
    // 2. 補零擴展為 max(aRow, aCol, bCol) 方陣
    // 3. 調用 multiplySquareMatrix
    // 4. 截取有效區域返回
}

性能與工程化建議

手寫 Strassen 是理解分治算法、矩陣分塊、遞歸優化的絕佳練習，但工程落地請站在巨人肩膀上。