Вычислительные методы алгебры и оценивания. Семушин И.В. - 55 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

3.2 Распараллеливание вычислений
Правая часть b системы (3.1) также может обрабатываться в ходе при-
ведения систе м ы к треугольному в иду, благодаря чему осущес т в ля ется этап
прямой подстановки в равенствах (3.2). Такая обработка правой части b,
выполняемая одновременно с приведением матрицы A к треугольному виду,
также запрещена во всех вариантах лабораторных работ (проектов). Это
требование тоже отвечает реальности, так как позволяет экономить значи-
тельное время в условиях, когда требуется решать одну и ту же систему
(3.1) с различными правыми частями. Ситуация такого рода — об ращ ение
матрицы с помощью ре шения матричного уравнения AX = I, где I — еди-
ничная матрица, т. е. нахождение X = A
−1
. В этом случае правые части b
вводятся в уравнения (3.2) последовательно. При вычислении i-го столбца
матрицы X = A
−1
каждая правая часть равна очередному (i-му) столбцу
единичной матрицы. Для каждого b в (3.2) сначала решают первую систему,
т.е. вычисляют y, а затем — в т о рую систему, т.е. вычисляют x. Существенно,
что для хранения ни y, ни x затрат памяти не требуется: их можно хранить
там же, куда был введен вектор b.
Если A хранится по столбцам, то мы изменим алгоритм LU-разложения,
как это показано на рис. 3.2. На k-м шаге измененного алгоритма сначала
формируется k-й столбец матрицы L; это дост игается векторной операцией
деления. В самом внутреннем цикле (цикле по i) k-й столбец L, умноженный
на число, вычитается из j-го столбца текущей матрицы A; длина столбцов
равна n −k. Таким образом, основной векторной операцией снова является
триада, но тепе рь в качест в е векторов выступают столбцы матрицы L и
текущей матрицы A. В данный алгоритм также возможно внедрить любую
из трех стратегий выбора главного элеме нта (см. подразд. 2.2).
3.2 Распараллеливание вычислений
В этом разделе мы, следуя [8], излагаем некоторые понятия параллельных
вычислений, которые в практике решения линейных систем имеют большое
значение.
Параллельные вычисления реализуются не на обычных (скалярных) ком-
пьютерах, какими являются все персональные компьютеры, а на векторных
или параллельных компьюте рах. Их отличает то, что операндами команд
копьютера являются не отдельные числовые в еличины (скаляры), а целые
группы таких в еличин, объединяемых в векторы или матрицы. Поэтому
векторно-матричные операции для своего выполнения требуют вызова всего
55

Страницы