Space–Time Tradeoffs - Models of Computation: Exploring the Power of Computing - page 478

makes many variables of B in X 1 match entries in C in Y 1 , or choosing B to be the s th
cyclic permutation makes many variables of A in X 1 match entries in C in Y 1 .Whenan
input and output variable match, the latter assumes the value of the former. Thus, all the
variation in the former is reflected in the latter.
Let Q =

. Then the w ( u , v ) -flow is at least Q/ 2. Applying
( 10.5 )andthen( 10.4 )to Q , we have the following inequalities:

| C ∩ A ( r ) | + | C ∩ B ( s ) |

n 2 Q ≥| C ∩ ( A ( r ) ∪ B ( s )) |≥| C | + | A ( r ) ∪ B ( s ) |−

Applying ( 10.3 )to | A ( r ) ∪ B ( s ) | yields the following lower bound on Q :

n 2 Q ≥| C | + | A ( r ) | + | B ( s ) |−| A ( r ) ∩ B ( s ) |−

(10.6)

| C | = | Y 1 | | A ( r ) | = | A | | B ( s ) | = | B | | A | + | B | = | X 1 |

But , , ,and . We now show that

there are values for r and s such that

| A ( r ) ∩ B ( s ) | | A || B | /n 2 .

is at most

Consider the following sum:

n

s = 1 |

n

S = A ( r ) ∩ B ( s ) |

r = 1

Since A ( r ) and B ( s ) are formed by the r th and s th cyclic shift of columns of A and rows
of B respectively, each 1 in A is aligned once with each 1 in B . It follows that

S = | A || B |

is at most S/n 2 . Applying As a consequence, there are some r and s such that | A ( r ) ∩ B ( s ) |

this result in ( 10.6 ), we have the following lower bound on Q :

/n 2 n 2 Q ≥| Y 1 | + | A | + | B |−| A || B | −

| X 1 | = | A | + | B |

is fixed, the above lower bound on Q is minimized by maximizing

Since

| A || B | | A | | A | = | X 1 | / 2. Consequently

under variation of . This maximum occurs when

we have the following lower bound on Q :

n 2 1

2 n 2 2

− |

X 1 |

Q ≥| Y 1 |−

Since w ( u , v ) ≥ Q/ 2for u = | X 1 | and v = | Y 1 | , we have desired the conclusion.

We now apply this result and Theorem 10.4.1 to derive a stronger result for matrix multi-
plication than was obtained earlier using its ( 1, 2 n 2 , n 2 , n ) -independence property.

THEOREM 10.5.4 Every pebbling strategy for straight-line programs computing the matrix multi-
plication function f ( n )
A

2 n 2 n 2

B :

B →B for n × n matrices requires space S and time T satisfying

×

the following inequality:

ST 2 n 6 / 3 ≥

The standard algorithm for multiplying n

× n matrices uses space and time satisfying

ST 2 = 48 n 6