Составители:
Рубрика:
матрицей (см. (7.4)); благодаря теореме 6.3 это можно сделать
с помощью параллельной формы высоты O(log
2
2
n) и ширины
O(n
3
).
4. На четвертом этапе вычисляется матрица A
−1
по формуле
(7.2) с использованием схемы сдваивания (для всех n
2
элемен-
тов одновременно) с помощью параллельной формы высотой
O(log
2
n) и шириной O(n
3
).
Для наглядности результаты представим в таблице.
Содержание этапа Высота Ширина
Вычисление степеней A
2
, . . . , A
n
O(log
2
2
n) O(n
4
)
Вычисление следов s
k
, k = 1, . . . , n O(log
2
n) O(n
2
)
Вычисление коэффициентов c
k
O(log
2
2
n) O(n
3
)
Вычисление матрицы A
−1
O(log
2
n) O(n
3
)
Из предыдущих рассуждений и приведенной таблицы видно,
что доказано следующее утверждение.
Теорема 7.1. Для вычисления обратной матрицы n-го по-
рядка существует параллельная форма высоты O(log
2
2
n) и шири-
ны O(n
4
).
40
Страницы
- « первая
- ‹ предыдущая
- …
- 37
- 38
- 39
- 40
- 41
- …
- следующая ›
- последняя »
