Лекции по параллельным вычислениям. Гергель В.П - 154 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

154
/nwslognnii
s
T
n
i
s
231123
1
2
2
23
, (11.15)
где τ – время выполнения одной вычислительной операции.
С использованием приближенных оценок вычислительной сложности по-
следовательного (11.6) и параллельного (11.11) алгоритмов можно построить
также оценки ускорения и эффективности:
23
155
6
15
3
21
2
3
3
2
2
223
23
nw
slognnnnn
s
nn
R , (11.16)
23
155
6
15
3
2
2
3
3
2
2
223
23
nw
slognsnnsnn
nn
E
s
. (11.17)
Нетрудно заметить, что при достаточно большом n и отсутствии потерь на
коммуникации могут достигаться значения ускорения и эффективности близкие
к предельно возможным: s и 1 соответственно. При малых n характеристики
быстро падают. Например, непосредственным подсчетом легко установить, что
при n =5 и s =10 ускорение составит около 5,8.
11.3. Последовательный алгоритм метода сопряженных градиентов
Наряду с методом исключения Гаусса для решения систем линейных урав-
нений широко используются итерационные алгоритмы, в которых строится по-
следовательность приближений x
0
, x
1
, ..., x
k
, .... к искомому точному решению x
*
системы (1). Процесс строится так, что очередное приближение дает оценку
точного решения с меньшей погрешностью, и при увеличении числа шагов
оценка точного решения может быть получена с любой требуемой точностью.
К преимуществам итерационных методов можно отнести сравнительно ма-
лый объем вычислений при решении разреженных систем, возможность быст-

Страницы