## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

Chapter 2
Divide-and-conquer
This chapter revisits the divide-and-conquer paradigms and explains how to
solve recurrences, in particular, with the use of the “master theorem.” We
ﬁrst illustrate the concept with Strassen’s matrix multiplication algorithm
(Section 2.1) before explaining the master theorem (Section 2.2) and ﬁnally
providing techniques to solve recurrences (Section 2.3). These techniques
are further illustrated in the exercises of Section 2.4, with solutions found in
Section 2.5.
2.1 Strassen’s algorithm
The classical matrix multiplication algorithm computes the prod uct of two
matrices of size n × n with Add(n) = n
2
(n 1) additions and Mult(n) = n
3
multiplications. Indeed, there are n
2
coeﬃcients to compute, each of them
corresponding to a scalar product of size n, thus with n multiplications, n 1
additions, and one aﬀectation. Can we do better than this?
Note that the question was raised at a time when it was mainly interest-
ing to decrease the number of multiplications, even though this would imply
computing more additions. The pipelined architecture of today’s processors
allows us to perform, in steady-state mode, one addition or one multiplication
per cycle time.
Strassen intr oduced a new method in his seminal paper [101]. Let us com-
pute the product of two 2 × 2 matrices:
r s
t u
=
a b
c d
×
e f
g h
33
© 2014 by Taylor & Francis Group, LLC
34 Chapter 2. Divide-and-conquer
We ﬁrst compute seven intermediate pro du cts
p
1
= a(f h)
p
2
= (a + b)h
p
3
= (c + d)e
p
4
= d(g e)
p
5
= (a + d)(e + h)
p
6
= (b d)(g + h)
p
7
= (a c)(e + f)
and then we can write
r = p
5
+ p
4
p
2
+ p
6
s = p
1
+ p
2
t = p
3
+ p
4
u = p
5
+ p
1
p
3
p
7
.
If we count operations for each method, we obtain the following:
Classic
Strassen
Mult(2) = 8 Mult(2) = 7
Strassen’s method gains one multiplication, but at the price of 14 extra
additions, thus being worse on modern processors than the classical method
for 2 × 2 matrices. However, it is remarkable th at the new method does not
require the commutativity of multiplication, and, therefore, it can be used,
for instance, with matrices instead of numbers. We can readily use it with
matrices of even size n, say n = 2m. We consider that a, b, c, d, e, f, g, h, r, s, t,
and u are matrices of size m × m. So, let n = 2m, and use the previous
approach with submatrices of size m × m. To compute each p
i
(1 i 7)
with the classic matrix multiplication algorithm, we need m
3
multiplications,
thus a total M u l t(n) = 7m
3
= 7n
3
additions performed in the seven matrix multiplications to form the interme-
diate products p
i
, namely 7m
2
(m 1), with the number of additions required
to form the auxiliary matrices, namely 18m
2
. Indeed, there are 10 matrix ad-
ditions to compute the p
i
s, and then 8 other matrix additions to obtain r, s, t,
and u. Therefore, we have a total of Add(n) = 7m
3
+11m
2
= 7n
3
/8+11n
2
/4.
Asymptotically, the dominant term is in
7
8
n
3
and the new method is interesting for n large enough. The intuition is the
following: Multip lyin g two matrices of size n × n requires O(n
3
) operations