Анализ эффективности

Выполним анализ эффективности первого параллельного алгоритма умножения матриц.

Общая трудоемкость последовательного алгоритма, как уже отмечалось ранее, является пропорциональной n³. Для параллельного алгоритма на каждой итерации каждый процессор выполняет умножение имеющихся на процессоре полос матрицы А и матрицы В(размер полос равен n/p, и, как результат, общее количество выполняемых при этом умножении операций равно n³/p² ). Поскольку число итераций алгоритма совпадает с количеством процессоров, сложность параллельного алгоритма без учета затрат на передачу данных может быть определена при помощи выражения

(7.4)

С учетом этой оценки показатели ускорения и эффективности данного параллельного алгоритма матричного умножения принимают вид:

Лекция 8

Параллельное решение систем линейных уравнений Алгоритм решения систем линейных уравнений методом Гаусса.

Системы линейных уравнений возникают при решении многих прикладных задач. Матрицы коэффициентов систем линейных уравнений могут иметь различные структуру и свойства. Мы будем полагать, что решаемая система имеет плотную матрицу высокого порядка. Линейная система n уравнений с n неизвестными , , …, может быть представлена в виде Ax=b. Здесь n×n-матрица A и n×1-вектор b составлены из вещественных чисел, а задача заключается в нахождении неизвестного вектора x.

………………

Метод Гаусса – широко используемый алгоритм решения систем линейных уравнений с невырожденной матрицей A. Метод заключается в приведении матрицы А системы к верхнему треугольному виду путем последовательных эквивалентных преобразований (прямой ход), с последующей последовательной подстановкой (обратный ход). К числу эквивалентных преобразований относятся:

• умножение любого из уравнений на ненулевую константу;

• перестановка уравнений;

• прибавление к уравнению любого другого уравнения системы.

Прямой ход метода Гаусса состоит в последовательном исключении неизвестных в уравнениях решаемой системы линейных уравнений. На итерации i, 0 ≤ i<n–1 метода производится исключение неизвестной i для всех уравнений с номерами k, большими i (т.е. i<k≤n–1). Для этого из этих уравнений осуществляется вычитание строки i, умноженной на константу ( / ), с тем чтобы результирующий коэффициент при неизвестной xi в строках оказался нулевым. Вычисления, выполняемые над элементами матрицы A и вектора b, определяются следующими соотношениями:

0≤ i <n-1 ; i< k ≤ n-1 ; i≤ 0 ≤ n-1

Выполнение прямого хода метода Гаусса покажем на примере системы:

На первой итерации производится исключение неизвестной из второй и третьей строк. Для этого из этих строк нужно вычесть первую строку, умноженную соответственно на 2 и 1. После этих преобразований система уравнений принимает вид

В результате остается выполнить последнюю итерацию и исключить неизвестную из третьего уравнения. Для этого необходимо вычесть вторую строку, при этом система принимает вид: