Matrix Multiplication – Divide & Conquer Approach
.
Divide and conquer is a popular approach in the field of algorithm design and analysis. It involves breaking down a big problem into smaller, more manageable subproblems, solving them independently, and then combining the solutions to obtain the final result. Matrix multiplication also refers to this approach.
.
The Divide & Conquer has three terms in it.
.
Divide–Â The first step is to divide the problem into smaller, more manageable subproblems. This is usually done by breaking the problem into two or more similar but smaller instances of the same problem.
Conquer– Conquer means ‘to win’ or ‘to solve’. Once the problem is divided, each smaller subproblem is solved easily and independently.
Combine- Finally, the solutions obtained from the smaller subproblems are combined or merged to obtain the solution to the original problem. This step involves taking the solutions from the subproblems and integrating them to produce the final output.
The divide and conquer approach are particularly useful when solving complex problems that can be divided into smaller, more manageable parts. By breaking the problem down, we can focus on solving each part independently, which can make the overall problem easier to understand and solve.
It is a powerful technique used in various algorithms and can help us solve complex problems effectively.
This approach is commonly used in various algorithms and applications, such as sorting algorithms like Merge Sort and Quick Sort, searching algorithms like Binary Search, and problems related to computational geometry and matrix multiplication.
.
Matrix Multiplication
Consider two matrices A and B with 4*4 dimensions each.
The matrix multiplication of the above two matrices is matrix C.
Where
C11 = (a11*b11) + (a12*b21) + (a13*b31) + (a14*b41)
C12 = (a11*b12) + (a12*b22) + (a13*b32) + (a14*b42)
C21 = (a21*b11) + (a22*b21) + (a23*b31) + (a24*b41)
C22 = (a21*b12) + (a22*b22) + (a23*b32) + (a24*b42)
and so on…
Now, lets look at the divide and conquer approach to multiply two matrices.
Take two submatrices from the above two matrices A and B each.
And the matrix multiplication of the two 2*2 matrices A11 and B11 is
Also,
So, if you observe, this result toÂ
C11 = a11 x b11 + a12 x b21 + a13 x b31 + a14 x b41
C12 = a11 x b12 + a12 x b22 + a13 x b32 + a14 x b42
C13 = a11 x b13 + a12 x b23 + a13 x b33 + a14 x b43
C14 = a11 x b14 + a12 x b24 + a13 x b34 + a14 x b44
which finally become
So, the idea is to recursively divide n*n matrices into n/2*n/2 matrices until they are small enough to be multiplied in the naïve (simple) way.
More specifically into 8 multiplications and 4 additions.
In this example,
From master’s theorem, we can analyse its time complexity is O(n3), where n is the size of matrices. This means that as the size of the matrices increases, the time required to multiply them grows significantly. For large matrices, this can become computationally expensive and time-consuming.
Strassen’s algorithm, on the other hand, has a time complexity of approximately O(n^log2(7)), which is faster than the naive algorithm for large matrices. The algorithm achieves this improvement by reducing the number of individual multiplications required to compute the matrix product.
In the next post of design and analysis of algorithm, we will discuss the working of Strassen’s algorithm.
Â
Advantage of Matrix multiplication
- The matrix multiplication is straightforward and does not involve any additional overhead in terms of recursion or extra computations, while, Strassen’s algorithm introduces additional overhead due to the recursive calls and bookkeeping required to split the matrices and combine the intermediate products.
- It is made for humans and Strassen’s algorithm is made for computers. If the user uses Strassen’s algorithm, then he may face a lot of complexity because the algorithm used is for large matrices.
Disadvantage of Matrix Multiplication
- Time complexity is very high O(n3).
Test Yourself
Q1- Explain the three steps involved in the divide and conquer approach.
The three steps in the divide and conquer approach are:
Divide: Break down the problem into smaller subproblems.
Conquer: Solve each subproblem independently.
Combine: Merge the solutions of the subproblems to obtain the final result.
Q2- Why is the divide and conquer approach useful for solving complex problems?
The divide and conquer approach breaks down complex problems into smaller, more manageable subproblems. This makes the problem easier to understand and solve, as we can focus on solving each subproblem independently. It also allows for parallelism and can lead to improved time and space efficiency.
Q3- Give an example of a problem that can be solved using the divide and conquer approach.
One example is the Merge Sort algorithm, which uses the divide and conquer approach to sort a list of elements. The problem of sorting the entire list is divided into smaller subproblems of sorting two halves of the list, and then the sorted halves are merged together to obtain the final sorted list.
Q4- How does matrix multiplication fit into the divide and conquer paradigm?
Matrix multiplication can be solved using the divide and conquer approach by recursively dividing the matrices into smaller submatrices until they are small enough to be multiplied using the standard multiplication algorithm. The resulting submatrix multiplications are then combined to obtain the final matrix multiplication.
Q5- What is the advantage of the matrix multiplication algorithm compared to Strassen’s algorithm?
The advantage of the matrix multiplication algorithm is its simplicity and straightforward implementation. It does not involve additional overhead in terms of recursion or extra computations. However, it has a higher time complexity compared to Strassen’s algorithm for large matrices.
Q6- What is the time complexity of the matrix multiplication algorithm?
The time complexity of the matrix multiplication algorithm is O(n^3), where n is the size of the matrices being multiplied. As the size of the matrices increases, the time required to multiply them grows significantly.
Q7- How does Strassen’s algorithm improve the time complexity of matrix multiplication?
Strassen’s algorithm reduces the number of individual multiplications required to compute the matrix product. It achieves this improvement by recursively splitting the matrices into smaller submatrices and combining the intermediate products. The time complexity of Strassen’s algorithm is approximately O(n^log2(7)), which is faster than the naive algorithm for large matrices.
Q8- What is the disadvantage of the matrix multiplication algorithm?
The main disadvantage of the matrix multiplication algorithm is its high time complexity of O(n^3), which can become computationally expensive and time-consuming for large matrices. It is less efficient compared to Strassen’s algorithm for large matrix sizes.
