Explain the strassen’s multiplication technique?

I. Introduction

Strassen’s multiplication technique is a revolutionary method proposed by Volker Strassen in 1969 for matrix multiplication. It is an efficient algorithm that performs matrix multiplication faster than the standard method. The standard matrix multiplication technique has a time complexity of O(n^3), while Strassen’s multiplication technique reduces this to approximately O(n^2.81), making it a significant improvement for large matrices.

II. Strassen’s Multiplication Technique

The basic concept of Strassen’s multiplication technique is to divide the given matrices into smaller sub-matrices, perform multiplication on these sub-matrices, and then combine the results to get the final matrix. This technique is applicable for matrices of order 2^n x 2^n. For matrices of other orders, they can be padded with zeros to make them of order 2^n x 2^n.

The formula used in Strassen’s multiplication technique is derived from the standard matrix multiplication formula. However, instead of performing eight multiplications for each element of the resulting matrix, Strassen’s technique performs only seven multiplications.

The steps involved in Strassen’s multiplication technique are as follows:

1. Divide the given matrices into sub-matrices: The given matrices A and B are divided into four sub-matrices each.

2. Calculate the seven products of the sub-matrices: Seven products P1, P2, P3, P4, P5, P6, and P7 are calculated using the sub-matrices.

3. Combine these products to get the final matrix: The final matrix C is obtained by combining these products.

A diagram is necessary to illustrate these steps.

III. Detailed Explanation of Strassen’s Multiplication Technique

1. Divide the given matrices into sub-matrices: Given two matrices A and B of order 2^n x 2^n, divide them into four sub-matrices each of order 2^(n-1) x 2^(n-1).

2. Calculate the seven products of the sub-matrices: The seven products P1 to P7 are calculated using the following formulas:

   P1 = A11 * (B12 - B22)

   P2 = (A11 + A12) * B22

   P3 = (A21 + A22) * B11

   P4 = A22 * (B21 - B11)

   P5 = (A11 + A22) * (B11 + B22)

   P6 = (A12 - A22) * (B21 + B22)

   P7 = (A11 - A21) * (B11 + B12)

3. Combine these products to get the final matrix: The final matrix C is obtained by combining these products using the following formulas:

   C11 = P5 + P4 - P2 + P6

   C12 = P1 + P2

   C21 = P3 + P4

   C22 = P5 + P1 - P3 - P7

IV. Example of Strassen’s Multiplication Technique

Let's take an example of two 2x2 matrices A and B:

A = | 1 3 | B = | 6 8 | | 7 5 | | 4 2 |

Applying Strassen’s multiplication technique, we get:

P1 = 1 * (8 - 2) = 6 P2 = (1 + 3) * 2 = 8 P3 = (7 + 5) * 6 = 72 P4 = 5 * (4 - 6) = -10 P5 = (1 + 5) * (6 + 2) = 48 P6 = (3 - 5) * (4 + 2) = -12 P7 = (1 - 7) * (6 + 8) = -84

The final matrix C is:

C = | 48 + (-10) - 8 + (-12) 6 + 8 | = | 18 14 | | 72 + (-10) 48 + 6 - 72 - (-84) | | 62 66 |

V. Comparison of Strassen’s Multiplication Technique with Standard Matrix Multiplication

The standard matrix multiplication technique involves multiplying each element of the first matrix with each element of the second matrix and adding the products to get the resulting matrix. This involves n^3 multiplications and n^3 - n^2 additions, leading to a time complexity of O(n^3).

On the other hand, Strassen’s multiplication technique involves only seven multiplications and 18 additions, leading to a time complexity of approximately O(n^2.81). This makes Strassen’s technique more efficient for large matrices.

However, Strassen’s technique has a higher space complexity due to the need to store the intermediate products. It also involves more complex calculations, making it less suitable for small matrices or matrices with special properties.

VI. Conclusion

Strassen’s multiplication technique is a significant advancement in the field of algorithm analysis and design. It provides a more efficient method for matrix multiplication, especially for large matrices. However, it also has its limitations, such as higher space complexity and complexity of calculations. Despite these limitations, Strassen’s multiplication technique remains a valuable tool in the field of computer science and mathematics.

Summary

Strassen’s multiplication technique is an efficient algorithm for matrix multiplication that reduces the time complexity from O(n^3) to approximately O(n^2.81). It involves dividing the matrices into sub-matrices, calculating seven products of these sub-matrices, and combining them to obtain the final matrix. Strassen’s technique is more efficient for large matrices but has higher space complexity and is less suitable for small matrices or matrices with special properties.

Analogy

Strassen’s multiplication technique is like breaking a big task into smaller sub-tasks, performing these sub-tasks separately, and then combining the results to get the final output. It's similar to dividing a large group of people into smaller teams, assigning different tasks to each team, and then combining their work to achieve a common goal.