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

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 ineﬃciency of the method

for 2 × 2 matrices.

© 2014 by Taylor & Francis Group, LLC

Start Free Trial

No credit card required