All about Matrix Chain Multiplication || EASY
Vidhu
20852

Question : If a chain of matrices is given, we have to find the minimum number of the correct sequence of matrices to multiply.

  • The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.
  • Note: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) = ....
  • 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 parenthesization requires less number of operations.
  • Note ; We'll be given an array arr[ ] which represents the chain of matrices such that the ith matrix arr[i] is of dimension arr[i-1] x arr[i].
  • That's why we start out 'k' i.e partition from 'i' =1 so that arr[ 1] is of dimentions arr[1-1] * arr[1] else we'll get index out of bound error Eg arr[0-1] * arr[0] is not possible
  • So first half of the array is from i to k & other half is from k+1 to j
  • Also we need to find the cost of multiplication of these 2 resultant matrixes (first half & second half) which is nothing but arr[i-1] * arr[k] * arr[j]

Recursion

Here is the recursive algo :

image

Code

    int solve(int i, int j,int arr[])
    {
        if(i>=j)return 0;

        int ans=INT_MAX;
        for(int k=i;k<=j-1;k++)
        {
            int tempAns = solve(i,k,arr) + solve(k+1,j,arr)
                          + arr[i-1]*arr[k]*arr[j];
            
            ans=min(ans,tempAns);                        
        }
        return ans;
    }
    int matrixMultiplication(int N, int arr[])
    {
        return solve(1,N-1,arr);
    }

  • The time complexity of the above naive recursive approach is exponential. Observe that the above function computes the same subproblems again and again.

  • Let us saywe are given an array of 5 elements that means we are given N-1 i.e 4 matrixes .See the following recursion tree for a matrix chain of size 4.
    image

  • There are so many overlapping subproblems . Let's optimize it using DP !!

Memoization

  • Just adding a few lines to the above code, we can reduce time complexity from exponential to cubic
int dp[501][501];
    
    int solve(int i, int j,int arr[])
    {
        if(i>=j)return 0;
        
        if(dp[i][j]!=-1)
        return dp[i][j];

        int ans=INT_MAX;
        for(int k=i;k<=j-1;k++)
        {
            int tempAns = solve(i,k,arr) + solve(k+1,j,arr)
                          + arr[i-1]*arr[k]*arr[j];
            
            ans=min(ans,tempAns);
                          
        }
        return dp[i][j] = ans;
    }
    int matrixMultiplication(int N, int arr[])
    {
        memset(dp,-1,sizeof(dp));
        return solve(1,N-1,arr);
    }

Bottom Up DP

  • It's a bit tricky but if you got the above logic then you woudn't face any issues. I stil, prefer the Momoization
int MatrixChainOrder(int arr[], int n)
{
 
    /* For simplicity of the program, one
    extra row and one extra column are
    allocated in arr[][]. 0th row and 0th
    column of arr[][] are not used */
    int dp[n][n];
 
    int i, j, k, L, q;
 
    /* dp[i, j] = Minimum number of scalar
    multiplications needed to compute the
    matrix A[i]A[i+1]...A[j] = A[i..j] where
    dimension of A[i] is arr[i-1] x arr[i] */
 
    // cost is zero when multiplying
    // one matrix.
    for (i = 1; i < n; i++)
        dp[i][i] = 0;
 
    // L is chain length.
    for (L = 2; L < n; L++)
    {
        for (i = 1; i < n - L + 1; i++)
        {
            j = i + L - 1;
            dp[i][j] = INT_MAX;
            for (k = i; k <= j - 1; k++)
            {
                // q = cost/scalar multiplications
                q = dp[i][k] + dp[k + 1][j]
                    + arr[i - 1] * arr[k] * arr[j];
                if (q < dp[i][j])
                    dp[i][j] = q;
            }
        }
    }
 
    return dp[1][n - 1];
}
Comments (10)