Skip to content
The Chat Archive
grok-3-preview-02-24· xAI LMArena Human Preference 140K

Give me the most optimized code for strassen's matrix multiplication

  1. User

    Give me the most optimized code for strassen's matrix multiplication

  2. Assistant

    Here's an optimized implementation of Strassen's Matrix Multiplication algorithm in C++. This implementation includes several optimizations while maintaining readability:

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <cstring>
    
    using namespace std;
    
    // Threshold for switching to standard multiplication for small matrices
    const int THRESHOLD = 64;
    
    // Standard matrix multiplication for small matrices
    void standardMultiply(const vector<vector<int>>& A, const vector<vector<int>>& B, 
                         vector<vector<int>>& C, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                C[i][j] = 0;
                for (int k = 0; k < n; k++) {
                    C[i][j] += A[i][k] * B[k][j];
                }
            }
        }
    }
    
    // Utility function to add matrices
    void addMatrix(const vector<vector<int>>& A, const vector<vector<int>>& B, 
                   vector<vector<int>>& C, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                C[i][j] = A[i][j] + B[i][j];
            }
        }
    }
    
    // Utility function to subtract matrices
    void subtractMatrix(const vector<vector<int>>& A, const vector<vector<int>>& B, 
                       vector<vector<int>>& C, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                C[i][j] = A[i][j] - B[i][j];
            }
        }
    }
    
    // Strassen's Matrix Multiplication
    void strassenMultiply(vector<vector<int>>& A, vector<vector<int>>& B, 
                         vector<vector<int>>& C, int n) {
        // Base case: if matrix size is below threshold, use standard multiplication
        if (n <= THRESHOLD) {
            standardMultiply(A, B, C, n);
            return;
        }
    
        // If n is not a power of 2, pad the matrices
        int newSize = n;
        if (n & (n - 1)) { // If n is not a power of 2
            newSize = 1;
            while (newSize < n) {
                newSize <<= 1;
            }
        }
    
        // Create padded matrices if needed
        vector<vector<int>> paddedA, paddedB, paddedC;
        if (newSize != n) {
            paddedA = vector<vector<int>>(newSize, vector<int>(newSize, 0));
            paddedB = vector<vector<int>>(newSize, vector<int>(newSize, 0));
            paddedC = vector<vector<int>>(newSize, vector<int>(newSize, 0));
            
            // Copy original matrices to padded matrices
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    paddedA[i][j] = A[i][j];
                    paddedB[i][j] = B[i][j];
                }
            }
            A = paddedA;
            B = paddedB;
            C = paddedC;
        }
    
        int half = newSize / 2;
    
        // Create submatrices
        vector<vector<int>> A11(half, vector<int>(half));
        vector<vector<int>> A12(half, vector<int>(half));
        vector<vector<int>> A21(half, vector<int>(half));
        vector<vector<int>> A22(half, vector<int>(half));
        vector<vector<int>> B11(half, vector<int>(half));
        vector<vector<int>> B12(half, vector<int>(half));
        vector<vector<int>> B21(half, vector<int>(half));
        vector<vector<int>> B22(half, vector<int>(half));
    
        // Divide matrices into quadrants
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half; j++) {
                A11[i][j] = A[i][j];
                A12[i][j] = A[i][j + half];
                A21[i][j] = A[i + half][j];
                A22[i][j] = A[i + half][j + half];
                
                B11[i][j] = B[i][j];
                B12[i][j] = B[i][j + half];
                B21[i][j] = B[i + half][j];
                B22[i][j] = B[i + half][j + half];
            }
        }
    
        // Create temporary matrices for the 7 products
        vector<vector<int>> P1(half, vector<int>(half));
        vector<vector<int>> P2(half, vector<int>(half));
        vector<vector<int>> P3(half, vector<int>(half));
        vector<vector<int>> P4(half, vector<int>(half));
        vector<vector<int>> P5(half, vector<int>(half));
        vector<vector<int>> P6(half, vector<int>(half));
        vector<vector<int>> P7(half, vector<int>(half));
    
        // Create temporary matrices for intermediate results
        vector<vector<int>> temp1(half, vector<int>(half));
        vector<vector<int>> temp2(half, vector<int>(half));
    
        // Calculate the 7 products using Strassen's algorithm
        
        // P1 = A11 * (B12 - B22)
        subtractMatrix(B12, B22, temp1, half);
        strassenMultiply(A11, temp1, P1, half);
    
        // P2 = (A11 + A12) * B22
        addMatrix(A11, A12, temp1, half);
        strassenMultiply(temp1, B22, P2, half);
    
        // P3 = (A21 + A22) * B11
        addMatrix(A21, A22, temp1, half);
        strassenMultiply(temp1, B11, P3, half);
    
        // P4 = A22 * (B21 - B11)
        subtractMatrix(B21, B11, temp1, half);
        strassenMultiply(A22, temp1, P4, half);
    
        // P5 = (A11 + A22) * (B11 + B22)
        addMatrix(A11, A22, temp1, half);
        addMatrix(B11, B22, temp2, half);
        strassenMultiply(temp1, temp2, P5, half);
    
        // P6 = (A12 - A22) * (B21 + B22)
        subtractMatrix(A12, A22, temp1, half);
        addMatrix(B21, B22, temp2, half);
        strassenMultiply(temp1, temp2, P6, half);
    
        // P7 = (A11 - A21) * (B11 + B12)
        subtractMatrix(A11, A21, temp1, half);
        addMatrix(B11, B12, temp2, half);
        strassenMultiply(temp1, temp2, P7, half);
    
        // Calculate quadrants of result matrix
        vector<vector<int>> C11(half, vector<int>(half));
        vector<vector<int>> C12(half, vector<int>(half));
        vector<vector<int>> C21(half, vector<int>(half));
        vector<vector<int>> C22(half, vector<int>(half));
    
        // C11 = P5 + P4 - P2 + P6
        addMatrix(P5, P4, temp1, half);
        subtractMatrix(temp1, P2, temp2, half);
        addMatrix(temp2, P6, C11, half);
    
        // C12 = P1 + P2
        addMatrix(P1, P2, C12, half);
    
        // C21 = P3 + P4
        addMatrix(P3, P4, C21, half);
    
        // C22 = P5 + P1 - P3 - P7
        addMatrix(P5, P1, temp1, half);
        subtractMatrix(temp1, P3, temp2, half);
        subtractMatrix(temp2, P7, C22, half);
    
        // Combine quadrants into result matrix
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half; j++) {
                C[i][j] = C11[i][j];
                C[i][j + half] = C12[i][j];
                C[i + half][j] = C21[i][j];
                C[i + half][j + half] = C22[i][j];
            }
        }
    
        // If we padded the matrices, copy back only the relevant portion
        if (newSize != n) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    C[i][j] = paddedC[i][j];
                }
            }
        }
    }
    
    // Utility function to print matrix
    void printMatrix(const vector<vector<int>>& matrix, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << matrix[i][j] << " ";
            }
            cout << endl;
        }
    }
    
    // Main function to test the implementation
    int main() {
        int n = 4; // Size of matrices (must be power of 2 for optimal performance)
        
        // Initialize matrices
        vector<vector<int>> A = {{1, 2, 3, 4},
                                {5, 6, 7, 8},
                                {9, 10, 11, 12},
                                {13, 14, 15, 16}};
        
        vector<vector<int>> B = {{16, 15, 14, 13},
                                {12, 11, 10, 9},
                                {8, 7, 6, 5},
                                {4, 3, 2, 1}};
        
        vector<vector<int>> C(n, vector<int>(n, 0));
    
        // Perform Strassen multiplication
        strassenMultiply(A, B, C, n);
    
        // Print result
        cout << "Result matrix:" << endl;
        printMatrix(C, n);
    
        return 0;
    }
    

    Key optimizations and features in this implementation:

    1. Threshold Optimization: Uses standard matrix multiplication for small matrices (below THRESHOLD) where Strassen's algorithm might have more overhead.

    2. Padding for Non-Power-of-2 Sizes: Handles matrices of any size by padding to the next power of 2, though optimal performance is achieved with power-of-2 sized matrices.

    3. Memory Efficiency: Uses vector of vectors for dynamic memory allocation, though for maximum performance in a production environment, you might want to use a flat array with manual indexing.

    4. Cache-Friendly Operations: The matrix operations are implemented in a way that maintains good cache locality.

    5. Reduced Memory Allocations: Temporary matrices are reused where possible.

    To further optimize this code for production use, you could:

    1. Use flat arrays instead of vector of vectors for better cache performance
    2. Implement SIMD instructions for the basic operations
    3. Add parallel processing for large matrices
    4. Use memory alignment for better cache utilization
    5. Implement in-place operations to reduce memory usage

    Time Complexity:

    • Theoretical: O(n^log₂7) ≈ O(n^2.807)
    • Compare to standard multiplication: O(n^3)

    Space Complexity:

    • O(n^2) for the matrices
    • Additional temporary space during recursion

    Note that while Strassen's algorithm has better theoretical complexity, in practice, the standard algorithm might be faster for smaller matrices due to better cache utilization and fewer operations. The THRESHOLD value can be tuned based on your specific hardware and use case.

    For real-world applications, you might want to consider using optimized linear algebra libraries like BLAS or LAPACK, which often include highly optimized matrix multiplication routines that may use Strassen's algorithm internally along with other optimizations.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.