Решение системы линейных уравнений методом Гаусса (Машеров) (Лабораторная работа 3)
Описание файла
Файл "Решение системы линейных уравнений методом Гаусса (Машеров)" внутри архива находится в папке "Лабораторная работа 3". Документ из архива "Лабораторная работа 3", который расположен в категории "". Всё это находится в предмете "параллельные системы и параллельные вычисления" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "лабораторные работы", в предмете "параллельные системы и параллельные вычисления" в общих файлах.
Онлайн просмотр документа "Решение системы линейных уравнений методом Гаусса (Машеров)"
Текст из документа "Решение системы линейных уравнений методом Гаусса (Машеров)"
Национальный исследовательский институт
Московский Энергетический Институт (Технический Университет)
Институт автоматики и вычислительной техники
Кафедра Прикладной математики
Лабораторная работа №3
по дисциплине «Параллельные системы и параллельное программирование»
тема: «Решение системы линейных уравнений методом Гаусса с использованием нитевого распараллеливания.»
Выполнил:
Машеров Д.Е.
А-13-08
Москва
2012 г.
Постановка задачи
Дана линейная система уравнений,представленная в матричном виде, требуется найти решение этой системы с помощью метода Гаусса, используя принципы нитевого (threads) распараллеливания.
Последовательный алгоритм.
Метод Гаусса – широко известный прямой алгоритм решения систем линейных уравнений, для которых матрицы коэффициентов являются плотными. Если система линейных уравнений невырожденна, то метод Гаусса гарантирует нахождение решения с погрешностью, определяемой точностью машинных вычислений. Основная идея метода состоит в приведении матрицы А посредством эквивалентных преобразований (не меняющих решение системы (8.2)) к треугольному виду, после чего значения искомых неизвестных могут быть получены непосредственно в явном виде.
Метод Гаусса включает последовательное выполнение двух этапов. На первом этапе – прямой ход метода Гаусса – исходная система линейных уравнений при помощи последовательного исключения неизвестных приводится к верхнему треугольному виду
,
где матрица коэффициентов получаемой системы имеет вид
На обратном ходе метода Гаусса (второй этап алгоритма) осуществляется определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной , после этого из предпоследнего уравнения становится возможным определение переменной и т.д.
Прямой ход алгоритма Гаусса
Прямой ход метода Гаусса состоит в последовательном исключении неизвестных в уравнениях решаемой системы линейных уравнений. На итерации i, 0 i n-1, метода производится исключение неизвестной i для всех уравнений с номерами k, большими i (т.е. i
Обратный ход алгоритма Гаусса
После приведения матрицы коэффициентов к верхнему треугольному виду становится возможным определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной , после этого из предпоследнего уравнения становится возможным определение переменной и т.д.
Параллельный алгоритм.
В основу параллельной реализации алгоритма Гаусса может быть положен принцип распараллеливания по данным. В качестве базовой подзадачи можно принять все вычисления, связанные с обработкой одной строки матрицы A и соответствующего элемента вектора b.
Выделение информационных зависимостей
Рассмотрим общую схему параллельных вычислений и возникающие при этом информационные зависимости между базовыми подзадачами.
Для выполнения прямого хода метода Гаусса необходимо осуществить (n-1) итерацию по исключению неизвестных для преобразования матрицы коэффициентов A к верхнему треугольному виду.
Выполнение итерации i, 0<=i
При выполнении обратного хода метода Гаусса подзадачи выполняют необходимые вычисления для нахождения значения неизвестных. Далее подзадачи подставляют полученное значение новой неизвестной и выполняют корректировку значений для элементов вектора b.
Результаты вычислительного эксперимента
Эксперементы осуществлялись на компьютере с процессором Intel i7 Сore 950(4 ядра)
-
Размерность матрицы 5 000 * 5 000
Число исполнителей | Время решения, секунд | Ускорение |
1 | 272,667 | |
2 | 144,183 | 1,89 |
3 | 102,892 | 2,65 |
4 | 94,723 | 2,88 |
5 | 93,211 | 2,93 |
6 | 82,778 | 3,29 |
7 | 74,29 | 3,67 |
8 | 69,009 | 3,95 |
-
Размерность матрицы 10 000 * 10 000
Число исполнителей | Время решения, секунд | Ускорение |
1 | 2174,58 | |
2 | 1115,066 | 1,95 |
3 | 765,773 | 2,84 |
4 | 673,226 | 3,23 |
5 | 676,32 | 3,22 |
6 | 603,849 | 3,60 |
7 | 559,695 | 3,89 |
8 | 504,776 | 4,31 |