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

Proof From Lemma 10.5.3 we have that the matrix multiplication function has a w ( u , v ) -
flow, where

( 2 n 2 u ) 2 / 4 n 2 ) / 2

w ( u , v ) ≥ ( v − −

Applying Theorem 10.4.1 to this problem with b = 3 S ,weseekthelargestinteger d such
that w ( d , b )

≤ S , which must satisfy the bound

3 S

d ) 2 / 4 n 2 / 2

( 2 n 2 − − ≤ S

2 n √ S .FromTheorem 10.4.1 , the time to pebble the graph

This implies that ( 2 n 2

− d ) ≥

satisfies

2 √ Sn

n 2 / 3 S T ≥

2 √ Sn ( n 2

≥ −

3 S + 1 ) / 3 S

( 16 √ 2 n 3 ) / ( 27 √ S ) or ST 2 If S

≤ n 2 / 27, T ≥ ≥

( . 35 ) n 6 . On the other hand, since

T ≥

3 n 2 just to pebble inputs and outputs, if S>n 2 / 27, then ST 2

≥ n 6 / 3.

10.5.5 Discrete Fourier Transform
The discrete Fourier transform (DFT) is defined in Section 6.7.3 . We derive upper and lower
bounds on the space-time product needed to compute this function.

LEMMA 10.5.4 The n -point DFT function F n : R

n n

→R over a commutative ring R is

( 2, n , n , n/ 2 ) -independent for n even.
Proof Asshowninequation( 6.23 ), the DFT is defined by the matrix-vector product
[ w ij ] a ,where [ w ij ] is a Vandermonde matrix. To show that the DFT function is ( 2, n , n ,
n/ 2 ) -independent, consider any set Y 1 of outputs (corresponding to rows of [ w ij ] )andany
set X 0 of inputs (corresponding to columns) whose values are to be fixed judiciously, where
p = |R| |Y 1 |/ 2 valuesaswe | X 0 | + | Y 1 | = n/ 2. We show that the outputs in Y 1 have at least

vary over the remaining inputs.
It is straightforward to show that the submatrix of [ w ij ] defined by any

| Y 1 |

rows and any

| Y 1 |

consecutive columns is non-singular. (Its determinant is that of another Vandermonde
matrix. Show this by letting the row and column indices be r 1 , r 2 , ... , r |Y 1 |

and s , s +

1, respectively, and demonstrating that w r i s can be factored out of the i th
row when computing its determinant.) Our goal is to show that some consecutive group of
columns corresponds to at least

1, ... , s +

| Y 1 |−

/ 2inputsof a in X 1 .
Divide the n columns of [ w ij ] into

| Y 1 |

n/ | Y 1 | | Y 1 |

groups of consecutive columns with

inputs in each group except possibly the last, which may have fewer. There are n −| X 0 |

inputs that may vary. Since there are n/ | Y 1 | groups, by an averaging argument some group

contains at least ( n −| X 0 | ) / n/ | Y 1 | of these inputs. Since n/ | Y 1 | ≤ ( n + | Y 1 |− 1 ) / | Y 1 | ,

we show that ( n −| X 0 | ) / n/ | Y 1 | > | Y 1 | / 2for p = n/ 2. Observe that ( n −| X 0 | ) / ( n +

| Y 1 |− 1 ) ≥ 1 / 2if2 n − 2 | X 0 |≥ n + | Y 1 |− 1or n ≥| X 0 | + p − 1, which holds because

| X 0 |≤ n/ 2.

Since the submatrix defined by k consecutive columns and any k rows where

p ≤

| Y 1 | / 2 ≤

k ≤| Y 1 | is non-singular, it follows that any subset of | Y 1 | / 2 columns has full rank. Thus,

the submatrix contains a non-singular | Y 1 | / 2 ×| Y 1 | / 2 matrix. When all inputs outside