Last Updated: 14 Mar, 2021
Matrix Multiplication
Moderate
Asked in companies
Ninja has been given two sparse matrices ‘MAT1’ and ‘MAT2’ of integers having size ‘N’ x ‘M’ and ‘M’ x ‘P’, respectively.
A sparse matrix is a matrix that contains very few non-zero elements.
Ninja has to find the matrix formed by the multiplication of ‘MAT1’ and ‘MAT2’. As Ninja is busy with some other tasks so he needs your help. Can you help Ninja to find the matrix formed by the multiplication of ‘MAT1’ and ‘MAT2’?
Note: The number of columns in ‘MAT1’ i.e ‘M’ is equal to the number of rows in ‘MAT2’ i.e ‘M’. It means we can always multiply ‘MAT1’ with ‘MAT2’.
For example:
For the ‘MAT1’ and ‘MAT2’ given below, ‘MAT3’ is the matrix formed by multiplying ‘MAT1’ and ‘MAT2’.
1. MAT3[0][0] = MAT1[0][0] * MAT2[0][0] + MAT1[0][1] * MAT2[1][0] ie. 2 * 1 + 1 * 4 = 6
2. MAT3[1][0] = MAT1[1][0] * MAT2[1][0] + MAT1[1][1] * MAT2[1][0] ie. 0 * 6 + 0 * 4 = 0
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first line of each test case contains four space-separated integers ‘N’, ‘M’, ‘M’, ‘P’ where ‘N’ and ‘M’ representing the number of rows and columns of ‘MAT1’ respectively and ‘M’ and ‘P’ representing the number of rows and columns of ‘MAT2’ respectively.
The next ‘N’ lines of each test case contain ‘M’ single space-separated integers denoting the values of ‘MAT1’. Then the next ‘M’ lines contain ‘P’ single space-separated integers denoting the values of ‘MAT2’
Output Format :
For each test case, return the matrix ‘MAT3’ which will be formed by multiplying ‘MAT1’ and ‘MAT2’.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= ‘T’ <= 100
1 <= ‘N’, ‘M’ and ‘P’ <= 100
-10^5 <= ‘MAT1[i][j]’ and ‘MAT2[i][j]’ <= 10^5
Time limit: 1 sec
Approaches
- We can get the matrix ‘MAT3’ using 3 nested loops.
- To get the (‘i’, ‘j’) cell element of the matrix ‘MAT3’, we need to multiply each element of the ‘i’th row of ‘MAT1’ with the ‘j’’th column of the matrix ‘MAT2’ and finally add all the results.
Here is the complete algorithm:
- Make a 2D array/list ‘MAT3’ having ‘N’ rows and ‘P’ columns.
- Run a for loop from ‘i’ = 0 to ‘i’ < ‘N’ and for each ‘i’ do the following:
- Run a for loop from ‘j’ = 0 to ‘j’ < ‘P’ and for each ‘j’ do the following:
- Make a variable ‘sum’ = 0.
- Run a for loop from ‘k’ = 0 to ‘k’ < ‘M’ and for each ‘k’ do the following:
- ‘sum’ = ‘sum’ + ‘MAT1[i][k]’ * ‘MAT2[k][j]’.
- Update ‘MAT3[i][j]’ = ‘sum’.
- Run a for loop from ‘j’ = 0 to ‘j’ < ‘P’ and for each ‘j’ do the following:
- Return ‘MAT3’.
- We can optimize the above approach because in ‘MAT1’ and ‘MAT2’ we have more zero elements than non-zero as both the matrices are sparse matrices.
- From the formula: Sum(MAT1_ik * MAT2_kj) -> MAT3_ij, we can see that when ‘MAT1_ik’ is 0, there is no need to compute ‘MAT2_kj’. So we switch the inner two loops and add a 0-checking condition.
Here is the complete Algorithm:
- Make a 2D array ‘C’ having ‘N’ rows and ‘P’ columns.
- Run a for loop from ‘i’ = 0 to ‘i’ < ‘N’ and for each ‘i’ do the following:
- Run a for loop from ‘k’ = 0 to ‘k’ < ‘M’ and for each ‘j’ do the following:
- If ‘MAT1[i][k]’ is not 0 then do the following:
- Run a for loop from ‘j’ = 0 to ‘j’ < ‘P’ and for each ‘j’ do the following:
- ‘MAT3[i][j]’ = ‘MAT3[i][j]’ + ‘MAT1[i][k]’ * ‘MAT2[k][j]’
- Run a for loop from ‘j’ = 0 to ‘j’ < ‘P’ and for each ‘j’ do the following:
- If ‘MAT1[i][k]’ is not 0 then do the following:
- Run a for loop from ‘k’ = 0 to ‘k’ < ‘M’ and for each ‘j’ do the following:
- Return ‘MAT3’.