Parallel Computing for Data Science

266 CHAPTER 12. MATRIX OPERATIONS

But this says that

R

(2)

27

= b(a

21

a

17

+ a

22

a

27

+ a

23

a

37

+ ...) (12.20)

The key point is that the argument to b() here is (A

2

)

27

, demonstrating

(12.19).

So, the original graph connectivity problem reduces to a matrix power

problem. We simply compute A

n−1

(and then apply b()).

12.6.2 The “Log Trick”

Moreover, we can save computation there as well, by using the “log trick.”

Say we want the 16

th

power of some matrix B. We can square it, yielding

B

2

, then square that, yielding B

4

. Two more squarings then give us B

8

and B

16

. That would be only four matrix-multiply operations, instead of

15. In general, for power 2

m

, we need m steps. ...