El algoritmo de Strassen se usa para la multiplicación de arrays cuadradas, es decir, el orden de las arrays debe ser (N x N). El Algoritmo de Strassen se basa en la técnica de divide y vencerás . En términos más simples, se utiliza para la multiplicación de arrays. El método de multiplicación de arrays de Strassen es un algoritmo típico de divide y vencerás. Sin embargo, volvamos a lo que hay detrás del enfoque divide y vencerás e impleméntalo considerando una ilustración como la siguiente. Por ejemplo: Sean A y B dos arrays, entonces la array resultante C tal que
Array C = Array A * Array B
Considere por ahora que el cálculo matemático de arrays es que se puede concluir por qué entra en juego la implementación de las arrays de Strassen. Supongamos que dos arrays se operan para ser multiplicadas, entonces el enfoque habría sido
- Tome la entrada de dos arrays.
- Compruebe la compatibilidad de la multiplicación de arrays, que es válida solo y solo si el número de filas de la primera array es igual al número de columnas de la segunda array.
- Multiplique la array y asigne la multiplicación de dos arrays a otra array conocida como array resultante.
- Imprime la array resultante.
En el enfoque anterior, se trazan dos supuestos que muestran por qué surge la necesidad del algoritmo de Strassen.
- En primer lugar, la complejidad temporal del algoritmo es O(n 3 ), que es demasiado alta.
- En segundo lugar, la multiplicación de más de dos arrays no solo aumentará la confusión y la complejidad del programa, sino que también aumentará la complejidad del tiempo en consecuencia.
Objetivo:
Volker Strassen es un nombre que publicó su algoritmo para demostrar que la complejidad temporal O(n 3 ) de la multiplicación general de arrays no era óptima. Así se publicó la multiplicación de strings de arrays de Strassen y se redujo la complejidad del tiempo. Este algoritmo es más rápido que la multiplicación de arrays estándar y es útil cuando se calculan numerosas multiplicaciones de arrays grandes en el mundo cotidiano.
Algoritmo de Strassen para la multiplicación de arrays
Paso 1: Tome tres arrays para suponer A, B, C donde C es la array resultante y A y B son arrays que se multiplicarán utilizando el método de Strassen.
Paso 2: divida la array A, B, C en cuatro arrays (n/2) × (n/2) y tome la primera parte de cada una como se muestra a continuación
Paso 3: Use las fórmulas a continuación para resolver la parte 1 de la array
M1:=(A1+A3)×(B1+B2) M2:=(A2+A4)×(B3+B4) M3:=(A1−A4)×(B1+A4) M4:=A1×(B2−B4) M5:=(A3+A4)×(B1) M6:=(A1+A2)×(B4) M7:=A4×(B3−B1) Then, P:=M2+M3−M6−M7 Q:=M4+M6 R:=M5+M7 S:=M1−M3−M4−M5
Paso 4: después de resolver la primera parte, calcule la segunda, la tercera y la cuarta, y además del resultado final, se genera una array multiplicada como resultado, como se muestra en la imagen de arriba.
Paso 5: Imprime la array resultante.
Implementación:
Ejemplo
Java
// Java Program to Implement Strassen Algorithm
// Class Strassen matrix multiplication
public class GFG {
// Method 1
// Function to multiply matrices
public int[][] multiply(int[][] A, int[][] B)
{
// Order of matrix
int n = A.length;
// Creating a 2D square matrix with size n
// n is input from the user
int[][] R = new int[n][n];
// Base case
// If there is only single element
if (n == 1)
// Returning the simple multiplication of
// two elements in matrices
R[0][0] = A[0][0] * B[0][0];
// Matrix
else {
// Step 1: Dividing Matrix into parts
// by storing sub-parts to variables
int[][] A11 = new int[n / 2][n / 2];
int[][] A12 = new int[n / 2][n / 2];
int[][] A21 = new int[n / 2][n / 2];
int[][] A22 = new int[n / 2][n / 2];
int[][] B11 = new int[n / 2][n / 2];
int[][] B12 = new int[n / 2][n / 2];
int[][] B21 = new int[n / 2][n / 2];
int[][] B22 = new int[n / 2][n / 2];
// Step 2: Dividing matrix A into 4 halves
split(A, A11, 0, 0);
split(A, A12, 0, n / 2);
split(A, A21, n / 2, 0);
split(A, A22, n / 2, n / 2);
// Step 2: Dividing matrix B into 4 halves
split(B, B11, 0, 0);
split(B, B12, 0, n / 2);
split(B, B21, n / 2, 0);
split(B, B22, n / 2, n / 2);
// Using Formulas as described in algorithm
// M1:=(A1+A3)×(B1+B2)
int[][] M1
= multiply(add(A11, A22), add(B11, B22));
// M2:=(A2+A4)×(B3+B4)
int[][] M2 = multiply(add(A21, A22), B11);
// M3:=(A1−A4)×(B1+A4)
int[][] M3 = multiply(A11, sub(B12, B22));
// M4:=A1×(B2−B4)
int[][] M4 = multiply(A22, sub(B21, B11));
// M5:=(A3+A4)×(B1)
int[][] M5 = multiply(add(A11, A12), B22);
// M6:=(A1+A2)×(B4)
int[][] M6
= multiply(sub(A21, A11), add(B11, B12));
// M7:=A4×(B3−B1)
int[][] M7
= multiply(sub(A12, A22), add(B21, B22));
// P:=M2+M3−M6−M7
int[][] C11 = add(sub(add(M1, M4), M5), M7);
// Q:=M4+M6
int[][] C12 = add(M3, M5);
// R:=M5+M7
int[][] C21 = add(M2, M4);
// S:=M1−M3−M4−M5
int[][] C22 = add(sub(add(M1, M3), M2), M6);
// Step 3: Join 4 halves into one result matrix
join(C11, R, 0, 0);
join(C12, R, 0, n / 2);
join(C21, R, n / 2, 0);
join(C22, R, n / 2, n / 2);
}
// Step 4: Return result
return R;
}
// Method 2
// Function to subtract two matrices
public int[][] sub(int[][] A, int[][] B)
{
//
int n = A.length;
//
int[][] C = new int[n][n];
// Iterating over elements of 2D matrix
// using nested for loops
// Outer loop for rows
for (int i = 0; i < n; i++)
// Inner loop for columns
for (int j = 0; j < n; j++)
// Subtracting corresponding elements
// from matrices
C[i][j] = A[i][j] - B[i][j];
// Returning the resultant matrix
return C;
}
// Method 3
// Function to add two matrices
public int[][] add(int[][] A, int[][] B)
{
//
int n = A.length;
// Creating a 2D square matrix
int[][] C = new int[n][n];
// Iterating over elements of 2D matrix
// using nested for loops
// Outer loop for rows
for (int i = 0; i < n; i++)
// Inner loop for columns
for (int j = 0; j < n; j++)
// Adding corresponding elements
// of matrices
C[i][j] = A[i][j] + B[i][j];
// Returning the resultant matrix
return C;
}
// Method 4
// Function to split parent matrix
// into child matrices
public void split(int[][] P, int[][] C, int iB, int jB)
{
// Iterating over elements of 2D matrix
// using nested for loops
// Outer loop for rows
for (int i1 = 0, i2 = iB; i1 < C.length; i1++, i2++)
// Inner loop for columns
for (int j1 = 0, j2 = jB; j1 < C.length;
j1++, j2++)
C[i1][j1] = P[i2][j2];
}
// Method 5
// Function to join child matrices
// into (to) parent matrix
public void join(int[][] C, int[][] P, int iB, int jB)
{
// Iterating over elements of 2D matrix
// using nested for loops
// Outer loop for rows
for (int i1 = 0, i2 = iB; i1 < C.length; i1++, i2++)
// Inner loop for columns
for (int j1 = 0, j2 = jB; j1 < C.length;
j1++, j2++)
P[i2][j2] = C[i1][j1];
}
// Method 5
// Main driver method
public static void main(String[] args)
{
// Display message
System.out.println(
"Strassen Multiplication Algorithm Implementation For Matrix Multiplication :\n");
// Create an object of Strassen class
// in he main function
GFG s = new GFG();
// Size of matrix
// Considering size as 4 in order to illustrate
int N = 4;
// Matrix A
// Custom input to matrix
int[][] A = { { 1, 2, 3, 4 },
{ 4, 3, 0, 1 },
{ 5, 6, 1, 1 },
{ 0, 2, 5, 6 } };
// Matrix B
// Custom input to matrix
int[][] B = { { 1, 0, 5, 1 },
{ 1, 2, 0, 2 },
{ 0, 3, 2, 3 },
{ 1, 2, 1, 2 } };
// Matrix C computations
// Matrix C calling method to get Result
int[][] C = s.multiply(A, B);
// Display message
System.out.println(
"\nProduct of matrices A and B : ");
// Iterating over elements of 2D matrix
// using nested for loops
// Outer loop for rows
for (int i = 0; i < N; i++) {
// Inner loop for columns
for (int j = 0; j < N; j++)
// Printing elements of resultant matrix
// with whitespaces in between
System.out.print(C[i][j] + " ");
// New line once the all elements
// are printed for specific row
System.out.println();
}
}
}
Strassen Multiplication Algorithm Implementation For Matrix Multiplication : Product of arrays A and B : 7 21 15 22 8 8 21 12 12 17 28 22 8 31 16 31
Complejidad temporal del método de Strassen
Por análisis, la función de complejidad temporal se puede escribir como:
T(N) = 7T(N/2) + O(N2)
Resolviendo esto usando el Teorema Maestro obtenemos:
T(n)=O(nlog7)
Por lo tanto, el tiempo Complejidad del algoritmo de Strassen para la multiplicación de arrays se deriva como:
O(nlog7) = O (n2.81)
O(n 3 ) Vs O(n 2.81)
Publicación traducida automáticamente
Artículo escrito por jagroopofficial y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA