Page 244 - Discrete Mathematics and Its Applications

3.3 Complexity of Algorithms 223

EXAMPLE 7 How many additions of integers and multiplications of integers are used by Algorithm 1 to
multiply two n × n matrices with integer entries?

2
Solution: There are n entries in the product of A and B. To find each entry requires a total
2
3
of n multiplications and n − 1 additions. Hence, a total of n multiplications and n (n − 1)
additions are used. ▲
Surprisingly, there are more efficient algorithms for matrix multiplication than that given in
Algorithm 1. As Example 7 shows, multiplying two n × n matrices directly from the definition
3
requires O(n ) multiplications and additions. Using other algorithms, two n × n matrices can
√
be multiplied using O(n 7 ) multiplications and additions. (Details of such algorithms can be
found in [CoLeRiSt09].)
WecanalsoanalyzethecomplexityofthealgorithmwedescribedinChapter2forcomputing
the Boolean product of two matrices, which we display as Algorithm 2.

ALGORITHM 2 The Boolean Product of Zero-One Matrices.

procedure Boolean product of Zero-One Matrices (A, B: zero–one matrices)
for i := 1 to m
for j := 1 to n
c ij := 0
for q := 1 to k
c ij := c ij ∨ (a iq ∧ b qj )
return C {C =[c ij ] is the Boolean product of A and B}

The number of bit operations used to find the Boolean product of two n × n matrices can
be easily determined.
EXAMPLE 8 How many bit operations are used to find A B, where A and B are n × n zero–one matrices?

2
Solution: There are n entries in A B. Using Algorithm 2, a total of nORs and n ANDs are
used to find an entry of A B. Hence, 2n bit operations are used to find each entry. Therefore,
3
2n bit operations are required to compute A B using Algorithm 2. ▲
MATRIX-CHAIN MULTIPLICATION There is another important problem involving the
complexityofthemultiplicationofmatrices.Howshouldthe matrix-chain A 1 A 2 ··· A n becom-
puted using the fewest multiplications of integers, where A 1 , A 2 , ..., A n are m 1 × m 2 ,m 2 ×
m 3 ,...,m n × m n+1 matrices, respectively, and each has integers as entries? (Because matrix
multiplication is associative, as shown in Exercise 13 in Section 2.6, the order of the mul-
tiplication used does not change the product.) Note that m 1 m 2 m 3 multiplications of integers
are performed to multiply an m 1 × m 2 matrix and an m 2 × m 3 matrix using Algorithm 1.
Example 9 illustrates this problem.
EXAMPLE 9 In which order should the matrices A 1 , A 2 , and A 3 —where A 1 is 30 × 20, A 2 is 20 × 40, and
A 3 is 40 × 10, all with integer entries—be multiplied to use the least number of multiplications
of integers?
Solution:There are two possible ways to compute A 1 A 2 A 3 .These are A 1 (A 2 A 3 ) and (A 1 A 2 )A 3 .
If A 2 and A 3 are first multiplied, a total of 20 · 40 · 10 = 8000 multiplications of inte-
gers are used to obtain the 20 × 10 matrix A 2 A 3 . Then, to multiply A 1 and A 2 A 3 requires
30 · 20 · 10 = 6000 multiplications. Hence, a total of

8000 + 6000 = 14,000