Information Technology Reference
In-Depth Information
LEMMA
10.13.2
Let
A
be a
γ
-ok
n×n
matrix over
R
for some
0
<γ<
1
/
2
. Then the matrix-
vector product function
f
(
n
)
A
n
n
:
R
→R
is
(
1,
γ
,
γ
,
γ
,
τ
)
-distinguishable where
τ
(
b
)=
n
.
×
x
Proof
To s h ow t h a t
f
(
n
)
A
is
(
1,
γ
,
γ
,
γ
,
τ
)
-distinguishable, select any
a
≤
γn
inputs and
×
x
any
b
outputs. If the
i
th input is chosen and it has value
u
i
, introduce the equation
x
i
=
u
i
.Let
B
be the
a
≤
γn
n
coefficient matrix defining these equations; that is,
B
x
=
u
,
where
B
contains the
j
th row of the
n
×
×
n
identity matrix if the
j
th variable is among the
selected inputs.
n
matrix
C
=
A
B
. We show that it has rank
a
+
γb
.The
Consider the
(
n
+
a
)
×
submatrix
D
of
A
consisting of the intersection of those columns not selected by inputs (of
which there are
n
) and rows selected by outputs (of which there are
b
)
has rank
γb
because
A
is
γ
-ok. Thus,
γb
of the
n
−
a
≥
n
−
γn
a
columns of
A
not selected by inputs
and the
a
non-zero columns of
B
are linearly independent. Thus, the submatrix
E
of
C
consisting of the selected rows of
B
and the rows of
D
has rank
a
+
γb
.
The number of
n
-tuple input vectors
x
consistent with the linear system
E
x
=
d
is
−
n−a−γb
, as we show. Without loss of generality assume that the first
a
+
γb
columns of
E
(call it
F
) are linearly independent. (Permute the columns, if necessary, so that this is true.)
Fix the values of the
b
realizable outputs. Then for each assignment to inputs corresponding
to the last
n
|A|
(
a
+
γb
)
columns there are unique values for the first
a
+
γb
inputs, due to
the non-singularity of
F
. Thus the number of assignments to the last
n
−
−
(
a
+
γb
)
columns
n−a−γb
.
that are consistent with values for the
a
inputs and
b
outputs is
|A|
Invoking Corollary
10.11.1
yields the following result.
THEOREM
10.13.3
Let
A
be a
γ
-ok
n × n
matrix over
R
for some
0
<γ<
1
/
2
. Then there
is a constant
0
<γ<
1
/
2
and an integer
n
0
such that for
n
≥
n
0
the space
S
and time
T
used
by any general branching program for the function
f
(
n
)
n
n
must satisfy the following
:
R
→R
A×
x
lower bound when
T
≥
n
:
ST
=Ω(
n
2
log
|R|
)
This lower bound can be met to within a factor of
O
(log
n
)
for
log
n
≤
S
≤
n
.
Proof
The lower bound follows from the application of Theorem
10.11.1
.
The matrix-vector product
A
x
for an
n
n
matrix
A
can be done with a branching
program for the standard algorithm as follows: Compute the inner product of the
i
th row
with the column
x
for 1
×
n
. The inner product of two
n
-tuples can be computed
with a branching program having
O
(
n
≤
i
≤
2
)
vertices, as suggested in Fig.
10.20
. (This is
true even if
A
is not fixed.)
n
branching programs for inner products can be concatenated to
form one branching program to multiply an
n
|R|
×
n
matrix with an
n
-vector. This branching
program uses space
O
(log
n
+log
|R|
)
and time
O
(
n
2
)
, thereby meeting the lower bound
to within a factor of
O
(log
n
)
.
A matrix-vector product for a fixed matrix (this case) can also be computed by table
lookup in space
O
(
n
log
)
and time
O
(
n
)
since this function has
n
variables.
To bridge the gap between these two results, compute the matrix-vector product using a
hybrid algorithm similar to that used for convolution in the proof of Theorem
10.13.1
.
|R|
Search WWH ::
Custom Search