O'Reilly logo

A Guide to Algorithm Design by Frédéric Vivien, Yves Robert, Anne Benoit

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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
first illustrate the concept with Strassen’s matrix multiplication algorithm
(Section 2.1) before explaining the master theorem (Section 2.2) and finally
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
coefficients to compute, each of them
corresponding to a scalar product of size n, thus with n multiplications, n 1
additions, and one affectation. 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 first 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
Add(2) = 4 Add(2) = 18
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
/8. For the additions, we need to add the
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
for Mult(n) as for Add(n),
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
(both for pointwise multiplications and additions), while adding two matrices
of size n × n requires only O(n
2
) operations. For n large enough, matrix
additions have a negligible cost in comparison to matrix multiplications (and
the main source of pointwise additions is within these matr ix multiplications).
That was not the case for real numbers, hence, the inefficiency of the method
for 2 × 2 matrices.
© 2014 by Taylor & Francis Group, LLC

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

Start Free Trial

No credit card required