Теория и практика параллельных вычислений
Алгоритм Гаусса
Метод Гаусса включает последовательное выполнение двух этапов. На первом этапе – прямой ход метода Гаусса – исходная система линейный уравнений при помощи последовательного исключения неизвестных (при помощи эквивалентных преобразований) приводится к верхнему треугольному виду. На обратном ходе метода Гаусса (второй этап алгоритма) осуществляется определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной xn-1, после этого из предпоследнего уравнения становится возможным определение переменной xn-2 и т.д.
При внимательном рассмотрении метода Гаусса можно заметить, что все вычисления сводятся к однотипным вычислительным операциям над строками матрицы коэффициентов системы линейных уравнений. Как результат, в основу параллельной реализации алгоритма Гаусса может быть положен принцип распараллеливания по данным. В этом случае матрицу А можно разделить на горизонтальные полосы, а вектор правых частей b – на блоки. Полосы матрицы и блоки вектора правых частей распределяются между процессорами вычислительной системы.
Для выполнения прямого хода метода Гаусса необходимо осуществить (n-1) итерацию по исключению неизвестных для преобразования матрицы коэффициентов A к верхнему треугольному виду.
Выполнение итерации i, 0i<n-1, прямого хода метода Гаусса включает ряд последовательных действий. Процессор, на котором расположена строка i матрицы, должен разослать ее и соответствующий элемент вектора b всем процессорам, которые содержат строки с номерами k, k>i. Получив ведущую строку, процессоры выполняют вычитание строк, обеспечивая тем самым исключение соответствующей неизвестной xi.
При выполнении обратного хода метода Гаусса процессоры выполняют необходимые вычисления для нахождения значения неизвестных. Как только какой-либо процессор определяет значение своей переменной xi, это значение должно быть разослано всем процессорам, которые содержат строки с номерами k, k<i. Далее процессоры подставляют полученное значение новой неизвестной и выполняют корректировку значений для элементов вектора b.
Задания и упражнения
- В активном окне вычислительного эксперимента системы ПараЛаб установите топологию Полный граф. Выберите число процессоров, равное десяти. Сделайте текущей задачей этого окна задачу решения системы линейных уравнений.
- Выберите метод Гаусса решения задачи и выполните вычислительный эксперимент. Пронаблюдайте маршруты передачи данных при выполнении алгоритма.
