KEMBAR78
Strassen's Algorithm For Matrix Multiplication | PDF | Computer Programming | Computational Science
Scribd
Upload
27 views6 pages

Strassen's Algorithm For Matrix Multiplication

The document presents an assignment on the design and analysis of algorithms, specifically focusing on matrix operations in C++. It includes implementations for matrix addition, subtraction, and Strassen's algorithm for matrix multiplication, along with a main function to demonstrate the multiplication of two matrices. The code is structured to handle square matrices and outputs the result of the Strassen matrix multiplication.

Uploaded by

swayamfire2
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
27 views6 pages

Strassen's Algorithm For Matrix Multiplication

The document presents an assignment on the design and analysis of algorithms, specifically focusing on matrix operations in C++. It includes implementations for matrix addition, subtraction, and Strassen's algorithm for matrix multiplication, along with a main function to demonstrate the multiplication of two matrices. The code is structured to handle square matrices and outputs the result of the Strassen matrix multiplication.

Uploaded by

swayamfire2
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 6

ASSIGNMENT

DESIGN AND ANALYSIS OF


ALGORITHMS
Name-
Swayam
Sharma
Roll
number-
3951
Course-
B.Sc.
(Hons.)
Computer
Science
Year- II
Semester-
IV
#include
<iostream>
#include <vector>
using namespace
std;
vector<vector<int>> matrixAdd(const vector<vector<int>>& A, const
vector<vector<int>>&
B) { int n = A.size();
vector<vector<int>> result(n,
vector<int>(n)); for (int i = 0; i < n; +
+i) {

for (int j = 0; j < n; ++j)


{ result[i][j] = A[i][j] +
B[i][j];
}

return result;

vector<vector<int>> matrixSubtract(const vector<vector<int>>& A, const


vector<vector<int>>& B) {

int n = A.size();
vector<vector<int>> result(n,
vector<int>(n));
for (int i = 0; i < n; +
+i) { for (int j = 0; j
< n; ++j)
{ result[i][j] = A[i]
[j] - B[i][j];

return result;

vector<vector<int>> strassenMultiply(const vector<vector<int>>& A,


const vector<vector<int>>& B) {
int n =
A.size(); if (n
== 1) {

return {{A[0][0] * B[0][0]}};

int k = n / 2;

vector<vector<int>> A11(k, vector<int>(k));

vector<vector<int>> A12(k, vector<int>(k));


vector<vector<int>> A21(k, vector<int>(k));
vector<vector<int>> A22(k, vector<int>(k));
vector<vector<int>> B11(k, vector<int>(k));
vector<vector<int>> B12(k, vector<int>(k));
vector<vector<int>> B21(k, vector<int>(k));
vector<vector<int>> B22(k, vector<int>(k));
for (int i = 0; i < k;
++i) { for (int j =
0; j < k; ++j) {
A11[i][j] = A[i][j];
A12[i][j] = A[i][j + k];

A21[i][j] = A[i + k][j];

A22[i][j] = A[i + k][j + k];

B11[i][j] = B[i][j];

B12[i][j] = B[i][j + k];

B21[i][j] = B[i + k][j];

B22[i][j] = B[i + k][j + k];

}
}

vector<vector<int>> P1 = strassenMultiply(A11, matrixSubtract(B12,


B22)); vector<vector<int>> P2 = strassenMultiply(matrixAdd(A11, A12),
B22); vector<vector<int>> P3 = strassenMultiply(matrixAdd(A21, A22),
B11); vector<vector<int>> P4 = strassenMultiply(A22,
matrixSubtract(B21, B11)); vector<vector<int>> P5 =
strassenMultiply(matrixAdd(A11, A22), matrixAdd(B11, B22));
vector<vector<int>> P6 = strassenMultiply(matrixSubtract(A12, A22),
matrixAdd(B21, B22));

vector<vector<int>> P7 = strassenMultiply(matrixSubtract(A11, A21),


matrixAdd(B11, B12)); vector<vector<int>> C11 =
matrixAdd(matrixSubtract(matrixAdd(P5, P4), P2), P6);
vector<vector<int>> C12 = matrixAdd(P1, P2); vector<vector<int>>
C21 = matrixAdd(P3, P4);

vector<vector<int>> C22 =
matrixSubtract(matrixSubtract(matrixAdd(P5, P1), P3), P7);
vector<vector<int>> C(n, vector<int>(n));
for (int i = 0; i < k;
++i) { for (int j =
0; j < k; ++j) {
C[i][j] = C11[i][j];
C[i][j + k] = C12[i][j];

C[i + k][j] = C21[i][j];

C[i + k][j + k] = C22[i][j];

return C;
}

int main() { 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>> result = strassenMultiply(A, B); cout <<
"Strassen Matrix Multiplication Result:\n"; for (const auto& row :
result) { for (int val : row) { cout << val << " ";
}

cout << endl;

return 0;

You might also like