Mathematical Foundation of Computer Science

DHARM

74 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

3.7 Matrix Multiplication........................................................................................................

Let A and B are two n × n matrices and there product is another n × n matrix C, i.e.,

C(I, K) =

j

n

=

∑

1

A(I, J)* B(J, K) ; (3.33)

(where 1 ≤ I ≤ n and 1 ≤ K ≤ n)
From the equation (3.33), computation of each C(I,K) requires n multiplications and
(n – 1) additions. Thus, computation of all terms of matrix C required a total of n^2 .n + n^2 .(n – 1)
operations. Therefore the complexity of such straight forward matrix multiplication method is
of order θ(n^3 ).
Let us assume n is a power of two viz. n = 1, 2, 4, 8,....... If n = 1 then we have single
element matrices A and B to multiply and we obtain matrix C of single element. Otherwise (n

1), we can divide the matrix A, B and C into 4 submatrices of each size n/2 × n/2 (since n is a
power of 2) say Ai’s, Bi’s and Ci’s; for 1 ≤ i ≤ 4.

AA

AA

12

3 4

F

H

GG

I

K

JJ ∗

BB

BB

12

3 4

F

H

GG

I

K

JJ =

CC

CC

12

3 4

F

H

GG

I

K

JJ

where C 1 = A 1 B 1 + A 2 B 2
C 2 = A 1 B 2 + A 2 B 4
C 3 = A 3 B 1 + A 4 B 3
C 4 = A 3 B 2 + A 4 B 4
The computations of all Ci’s (for i = 1 to 4) required 8 multiplications and 4 additions of
n/2 × n/2 matrices using divide-&-conquer paradigm.
Now we discuss a better scheme for matrix multiplication known as Stressman’s method
that involves 7 multiplications and 18 additions/subtractions operations of n/2 × n/2 matrices.
The seven smaller products are matrices M, N, O, P, Q, R and S where,
M = A 1 (B 2 – B 4 )
N = A 4 (B 3 – B 1 )
O = B 1 (A 3 + A 4 )
P = B 4 (A 1 + A 2 )
Q = (A 3 – A 1 ) (B 2 – B 4 )
R = (A 2 – A 4 ) (B 3 + B 4 )
and S = (A 1 + A 4 ) *(B 1 +B 4 )
along with 6 additions and 4 subtractions of n/2 × n/2 matrices. The matrices Ci’s will be computed
from above seven matrices as,
C 1 = N + R + S – P
C 2 = M + P
C 3 = N + O
C 4 = M + Q + S – O
That requires another 6 additions and 2 subtractions of n/2 × n/2 matrices. Therefore
Stressman’s method requires a total of 7 multiplications and 18 addition/subtraction opera-
tions of n/2 × n/2 matrices. If we compare these two methods of matrix multiplication we