Information Technology Reference
In-Depth Information
10.13.1 Convolution
The wrapped convolution function
f
(
n
)
wrapped
:
R
2
n
→R
n
over the ring
R
(see Problem
6.19
)
of two sequences
u
and
v
is described by the matrix-vector product
C
v
of a circulant matrix
C
in which
c
i
,
j
=
u
(
i−j
)mod
n
, as shown in Section
10.5.1
.
LEMMA
10.13.1
For
n
even, the wrapped convolution
f
(
n
)
2
n
n
over the ring
wrapped
:
R
→R
R
contains a subfunction
g
(
n
)
:
2
n
n/
2
that is
(
1,
γ/
2,
γ/
2, 1, 2
n
)
-distinguishable for some
R
→R
0
<γ<
1
/
2
.
Proof
Writing
C
as a 2
n/
2 matrices, we find that its (1,1) entry is
an unrestricted Toeplitz matrix
T
. That is, each diagonal can contain a different element.
Consider the subfunction of
f
(
n
)
×
2matrixof
n/
2
×
wrapped
defined by this submatrix. By Lemma
10.12.1
,a
(
2
/
3
)
(
γ/
2
)
n
/
−
|R|
of such matrices are
γ
-nice. By Definition
10.12.1
,
fraction of at least 1
|R|
(
γ/
2
)
n
different values. If we fix
the entries of
T
to be those of a
γ
-nice matrix, by Lemma
10.11.2
the lower bound on
ST
for matrix-vector multiplication with a Toeplitz matrix with
n
replaced by
n/
2servesasa
lower bound for the original problem. Since for large
n
most Toeplitz matrices are
γ
-nice,
we have the desired conclusion.
(
γ/
2
)
n
this implies that
output variables assume
Invoking Theorem
10.11.1
, we have the space-time lower bound stated below. The up-
per bound follows from the design of a branching program to implement the inner product
operation, as suggested by Fig.
10.6
.
THEOREM
10.13.1
There is an integer
n
0
>
0
such that for
n
even and
n ≥ n
0
,thetime
T
and
space
S
used by any general branching program for the wrapped convolution
f
(
n
)
wrapped
2
n
:
R
→
n
over the ring
R
R
must satisfy
ST
=Ω(
n
2
log
|R|
)
(10.9)
Branching programs exist that achieve the following bound for
log
|R| ≤
S
≤
n
log
|R|
:
ST
=
O
(
n
2
log
n
log
|R|
)
Proof
Since the wrapped convolution function depends on 2
n
variables, it can be computed
via table lookup with space
O
(
n
log
)
and time
O
(
n
)
.
At the limit of small space, namely for
S
=Θ(log
|R|
)
, a branching program can
be designed that computes the
n
inner products defined by the matrix-vector product of
(
10.1
). An example of a branching program to compute the inner product of two 3-vectors
isshowninFig.
10.20
. A branching program for the inner product of two
n
-tuples can be
constructed that has
O
(
n
|R|
2
)
vertices and depth
O
(
n
)
. Hence, a branching program to
|R|
n
matrix by a vector can be constructed that has time
O
(
n
2
)
and
multiply a general
n
×
space
O
(log
n
+log
)
.
To fill in the range between these extremes, let
k
divide
n
and note that the product of
an
n
|R|
×
n
matrix by a column
n
-vector can be viewed as the product of an
n/k
×
n/k
matrix
of
k
×
k
matrices with a column
n/k
-vector of column
k
-vectors. Since each product of
a
k
k
submatrix by a
k
-vector is a function of
O
(
k
)
parameters, compute it with table
lookup in time
O
(
k
)
and space
O
(
k
log
×
|R|
)
. Add two of these matrix-vector products by
Search WWH ::
Custom Search