(CS application: algorithms) One of the properties of matrix multiplication is t
ID: 3881855 • Letter: #
Question
(CS application: algorithms) One of the properties of matrix multiplication is that it is associative. That is, if we have matrices A, B, and C with dimensions that allow them to be multiplied as ABC, then A(BC) (AB)C. However, the amount of multiplications and additions may not be identical for both orderings (a) If A has dimensions 3 × 2, B has dimensions 2 × 4, and C has dimensions 4 x 5, then what is the total number of multiplications and the total number of additions for each of the two orderings? (b) Also, if A, B, and C have dimensions mx n, n × p, and p × q, respectively, what are the formulae for the number of multiplications and additions for each ordering? You should show that you derived these formulae. You should produce separate values and formulae for the multiplications and additions; don't combine them. For example, you might find that A(BC) with the dimensions given above requires 100 multiplications and 80 additions with the generic formula for multiplications being mnpq and the generic formula for additions being mn+p.Explanation / Answer
First let us derive a general formula for number of additions and multiplication while multiplying 2 matrices.
Consider 2 matrices A and B, with dimensions l x m and m x n respectively.
For each entry in the resulant product matrix, we multiply m elements in a row of matrix A with m elements in a column of matrix and add those m products.
Hence for a single entry in the product of matrix A and B, we perform m multiplication (m elements in row of A multiplied by m elements in column of B, Hence total multiplications = m) and then while adding those m products, we perform m-1 additions(To add 2 elements, we need 1 addition, for 3 elements we need 2 addition, hence for m elements, we need m-1 additions).
Hence each entry in the product of matrix A and B requires m multiplication and m-1 additions.
The dimension of product matrix AB is l x n, which means there are l*n entries in the product matrix.
Hence total multiplications = l*n*m (For 1 entry, its m so for l*n entries, it will be l*m*n)
and total addition = l*n*(m-1)
Now with above formula in our hand, we can solve the given problem.
a)
A has dimension 3 x 2, B has dimension 2 x 4 and C has dimension 4 x 5
First consider the case A(BC)
B is multiplied with C first. B has dimension 2 x 4, C has 4 x 5. In our above derived formula, l = 2, m = 4 and n = 5.
Hence total multiplications for BC = 2*5*4 = 40
Total addition for BC = 2*5*3 = 30
So for BC, we get 40 multiplication and 30 addition.
Now BC has dimension 2 x 5.
A has dimension 3 x 2. In our above formula, we substitute l = 3, m = 2 and n = 5.
Hence total multiplications = 3*5*2 = 30
Total addition = 3*5*1 = 15
We add the results of both the parts to get total number of multiplications and addition for A(BC)
Total multiplication = 30 + 40 = 70
Total addition = 15 + 30 = 45.
Now consider the case (AB)C. First we will multiply A and B.
Dimension of A and B are 3 x 2 and 2 x 4. Hence l = 3, m = 2 and n = 4 in above formula.
Multiplications = 3*4*2 = 24
Addition = 3*4*1 = 12
Now AB has dimension 3 x 4. and C has dimension 4 x 5.
We substitute l = 3, m = 4 and n = 5 in above formula
Multiplication = 3*5*4 = 60
Addition = 3*5*3 = 45
Adding results of both parts, we get
Total multiplication = 60 + 24 = 84
Total additions = 45 + 12 = 57
b)
A has dimension m x n, B has dimension n x p and C has dimension p x q
First consider the order A(BC)
While multiplying B and C, we substitute l = n, m = p and n = q
Total multiplications = n*q*p
Total additions = n*q*(p-1)
Now BC has dimension n x q
A has dimension m x n
In above formula, we substitute l = m, m = n, n = q
Multiplications = m*q*n
Additions = m*q*(n-1)
Adding the results of both parts, we get:
Total multiplications = m*q*n + n*q*p = n*q*(m + p)
Total additions = m*q*(n-1) + n*q*(p-1) = q*(m*n - m + p*n - n )
Now consider the order (AB)C
A has m x n, B has n x p
Substituting l = m, m = n and n = p, we get:
Multiplications = m*p*n
Additions = m*p*(n-1)
Now multiplying (AB) with C
AB will have dimensions m x p. C has dimension p x q
Substitutins l = m, m = p, n = q, we get:
Multiplications = m*q*p
Additions = m*q*(p-1)
Adding results from both the parts, we get:
Total multiplications = m*q*p + m*p*n = m*p*(q + n)
Total Additions = m*q*(p-1) + m*p*(n-1) = m*(q*p - q + p*n - p)
Please give this solution a thumbs up if you find it helpful and comment if you have and doubts in it.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.