Information Technology Reference
In-Depth Information
Proof
Let
n
be a multiple of 4. The lower bound follows by reducing matrix inversion to
the computation of the product of three arbitrary
n/
4
×
n/
4 matrices, as shown below:
⎡
⎤
⎡
⎤
−
1
I
−
A
0
0
I A AB ABC
0
IB BC
00
I C
00 0
I
⎣
⎦
⎣
⎦
0
I
−
B
0
=
00
I
C
000
I
−
The upper bound for
T
=Θ(
n
2
)
is obtained by table lookup using an algorithm of
the kind described in the proof of Theorem
10.13.3
.For
T
=Θ(
n
3
)
, the matrix inversion
algorithm based on the
LDL
T
decomposition of a symmetric positive definite matrix of
Section
6.5.4
can be used. For intermediate values of time, a hybridized algorithm based on
the inversion of block matrices provides the stated upper bound.
10.13.6 Discrete Fourier Transform
The discrete Fourier transform (DFT) and the fast Fourier transform algorithm are described
in Sections
6.7.2
and
6.7.3
. In this section we derive upper and lower bounds on space-
time tradeoffs for this problem. The lower bound follows from the result for matrix-vector
multiplication and the fact that the coefficient matrix for the DFT is
(
1
/
4
)
-ok.
LEMMA
10.13.5
Consider the
n
-point DFT over a commutative ring that has a principal
n
th
root of unity. It is defined as a matrix-vector product with
[
w
ij
]
as its
n
×
n
coefficient matrix.
This matrix is
(
1
/
4
)
-ok.
Proof
We use the fact, shown in Theorem
10.5.5
, that the submatrix of
W
=[
w
ij
]
con-
sisting of any
k
rows and any
k
consecutive columns is non-singular. We show that any
p
×
q
submatrix
B
of
W
,with
p
, has rank at least
p/
4.
Let
I
denote the row indices of the submatrix
B
and let
J
denote its column indices.
Let
C
be the submatrix of
W
with row indices in
I
. Divide the columns of
C
into
≤
n/
4
and
q
≥
n
−
n/
4
groups each containing
p
columns except possibly the last which has at most
p
columns. We
claim that some group has at least
p/
2 columns in common with
B
. Suppose not. Then
every one of the
n/p
n/p
groups has at most
(
p
−
1
)
/
2 columns in common with
B
.Thus
B
has at most
χ
(
p
)=
n/p
(
p
−
1
)
/
2 columns. We show that
χ
(
p
)
<n
−
(
n
+
3
)
/
4
≤
n
−
n/
4
. But this is a contradiction because
B
has at least
n
−
n/
4
columns. Since
n/p
≤
(
n
+
p
−
1
)
/p
,if
(
n
+
p
−
1
)(
p
−
1
)
/
2
p<n
−
(
n
+
3
)
/
4, the following holds
after multiplying both sides by 2
p
:
1
)
<
3
p
(
n
−
1
)
(
n
+
p
−
1
)(
p
−
or
2
n
+
1
<p
(
n
+
1
)
2
p
−
−
It suffices to show that the right-hand side of the last equation is positive. But
((
n
+
1
)
/
2
)
−
p
is positive since
p
≤
n/
4
≤
(
n
+
3
)
/
4
≤
(
n
+
1
)
/
2for
n
≥
1.
THEOREM
10.13.7
There is an integer
n
0
>
0
such that for
n>n
0
the
n
-point DFT over a
commutative ring
R
requires space
S
and time
T
with a branching program satisfying the following
Search WWH ::
Custom Search