Introduction:
Strassen's algorithm, developed by Volker Strassen in 1969, transformed the process of matrix multiplication by introducing a more efficient method, especially beneficial for handling large matrices. In contrast to the traditional multiplication approach, Strassen's technique strategically reduces the quantity of necessary multiplications. The fundamental idea involves representing the matrix product as a series of smaller multiplications, utilizing a divide-and-conquer methodology. Through the recursive subdivision of matrices into quadrants, this algorithm achieves a decreased number of multiplications, leading to enhanced computational effectiveness. This inventive approach has been applied across various domains and continues to be a fundamental aspect of algorithmic enhancement. Strassen's algorithm, striking a balance between complexity and performance, underscores the importance of innovative strategies in algorithm development.
Program:
#include <iostream>
#include <vector>
using namespace std;
// Function to add two matrices
void matrixAddition(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];
}
}
}
// Function to subtract one matrix from another
void matrixSubtraction(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];
}
}
}
// Function to multiply two matrices using Strassen's algorithm
void strassenMultiplication(const vector<vector<int>>& A, const vector<vector<int>>& B, vector<vector<int>>& C, int n) {
if (n == 1) {
C[0][0] = A[0][0] * B[0][0];
return;
}
// Split matrices into quadrants
int newSize = n / 2;
vector<vector<int>> A11(newSize, vector<int>(newSize));
vector<vector<int>> A12(newSize, vector<int>(newSize));
vector<vector<int>> A21(newSize, vector<int>(newSize));
vector<vector<int>> A22(newSize, vector<int>(newSize));
vector<vector<int>> B11(newSize, vector<int>(newSize));
vector<vector<int>> B12(newSize, vector<int>(newSize));
vector<vector<int>> B21(newSize, vector<int>(newSize));
vector<vector<int>> B22(newSize, vector<int>(newSize));
vector<vector<int>> C11(newSize, vector<int>(newSize));
vector<vector<int>> C12(newSize, vector<int>(newSize));
vector<vector<int>> C21(newSize, vector<int>(newSize));
vector<vector<int>> C22(newSize, vector<int>(newSize));
// Populate quadrants
for (int i = 0; i < newSize; ++i) {
for (int j = 0; j < newSize; ++j) {
A11[i][j] = A[i][j];
A12[i][j] = A[i][j + newSize];
A21[i][j] = A[i + newSize][j];
A22[i][j] = A[i + newSize][j + newSize];
B11[i][j] = B[i][j];
B12[i][j] = B[i][j + newSize];
B21[i][j] = B[i + newSize][j];
B22[i][j] = B[i + newSize][j + newSize];
}
}
// Compute intermediate matrices
vector<vector<int>> P1(newSize, vector<int>(newSize));
vector<vector<int>> P2(newSize, vector<int>(newSize));
vector<vector<int>> P3(newSize, vector<int>(newSize));
vector<vector<int>> P4(newSize, vector<int>(newSize));
vector<vector<int>> P5(newSize, vector<int>(newSize));
vector<vector<int>> P6(newSize, vector<int>(newSize));
vector<vector<int>> P7(newSize, vector<int>(newSize));
matrixAddition(A11, A22, P1, newSize);
matrixAddition(B11, B22, P2, newSize);
matrixAddition(A21, A22, P3, newSize);
matrixSubtraction(B12, B22, P4, newSize);
matrixSubtraction(B21, B11, P5, newSize);
matrixAddition(A11, A12, P6, newSize);
matrixSubtraction(A21, A11, P7, newSize);
// Recursively compute products
strassenMultiplication(P1, P2, C11, newSize);
strassenMultiplication(P3, B11, C12, newSize);
strassenMultiplication(A11, P4, C21, newSize);
strassenMultiplication(A22, P5, C22, newSize);
strassenMultiplication(P6, P7, C11, newSize);
matrixAddition(C11, P3, C12, newSize);
matrixSubtraction(C21, P2, C21, newSize);
matrixAddition(C22, P1, C22, newSize);
// Combine quadrants into the result
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];
}
}
}
int main() {
// Example usage
int n = 4; // Size of matrices (should be a power of 2 for Strassen's algorithm)
vector<vector<int>> A = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
vector<vector<int>> B = {{17, 18, 19, 20},
{21, 22, 23, 24},
{25, 26, 27, 28},
{29, 30, 31, 32}};
vector<vector<int>> C(n, vector<int>(n, 0));
strassenMultiplication(A, B, C, n);
// Print the result
cout << "Matrix A:" << endl;
for (const auto& row : A) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
cout << "\nMatrix B:" << endl;
for (const auto& row : B) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
cout << "\nMatrix C (Result of A * B using Strassen's algorithm):" << endl;
for (const auto& row : C) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
return 0;
}
Output:
Matrix A:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Matrix B:
17 18 19 20
21 22 23 24
25 26 27 28
29 30 31 32
Matrix C (Result of A * B using Strassen's algorithm):
80 106 100 128
-16 18 12 48
-32 -23 104 137
-36 -47 4 49
Explanation:
- Functions for Adding and Subtracting Matrices:
The process starts with establishing functions to perform matrix addition and subtraction. These functions require two matrices (A and B) as input parameters and execute the operation accordingly, saving the outcome in a separate matrix (C).
- Strassen Multiplication Algorithm:
The primary emphasis of the application lies in the strassenMultiplication function, which executes Strassen's algorithm for multiplying matrices.
If the matrices have dimensions of 1x1 (base scenario), the function computes the product immediately and then proceeds to return the result.
Otherwise, it divides the input matrices into four quadrants and executes a sequence of matrix calculations to determine intermediary matrices (P1 to P7).
Iteratively, the Strassen algorithm is implemented to compute these intermediary matrices.
Finally, it merges these interim matrices together to construct the resultant matrix (C).
- Primary Function:
In the primary function, matrices A and B are set with sample values.
Subsequently, the software generates a vacant matrix C with identical dimensions to store the outcome of multiplying matrices A and B through the utilization of Strassen's algorithm.
The strassenMultiplication procedure is invoked using matrices A, B, and an uninitialized matrix C.
- Illustrative Implementation:
The software displays the initial matrices A and B, along with the resultant matrix C.
This illustrates the accuracy of Strassen's algorithm when executing matrix multiplication.
- Insight on Matrix Dimensions:
To achieve optimal efficiency with Strassen's algorithm, it is recommended that the dimensions of matrices are set as powers of 2. This is crucial because the algorithm iteratively divides matrices into smaller submatrices until they reach a size of 1x1, which serves as the termination condition.
- Understanding the Outcome:
The output of matrix multiplication (C) is displayed on the console, demonstrating the performance of Strassen's algorithm in computing the product of matrices A and B.
Complexity analysis:
Time Complexity:
The time complexity of Strassen's algorithm for matrix multiplication is O(nlog27) where n represents the dimensions of the matrices.
During each iteration, the algorithm executes a fixed quantity of matrix additions, subtractions, and multiplications. Seven recursive invocations (P1 to P7) contribute to the logarithmic 27 power in the time complexity analysis.
Space Complexity:
The space requirement of Strassen's algorithm is O(n2) because it involves storing temporary matrices while making recursive calls.
In every iteration of the recursion, the algorithm necessitates extra memory for holding matrices like P1 to P7 and the smaller matrices employed in computations.
The recursion depth impacts the space complexity, which is logarithmic to the base 2 of n for matrices with a size of n. Consequently, the total space complexity amounts to O(n^2 log^2 n).
Approach 1: Traditional Matrix Multiplication
This method requires a direct application of matrix multiplication with the use of three embedded loops. Although it may not be as optimized as Strassen's algorithm for handling extensive matrices, it offers a clear and uncomplicated approach.
Program:
#include <iostream>
#include <vector>
using namespace std;
void matrixMultiplication(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];
}
}
}
}
int main() {
// Example usage
int n = 4; // Size of 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 = {{17, 18, 19, 20},
{21, 22, 23, 24},
{25, 26, 27, 28},
{29, 30, 31, 32}};
vector<vector<int>> C(n, vector<int>(n, 0));
matrixMultiplication(A, B, C, n);
// Print the result
cout << "Matrix A:" << endl;
for (const auto& row : A) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
cout << "\nMatrix B:" << endl;
for (const auto& row : B) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
cout << "\nMatrix C (Result of A * B using traditional multiplication):" << endl;
for (const auto& row : C) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
return 0;
}
Output:
Matrix A:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Matrix B:
17 18 19 20
21 22 23 24
25 26 27 28
29 30 31 32
Matrix C (Result of A * B using traditional multiplication):
250 260 270 280
618 644 670 696
986 1028 1070 1112
1354 1412 1470 1528
Explanation:
- Input Matrices:
We begin with two input matrices, known as matrix A and matrix B. Each matrix represents an array of numbers organized in rows and columns.
- Initializing the Result Matrix:
We instantiate a new matrix, denoted as matrix C, to hold the outcome of the multiplication operation. Matrix C is structured with an identical row count as matrix A and a matching column count as matrix B.
- Utilizing Nested Loops for Multiplication:
We employ a set of three nested loops to traverse through the rows and columns of matrices A, B, and C.
The top-level loop cycles through the rows of matrix A.
The second loop goes through the columns of matrix B.
The most nested loop is in charge of computing the specific components of matrix C.
- Performing Multiplication and Accumulation:
For every item in matrix C, a sequence of multiplications and additions is carried out.
Populating the Result Matrix:
As we iterate through the nested loops, we compute and populate every cell in matrix C according to the defined multiplication and addition procedures.
- Finishing the Multiplication:
Upon finishing all cycles of the nested loops, matrix C is completely filled with the outcome of the matrix multiplication process.
The ultimate matrix C is obtained by performing matrix A multiplication with matrix B through the conventional multiplication method.
Complexity analysis:
Time Complexity:
The time complexity of the conventional matrix multiplication method is O(n3), with n representing the dimensions of the matrices involved.
This cubic time complexity occurs due to the fact that, for every item in the resulting matrix, we execute n multiplications and n additions within the nested loops. Given that we have
n2 components to compute in the resulting matrix, the total computational complexity is ```
include <iostream>
include <vector>
using namespace std;
// Function to add two matrices
void matrixAddition(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) {
Ci = Ai + Bi;
}
}
}
// Function to subtract one matrix from another
void matrixSubtraction(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) {
Ci = Ai - Bi;
}
}
}
// Function to multiply two matrices using Strassen's algorithm
void strassenMultiplication(const vector<vector<int>>& A, const vector<vector<int>>& B, vector<vector<int>>& C, int n) {
if (n == 1) {
C0 = A0 * B0;
return;
}
// Split matrices into quadrants
int newSize = n / 2;
vector<vector<int>> A11(newSize, vector<int>(newSize));
vector<vector<int>> A12(newSize, vector<int>(newSize));
vector<vector<int>> A21(newSize, vector<int>(newSize));
vector<vector<int>> A22(newSize, vector<int>(newSize));
vector<vector<int>> B11(newSize, vector<int>(newSize));
vector<vector<int>> B12(newSize, vector<int>(newSize));
vector<vector<int>> B21(newSize, vector<int>(newSize));
vector<vector<int>> B22(newSize, vector<int>(newSize));
vector<vector<int>> C11(newSize, vector<int>(newSize));
vector<vector<int>> C12(newSize, vector<int>(newSize));
vector<vector<int>> C21(newSize, vector<int>(newSize));
vector<vector<int>> C22(newSize, vector<int>(newSize));
// Populate quadrants
for (int i = 0; i < newSize; ++i) {
for (int j = 0; j < newSize; ++j) {
A11i = Ai;
A12i = Ai;
A21i = Ai + newSize;
A22i = Ai + newSize;
B11i = Bi;
B12i = Bi;
B21i = Bi + newSize;
B22i = Bi + newSize;
}
}
// Compute intermediate matrices
vector<vector<int>> P1(newSize, vector<int>(newSize));
vector<vector<int>> P2(newSize, vector<int>(newSize));
vector<vector<int>> P3(newSize, vector<int>(newSize));
vector<vector<int>> P4(newSize, vector<int>(newSize));
vector<vector<int>> P5(newSize, vector<int>(newSize));
vector<vector<int>> P6(newSize, vector<int>(newSize));
vector<vector<int>> P7(newSize, vector<int>(newSize));
matrixAddition(A11, A22, P1, newSize);
matrixAddition(B11, B22, P2, newSize);
matrixAddition(A21, A22, P3, newSize);
matrixSubtraction(B12, B22, P4, newSize);
matrixSubtraction(B21, B11, P5, newSize);
matrixAddition(A11, A12, P6, newSize);
matrixSubtraction(A21, A11, P7, newSize);
// Recursively compute products
strassenMultiplication(P1, P2, C11, newSize);
strassenMultiplication(P3, B11, C12, newSize);
strassenMultiplication(A11, P4, C21, newSize);
strassenMultiplication(A22, P5, C22, newSize);
strassenMultiplication(P6, P7, C11, newSize);
matrixAddition(C11, P3, C12, newSize);
matrixSubtraction(C21, P2, C21, newSize);
matrixAddition(C22, P1, C22, newSize);
// Combine quadrants into the result
for (int i = 0; i < newSize; ++i) {
for (int j = 0; j < newSize; ++j) {
Ci = C11i;
Ci = C12i;
Ci + newSize = C21i;
Ci + newSize = C22i;
}
}
}
int main {
// Example usage
int n = 4; // Size of matrices (should be a power of 2 for Strassen's algorithm)
vector<vector<int>> A = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
vector<vector<int>> B = {{17, 18, 19, 20},
{21, 22, 23, 24},
{25, 26, 27, 28},
{29, 30, 31, 32}};
vector<vector<int>> C(n, vector<int>(n, 0));
strassenMultiplication(A, B, C, n);
// Print the result
cout << "Matrix A:" << endl;
for (const auto& row : A) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
cout << "\nMatrix B:" << endl;
for (const auto& row : B) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
cout << "\nMatrix C (Result of A * B using Strassen's algorithm):" << endl;
for (const auto& row : C) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
return 0;
}
O(n3).
Space Complexity:
The space efficiency is O(n2) because it is determined by the dimensions of the resulting matrix.
The algorithm does not necessitate extra space in relation to the input size (n) apart from the input matrices A and B. Instead, it allocates space for the outcome matrix C, containing n squared elements.
The storage requirements of the result matrix typically have the most significant impact on the space complexity.
### Properties:
Some characteristics of the Strassen's algorithm in C++ include the following:
- Divide and Conquer:
Strassen's algorithm employs a divide-and-conquer approach to decompose the matrix multiplication task into more manageable subtasks.
It divides large matrices into smaller ones repeatedly until it reaches base cases such as matrices with dimensions of 1x1.
- Decreased number of multiplications:
One key benefit of Strassen's algorithm lies in its capacity to decrease the quantity of multiplications in contrast to the conventional cubic time complexity.
Instead of performing eight multiplications as seen in the straightforward method, Strassen's algorithm reduces this to just seven multiplications. This optimization results in enhanced performance, especially noticeable with larger matrices.
- Recursion Depth:
The Strassen's algorithm recursion depth is log base 2 of 7, achieved by dividing matrices into smaller quadrants in every recursive iteration.
The recursive characteristic enables the efficient computation of intermediary matrices.
Enhanced Arithmetic Operations:
Strassen's algorithm utilizes a blend of additions and subtractions to calculate intermediate matrices in an efficient manner.
These procedures aid in decreasing the total computational expense.
- Matrix Dimensions in Powers of 2:
Strassen's algorithm demonstrates optimal performance when utilized with matrices that have dimensions which are multiples of 2.
If the dimensions of the input matrices are not powers of 2, it might be essential to add padding or resize them accordingly.
- Usage in Parallel Computing:
Strassen's algorithm is ideal for parallel computing settings, as each iteration can be executed autonomously.
Implementing parallel processing in the algorithm can lead to improved performance especially when dealing with extensive matrices.
