Information Technology Reference
In-Depth Information
Y 1
Y 0
Y
X 0
X
X 1
Figure 10.5 Afunction f that has a large information flow from input variables in X 1 to
output variables in Y 1 for some values of input variables in X 0 = X − X 1 .
|A| |X 1 | values. This flow property is also used
in Section 12.7 to derive lower bounds on the exchange of area for time in the VLSI model of
computation.
outputs in Y 1 as inputs in X 1 range over all their
DEFINITION 10.4.1 Afunction f : A
n
m has a w
→A
(
u , v
)
-flow if for all subsets X 1 and
Y 1 of
v ,thereisasubfunction
h of f obtained by making some assignment to variables of f not in X 1 (variables in X 0 )and
discarding output variables not in Y 1 such that h has at least
its n input and m output variables, with
|
X 1 |≥
u and
|
Y 1 |≥
w ( u , v ) points in the image of its
|A|
domain.
The exponent function w ( u , v ) is a nondecreasing function of both of its arguments: in-
creasing u , the number of variables that are allowed to vary, can only increase the number of
values assumed by f ; the same is true if v is increased.
An important class of functions are the ( α , n , m , p ) -independent functions defined below.
DEFINITION 10.4.2 Afunction f : A
n
m is an
→A
(
α , n , m , p
)
-independent function for
α
1 and p
m if it has a w ( u , v ) -flow satisfying w ( u , v ) > ( v/α )
1 for n
u + v
p .
We illustrate the independence property of a function with matrix multiplication: we show
that the function defined by the product of two n
n matrices is ( 1, 2 n 2 , n 2 , n ) -independent.
In Section 10.5.4 , we show that a stronger property holds for matrix multiplication.
Theproofoftheindependencepropertyof n
×
×
n matrices uses the permutation matrices
described in Section 6.2 .An n
×
n permutation matrix is obtained by permuting either the
rows or columns of the n
n identity matrix. When a permutation matrix B multiplies another
matrix A on the right (left) to produce AB ( BA ), it permutes the columns (rows) of A .
×
LEMMA 10.4.1 The matrix multiplication function f ( n )
2 n 2
n 2
B :
R
→R
over the ring
R
is
A
×
( 1, 2 n 2 , n 2 , n ) -independent.
Search WWH ::




Custom Search