Matrix Multiplication Algorithm and Program

by

In this tutorial, we’re going to learn an algorithm for Matrix multiplication along with its Program. Matrix is basically a two-dimensional array that can have any number of rows and any number of columns. Matrix multiplication procedure is not the same as a simple multiplication of numbers but it follows certain distinct rules
which must be followed during matrix multiplication.

Rules for matrix multiplication

  • First, declare two matrix M1 which has r1 rows and c1 columns, and M2 that has r2 rows and c2 columns.
  • To perform successful matrix multiplication r1 should be equal to c2 means the row of the first matrix should equal to a column of the second matrix.
  • Also, define a third matrix of size r2 rows and c1 columns to store the final result.
  • The order of the product of two matrices is distinct. When two matrices are of order r1 x c1 and r2 x c2, the order of product will be r2 x c1.
  • The matrix multiplication does not follow the Commutative Property. It means that, if M1 and M2 are two matrices then the product M1M2 is not equal to the product M2M1 i.e. M1M2 ≠ M2M1.

Matrix Multiplication Algorithm

matrixMultiplication(M1, M2):
 Matrix dimension of M1 is (r1 x c1) and dimension of M2 is (r2 x c2)
 Begin
    if r1 is not equal to c2, then exit
    otherwise define a new matrix M3 of dimension (r1 x c2)
    for i in range 0 to r1, do
       for j in range 0 to c2, do
          for k in range 0 to r2, do
             M3[i, j] = M3[i, j] + (M1[i, k] * M2[k, j])
          done
       done
    done
 End

Matrix Multiplication Algorithm Explanations

Above pseudocode is provided for a basic matrix multiplication algorithm. To analyze its complexity, let’s break down the steps and their respective computational costs.

Algorithm Steps:

  1. Check Dimensions: The algorithm first checks if the number of rows in matrix M1 (r1) is equal to the number of columns in matrix M2 (c2) or not. This step is crucial to perform the matrix multiplication. Matrix multiplication is only possible when r1 == c2 otherwise not. The complexity of this step is O(1) since it’s a single conditional check.
  2. Initialize Result Matrix M3: We will create a new matrix M3 with dimensions r1 x c2. The complexity for initializing this matrix is O(r1 * c2), as it involves setting up a grid of r1 rows and c2 columns.
  3. Perform Multiplication: To Perform matrix multiplication, we are using three for loop:
    • The outer loop runs r1 times.The middle loop runs c2 times.The innermost loop runs r2 (or c1, since c1 == r2) times.
    In each iteration of the innermost loop, the algorithm performs a multiplication and an addition operation: <strong>M3[i, j] = M3[i, j] + (M1[i, k] * M2[k, j])</strong>.

Complexity Analysis:

The time complexity of the algorithm is primarily determined by the nested loops:

  • The outer loop runs r1 times.
  • The middle loop runs c2 times for each iteration of the outer loop.
  • The inner loop runs r2 times for each iteration of the middle loop.

Hence, the total number of iterations for the innermost statement is r1 * c2 * r2. Since each iteration involves a constant amount of work (a multiplication and an addition), the time complexity of the algorithm is O(r1 * c2 * r2).

Space Complexity:

The space complexity of the algorithm is determined by the amount of additional memory it needs. Apart from the input matrices M1 and M2, it only requires space for the output matrix M3, which has dimensions r1 x c2. Therefore, the space complexity is O(r1 * c2).

Conclusion:

  • Time Complexity: O(r1 * c2 * r2)
  • Space Complexity: O(r1 * c2)

This matrix multiplication algorithm is a straightforward implementation with cubic time complexity, which can be computationally expensive for large matrices. Advanced algorithms like Strassen’s algorithm or the Coppersmith-Winograd algorithm can multiply matrices in faster time complexities, though they are more complex to implement.

Matrix Multiplication Program in C

#include<stdio.h> 
int main()
{
  int m, n, p, q, c, d, k, sum = 0;
  int first[10][10], second[10][10], multiply[10][10];
  printf("Enter number of rows and columns of first matrix\n");
  scanf("%d%d", &m, &n);
  printf("Enter elements of first matrix\n");
  for (c = 0; c<m; c++)
    for (d = 0; d <n; d++)
      scanf("%d", &first[d]);
  printf("Enter number of rows and columns of second matrix\n");
  scanf("%d%d", &p, &q);
  printf("Enter elements of second matrix\n");
  for (c = 0; c< p; c++)
      for (d = 0; d < q; d++)
        scanf("%d", &second[d]);
  if (n != p)
        printf("The multiplication isn't possible.\n");
    else
    {
        for (c = 0; c < m; c++) {
            for (d = 0; d < q; d++) {
                for (k = 0; k < p; k++) {
                    sum = sum + first[k]*second[k][d];
                }
                multiply[d] = sum;
                sum = 0;
            }
    }
  
    printf("Product of the matrices:\n");
    for (c = 0; c < m; c++) {
      for (d = 0; d < q; d++)
        printf("%d\t", multiply[d]);
      printf("\n");
    }
  }
}

Output:

Enter elements of first matrix
1
2
3
4
Enter number of rows and columns of second matrix
2
2
Enter elements of second matrix
1
2
3
4
Product of the matrices:
7       10
15      22