Information Technology Reference
In-Depth Information
10.5.1 Convolution
The wrapped convolution on strings of length
n
over the ring
,
f
(
n
)
n
,is
defined in Problem
6.19
. It can be characterized by the following product of a circulant matrix
with a vector (see Section
6.2
):
⎡
R
wrapped
:
R
2
n
→R
⎤
⎡
⎤
⎡
⎤
w
0
w
1
w
2
.
w
n−
1
u
0
u
n−
1
u
n−
2
...
u
1
v
0
v
1
v
2
.
v
n−
1
⎣
⎦
⎣
⎦
⎣
⎦
u
1
u
0
u
n−
1
...
u
2
.
.
.
=
×
(10.1)
u
n−
2
u
n−
3
u
n−
4
...
u
n−
1
u
n−
1
u
n−
2
u
n−
3
...
u
0
Lemma
10.5.1
demonstrates
(
2, 2
n
,
n
,
n/
2
)
-independence for the wrapped convolution
f
(
n
)
2
n
n
function by showing that for any set
X
0
of inputs there is a way to put
wrapped
:
R
→R
|
/
2entriesinany
set
Y
1
of outputs. This is established by setting one component of
v
to 1 and the rest to 0.
Y
1
|
/
2 of the inputs in
X
−
X
0
into a one-to-one correspondence with
|
Y
1
|
LEMMA
10.5.1
For
n
even, the wrapped convolution
f
(
n
)
2
n
n
over the ring
wrapped
:
R
→R
R
is
(
2, 2
n
,
n
,
n/
2
)
-independent.
Proof
Consider subsets
X
0
and
Y
1
of the inputs
X
and outputs
Y
of
f
(
n
)
satisfying
wrapped
=
p
=
n/
2. For
f
(
n
)
|
wrapped
to be
(
2, 2
n
,
n
,
n/
2
)
-independent, there must be
an assignment to input variables in
X
0
such that the output variables in
Y
1
have more than
|R|
X
0
|
+
|
Y
1
|
1
distinct values as the input variables of
f
(
n
)
(
|Y
1
|/
2
)
−
wrapped
in
X
1
=
X
−
X
0
range over
all possible values.
As shown above,
f
(
n
)
wrapped
is defined by a matrix-vector product
w
=
M
v
,
M
acir-
culant matrix, in which each row (column) is a cyclic shift of the first row (column). Let
e
=
|
X
0
∩{
u
0
,
u
1
,
...
,
u
n−
1
}|
. Thus, every row of
M
contains the same number
e
of
entries from
X
0
.Also,
n
X
0
.Theentriesin
X
1
are free to vary.
Each output in
Y
1
corresponds to a row of
M
. The number of instances of input
variables from
X
1
in these rows is
−
e
inputs are in
X
1
=
X
−
e
)
.Sincetheserowshave
n
columns, there
is some column, say the
t
th, containing at least the average number of instances from
X
1
.
This average is
|
Y
1
|
(
n
−
/
2. (The instances of variables from
X
1
in a column
are distinct.) It follows that by choosing the
t
th component of
v
,
v
t
,tobe1andthe
others to be 0, at least
|
Y
1
|
(
1
−
e/n
)
≥|
Y
1
|
/
2 of the inputs in
X
1
are mapped onto outputs in
Y
1
.Since
these inputs (and outputs) can assume
|
Y
1
|
|R|
|Y
1
|/
2
different values, it follows that
f
(
n
)
wrapped
is
(
2, 2
n
,
n
,
n/
2
)
-independent.
This implies the lower bound stated below. The upper bound follows from the standard
matrix-vector algorithm for the wrapped convolution using the observation that an inner prod-
uct can be done with three pebbles, as suggested in Fig.
10.6
.
THEOREM
10.5.1
The time
T
and space
S
required to pebble any straight-line program for the
standard or wrapped convolution must satisfy the following inequality:
(
S
+
1
)
T
n
2
/
16
This lower bound can be achieved to within a constant multiplicative factor for
S
=
O
(
1
)
.
≥
Search WWH ::
Custom Search