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