Give me the most optimized code for strassen's matrix multiplication
- User
Give me the most optimized code for strassen's matrix multiplication
- 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:
-
Threshold Optimization: Uses standard matrix multiplication for small matrices (below THRESHOLD) where Strassen's algorithm might have more overhead.
-
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.
-
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.
-
Cache-Friendly Operations: The matrix operations are implemented in a way that maintains good cache locality.
-
Reduced Memory Allocations: Temporary matrices are reused where possible.
To further optimize this code for production use, you could:
- Use flat arrays instead of vector of vectors for better cache performance
- Implement SIMD instructions for the basic operations
- Add parallel processing for large matrices
- Use memory alignment for better cache utilization
- 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.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.