Составители:
Рубрика:
Замечание.Скалярное произведение двух векторов размерно-
сти n можно осуществить с помощью параллельной формы высоты
dlog
2
ne + 1 и ширины n.
Д о к а з а т е л ь с т в о очевидно: на первом шаге проводим
необходимые умножения, что ведет к одному ярусу ширины n,
а при сложении применяем схему сдваивания (см. теорему 8.2
главы 1).
§ 4. О распараллеливании
одного рекурентного процесса
Здесь будет рассмотрен один часто встречающийся рекурент-
ный процесс.
Пусть r, s — фиксированные натуральные числа, а
X
0
, X
−1
, . . . , X
−r+1
(4.1)
— заданные n-мерные векторы. Требуется найти векторы
X
1
, X
2
, . . . , X
s
(4.2)
из рекурентных соотношений
X
i
= A
i1
X
i−1
+ . . . + A
ir
X
i−r
+ B
i
, i = 1, 2, . . . , s. (4.3)
Здесь A
ij
, (j = 1, . . . , r, i = 1, 2, . . . , s) — заданные квадратные мат-
рицы порядка n, B
i
— заданные векторы.
Итак, векторы (4.2) определяются из соотношений
X
1
= A
11
X
0
+ A
12
X
−1
+ . . . + A
1r
X
−r+1
+ B
1
X
2
= A
21
X
1
+ A
22
X
0
+ . . . + A
2r
X
−r+2
+ B
2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
X
s
= A
s1
X
s−1
+ A
s2
X
s−2
+ . . . + A
sr
X
s−r
+ B
s
,
причем слагаемое A
ss
X
0
встречается лишь при s ≤ r.
Теорема 4.1. Для вычисления векторов (4.2) существует
параллельная форма высоты s(dlog
2
ne+dlog
2
(r +1)e+1) и ширины
n
2
r.
29
Страницы
- « первая
- ‹ предыдущая
- …
- 26
- 27
- 28
- 29
- 30
- …
- следующая ›
- последняя »
