(CS application: algorithms) One of the properties of matrix multiplication is t
ID: 3028006 • 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 × 5, then what is the total number of multiplications and the total num ber of additions for each of the two orderings? (b) Also, if A , B , and C have dimensions m × n , n × p , and p × q , respectively, what are the formulae for the number of multiplications and additions fo r each ordering? You should show that you derived these formulae. You should produce separate values and formulae for the mult iplications 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 gene ric formula for multiplications being mn + pq and the generic formula for additions being m + n + p
Explanation / Answer
a.)
A(BC) :
i ) Additions and multiplications in BC :
The number of additions and multiplications in an inner product of vectors of length 'd' are (d-1, d).
the number of additions and multiplications in multiplication of each row of B with each coloumn of C are (3, 4).
the total number of additions and multiplications in multiplication of each row of B with all coloumns of C are
5(3,4) = (15, 20).
the total number of additions and multiplications in multiplication of all rows of B with all coloumns of C are
2(15,20) = (30, 40).
ii ) Additions and multiplications in A and BC :
Now the matrix BC has a dimensions 2 × 5. Now we need to find the additions and multiplications in A and BC.
the number of additions and multiplications in multiplication of each row of A with each coloumn of BC are (1, 2).
the total number of additions and multiplications in multiplication of each row of A with all coloumns of BC are
5(1,2) = (5, 10).
the total number of additions and multiplications in multiplication of all rows of A with all coloumns of BC are
3(5,10) = (15, 30).
The number of additions and multiplications in A(BC) is (30, 40) + (15,30) = (45, 70).
(AB)C :
i ) Additions and multiplications in AB :
the number of additions and multiplications in multiplication of each row of A with each coloumn of B are (1, 2).
the total number of additions and multiplications in multiplication of each row of A with all coloumns of B are
4(1,2) = (4, 8).
the total number of additions and multiplications in multiplication of all rows of A with all coloumns of B are
3(4,8) = (12, 24).
ii ) Additions and multiplications in AB and C :
Now the matrix AB has a dimensions 3 × 4. Now we need to find the additions and multiplications in AB and C.
the number of additions and multiplications in multiplication of each row of AB with each coloumn of C are (3, 4).
the total number of additions and multiplications in multiplication of each row of AB with all coloumns of C are
5(3,4) = (15, 20).
the total number of additions and multiplications in multiplication of all rows of AB with all coloumns of C are
3(15,20) = (45, 60).
The number of additions and multiplications in (AB)C is (12, 24) + (45,60) = (57, 84).
b.)
A(BC) :
i ) Additions and multiplications in BC :
the number of additions and multiplications in multiplication of each row of B with each coloumn of C are (p-1, p).
the total number of additions and multiplications in multiplication of each row of B with all coloumns of C are
q(p-1,p) = (q(p-1), pq).
the total number of additions and multiplications in multiplication of all rows of B with all coloumns of C are
n(q(p-1), pq). = (nq(p-1), npq ).
ii ) Additions and multiplications in A and BC :
Now the matrix BC has a dimensions n × q. Now we need to find the additions and multiplications in A and BC.
the number of additions and multiplications in multiplication of each row of A with each coloumn of BC are (n-1, n).
the total number of additions and multiplications in multiplication of each row of A with all coloumns of BC are
q(n-1, n) = (q(n-1), nq).
the total number of additions and multiplications in multiplication of all rows of A with all coloumns of BC are
m(q(n-1), nq). = (mq(n-1), mqn).
The number of additions and multiplications in A(BC) is
(nq(p-1), npq )+ (mq(n-1), mqn) = (qn(p-1)+qm(n-1)), nqp+nqm)).
(AB)C :
i ) Additions and multiplications in AB :
the number of additions and multiplications in multiplication of each row of A with each coloumn of B are (n-1, n).
the total number of additions and multiplications in multiplication of each row of A with all coloumns of B are
p(n-1,n) = (p(n-1), pn).
the total number of additions and multiplications in multiplication of all rows of A with all coloumns of B are
m (p(n-1), pn)=(mp(n-1), mpn).
ii ) Additions and multiplications in AB and C :
Now the matrix AB has a dimensions m × p. Now we need to find the additions and multiplications in AB and C.
the number of additions and multiplications in multiplication of each row of AB with each coloumn of C are (p-1, p).
the total number of additions and multiplications in multiplication of each row of AB with all coloumns of C are
q(p-1, p) = (q(p-1), qp).
the total number of additions and multiplications in multiplication of all rows of AB with all coloumns of C are
m(q(p-1), qp) = (mq(p-1), mqp)
The number of additions and multiplications in (AB)C is
(mp(n-1), mpn) + (mq(p-1), mqp) = (mpn+mqp, mp(n-1)+mq(p-1)).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.