UNIT II -Divide and Conquer:

Matrix Multiplication and Related Operations; Strassen’s Matrix Multiplication

✔ Introduction: 

    Matrix multiplication and related operations are fundamental operations in linear algebra, widely used in various fields such as computer science, engineering, physics, and data analysis. Strassen's Matrix Multiplication is a specialized algorithm that leverages the Divide and Conquer technique to efficiently multiply two matrices. In this article, we will explore Matrix Multiplication, Strassen's algorithm, provide examples, discuss characteristics, advantages, disadvantages, and include necessary diagrams.

✔ Matrix Multiplication: 

    Matrix multiplication is an essential operation that combines two matrices to produce a new matrix. The result matrix's dimensions are determined by the number of rows and columns of the input matrices.

Example: 

Consider two matrices:

Matrix A: |1 2| |3 4|

Matrix B: |5 6| |7 8|

Matrix multiplication of A and B will result in a new matrix C:

Matrix C: |15+27 16+28| |35+47 36+48|

Matrix C: |19 22| |43 50|

👉 Characteristics:The number of columns in the first matrix must be equal to the number of rows in the second matrix for matrix multiplication to be valid.
The time complexity of standard matrix multiplication is O(n^3), where n is the number of rows or columns of the matrices.

👉  Advantages:

Versatility: Matrix multiplication is a fundamental operation used in various mathematical and engineering applications.
Representations: Matrices are used to represent and solve systems of linear equations and transform objects in computer graphics.
Signal Processing: Matrix multiplication plays a significant role in digital signal processing and machine learning algorithms.

👉 Disadvantages:

Complexity: The time complexity of standard matrix multiplication is relatively high, which can be a concern for large matrices.
Memory Requirements: Matrix multiplication may require additional memory to store the resulting matrix, especially for large datasets.

Strassen's Matrix Multiplication: Strassen's algorithm is a Divide and Conquer approach that improves the efficiency of matrix multiplication by dividing the matrices into smaller submatrices and recursively computing their products using fewer multiplications.

Example: Let's consider the same matrices A and B as before:

Matrix A: |1 2| |3 4|

Matrix B: |5 6| |7 8|

Step 1: Divide the matrices into four submatrices: 

A11 = |1|, A12 = |2| |3| |4|

B11 = |5|, B12 = |6| |7| |8|


Step 2: Compute seven products recursively: 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)

Step 3: Combine the products to get the final result: C11 = P5 + P4 - P2 + P6 C12 = P1 + P2 C21 = P3 + P4 C22 = P5 + P1 - P3 - P7

Matrix C: |19 22| |43 50|

Characteristics:Time Complexity: Strassen's algorithm has a time complexity of O(n^log2(7)) ≈ O(n^2.81), which is more efficient than standard matrix multiplication.
Divide and Conquer: Strassen's algorithm divides the matrix multiplication problem into smaller subproblems, recursively computes the products, and combines the results.

Advantages:Improved Efficiency: Strassen's algorithm reduces the number of multiplications required, resulting in improved efficiency for large matrices.
Parallelization: The Divide and Conquer nature of Strassen's algorithm allows for easy parallelization of matrix multiplication, enhancing performance on multi-core systems.

Disadvantages:Overhead: Strassen's algorithm requires additional addition and subtraction operations, making it less practical for small matrices where the overhead might outweigh the benefits.
Limited Applicability: Strassen's algorithm is more efficient for large matrices, but for small matrices, the standard algorithm might still be faster.

Diagram: Below is a diagram illustrating Strassen's Matrix Multiplication process for the example matrices:

Matrix A: |1 2| |3 4|

Matrix B: |5 6| |7 8|

Step 1: Divide the matrices into submatricesmarkdown
A11 = |1|, A12 = |2| B11 = |5|, B12 = |6| |3| |4| |7| |8|


Step 2: Compute seven products recursively 
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)


Step 3: Combine the products to get the final result 
C11 = P5 + P4 - P2 + P6 C12 = P1 + P2 C21 = P3 + P4 C22 = P5 + P1 - P3 - P7


Matrix C: |19 22| |43 50|