14-08-2012, 02:31 PM
Matrix Chain Multiplication
Matrix.docx (Size: 40.22 KB / Downloads: 40)
INTRODUCTION:-
MATRIX CHAIN MULTIPLICATION :-
The matrix chain multiplication problem involves a series of operations to be performed. Matrix chain multiplication is an optimization problem that can be solved using dynamic programming. Given a sequence of matrices, we want to find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.
We have many options because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result will be the same. For example, if we had four matrices A, B,C, and D, we would have:
(ABC)D = (AB)(CD) = A(BCD) = A(BC)D = ..
However, the order in which we parenthesize the product affects the number of simple arithmetic operations needed to compute the product, or the efficiency. For example, suppose A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,
(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.
Clearly the first method is the more efficient. Now that we have identified the problem, how do we determine the optimal parenthesization of a product of n matrices? We could go through each possible parenthesization (brute force), but this would require time exponential in the number of matrices, which is very slow and impractical for large n. The solution, as we will see, is to break up the problem into a set of related sub problems. By solving sub problems one time and reusing these solutions many times, we can drastically reduce the time required. This is known as Dynamic programming. The Dynamic approach gives the optimal sequence of operations for the given problem.
Complexity Analysis:-
Clearly, the space complexity of this procedure Ο(n2). Since the tables m and s require Ο(n2) space. As far as the time complexity is concern, a simple inspection of the for-loop(s) structures gives us a running time of the procedure. Since, the three for-loops are nested three deep, and each one of them iterates at most n times (that is to say indices L, i, and j takes on at most n − 1 values). Therefore, The running time of this procedure is Ο(n3).