Information Technology Reference
In-Depth Information
√
s
3
1
/
(
√
3
r
2
)
r
3
=
r
2
−
s
1
/
3
r
1
=
1
/
(
√
3
r
1
)
r
2
=
r
1
√
s
2
−
Figure 11.7
A three-level decomposition of a matrix.
We now describe a multi-level recursive pebbling strategy satisfying the upper bounds
given above. It is based on the two-level strategy given in the proof of Theorem
11.5.2
.We
compute
C
from
A
and
B
using inner products.
Our approach is to successively block
A
,
B
,and
C
into
r
i
×
r
i
submatrices for
i
=
k
,
k
1,
...
,1wherethe
r
i
are chosen, as suggested in Fig.
11.7
, so they divide on another
and avoid memory fragmentation. Also, they are also chosen relative to
s
i
so that enough
pebbles are available to pebble
r
i
×
−
r
i
submatrices, as explained below.
s
1
/
3
⎧
⎨
i
=
1
r
i
=
r
i−
1
(
s
i
−
i
+
1
)
/
(
√
3
r
i−
1
)
i
⎩
≥
2
Using the fact that
b/
2
≤
a
b/a
≤
b
for integers
a
an
d
b
satisfying 1
≤
a
≤
b
(see
Problem
11.1
), we see that
(
s
i
−
r
i
≤
(
s
i
−
i
+
1
)
/
12
≤
i
+
1
)
/
3. Thus,
s
i
≥
3
r
i
+
i
3
n
2
.
By definition,
s
l
pebbles are available at level
l
and below. As stated earlier, there is at
least one pebble at each level above the first. From the
s
l
pebbles at level
l
and below we
create a reserve set containing one pebble at each level except the first. This reserve set is
used to perform I/O operations as needed.
Without loss of generality, assume that
r
k
divides
n
.(Ifnot,
n
must be at most doubled
for this to be true. Embed
A
,
B
,and
C
in such larger matrices.)
A
,
B
,and
C
are then
blocked into
r
k
×
1. Also,
r
k
≤
n
2
because
s
k
≤
−
r
k
submatrices (call them
a
i
,
j
,
b
i
,
j
,and
c
i
,
j
), and these in turn are blocked
into
r
k−
1
×
r
k−
1
submatrices, continuing until 1
×
1 submatrices are reached. The submatrix
c
i
,
j
is defined as
Search WWH ::
Custom Search