Information Technology Reference
In-Depth Information
a 1 =?
0
1
b 1 =?
b 1 =?
0,1
0
1
a 2 =?
a 2 =?
0
1
0
1
b 2 =?
b 2 =?
b 2 =?
b 2 =?
1
1
0
0,1
0,1
0
a 3 =?
a 3 =?
0
1
0
1
b 3 =?
b 3 =?
b 3 =?
b 3 =?
1
1
0,1
0
0,1
0
c = 0
c = 1
c = a 1 b 1 + a 2 b 2 + a 3 b 3 (mod 2 )
Figure 10.20 A branching program to compute the inner product of two 3-vectors over the set
R
of integers modulo 2.
k ) final states of a first table-lookup
rooting a table-lookup program at each of the O (
|R|
k sums of the two column k -vectors.
program. Coalesce final states corresponding to the
|R|
2 k ) vertices or space O ( k log
This program has O (
) and time O ( k ) . n/k such stages
increase the number of vertices and time each by a factor of n/k . Since this process is
then repeated for each of the n/k rows of the block matrix, the space and time used are
O ( k log
|R|
|R|
+log( n/k )) and O ( n 2 /k ) , respectively.
|R|
10.13.2 Integer Multiplication
To derive space-time lower bounds for integer multiplication, we could invoke the reductions
from this problem to cyclic shifting, as was done in Section 10.5.3 . However, as shown in
Section 10.10 , the space-time product for cyclic shifting is only O ( n log n ) .Thus,weare
forced to use another reduction to obtain a strong space-time product lower bound, namely a
reduction from integer multiplication to convolution.
 
Search WWH ::




Custom Search