ВУЗ:
Составители:
156
Шаг 4: Вычисление нового приближения по соотношению (11.11).
Описанный алгоритм содержит две операции умножения матрицы на век-
тор, четыре операции скалярного произведения и пять операций (сложение и
умножение на скаляр) над векторами. Общее количество операций на одной
итерации
t
1
=2n
2
+13n.
Известно, что точное решение достигается после выполнения n итераций
алгоритма метода сопряженных градиентов. Следовательно, всего необходимо
выполнить
23
1
132 nnT (11.12)
операций, т.е. сложность описанного алгоритма имеет порядок O(n
3
).
11.4 Организация параллельных вычислений
Поскольку итерации алгоритма сопряженных градиентов должны выпол-
няться последовательно, распараллеливание вычислений возможно лишь в пре-
делах одной итерации. Основные вычислительные затраты на каждой итерации
связаны с умножением матрицы A на векторы x и d. Для организации парал-
лельных вычислений в данном случае могут использоваться схемы, рассмот-
ренные в лекции 10.
Кроме того, должны выполняться операции над векторами: скалярное про-
изведение, сложение, умножение на скаляр. Организация этих вычислений
должна согласовываться с принятым способом (типом декомпозиции) умноже-
ния матрицы на вектор. Общая рекомендация может заключаться в том, что при
малом размере векторов возможно дублирование данных, при большой размер-
ности системы уравнений целесообразно осуществлять разделение на блоки.
Анализ эффективности
Анализ эффективности параллельного алгоритма проведем для варианта с
ленточным горизонтальным разделением матрицы, в предположении, что все
Страницы
- « первая
- ‹ предыдущая
- …
- 154
- 155
- 156
- 157
- 158
- …
- следующая ›
- последняя »
