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

Figure 10.6 Pebbling an inner product graph with three pebbles.

10.4.3 First Matrix Multiplication Bound
The Grigoriev lower-bound method is well illustrated by matrix multiplication. We established
its independence property in Section 10.4.1 . In this section we apply it to Corollary 10.4.1 .
The upper bound stated in the following theorem follows from the development of an algo-
rithm for matrix multiplication that uses three pebbles and executes at most 4 n 3 steps. This
algorithm, based on the standard matrix multiplication algorithm of Section 6.2.2 ,formseach
of the n 2 inner products defined by the product of two n

× n matrices using three pebbles, as

suggested in Fig. 10.6 ,and4 n

−

1steps.

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

2 n 2 n 2

B →B

for n

× n matrices requires space S and time T satisfying

B : ×

the following inequality:

n 3 / 4 ( S + 1 ) T ≥

The standard algorithm for multiplying n

n matrices uses space and time satisfying
( S + 1 ) T = 16 n 3

×

Those familiar with fast non-standard matrix multiplication algorithms such as Strassen's
fast matrix algorithm (Section 6.3 ) may find this result surprising. Whereas one learns that
the standard matrix multiplication algorithm is not optimal with respect to computation time,
the above result states that the standard matrix multiplication algorithm is nearly optimal with
respect to the space-time product.
In Section 10.5.4 we specialize Theorem 10.4.1 to the flow properties of matrix multipli-
cation, giving a stronger result: that the space and time for matrix multiplication must satisfy
the inequality ST 2 =Ω( n 6 ) .

10.5 Applications of Grigoriev's Method
Given the above results, to derive a lower bound on T using Corollary 10.4.1

it suffices to establish the independence property of a function. We apply this idea in this
section to convolution, cyclic shifting, integer multiplication, matrix-vector multiplication,
matrix inversion, and solving linear equations. We apply related arguments to derive lower
bounds for the discrete Fourier transform and merging. Finally, we apply Theorem 10.4.1 to
derive a lower bound on space-time exchanges for matrix-matrix multiplication that improves
upon the bound of Section 10.4.3 . Where possible we also derive upper bounds on space-time
tradeoffs.

α ( S + 1 )