Новости
О Центре
Кластер
Обучение
Основной курс по параллельному программированию
Учебные курсы
Магистратура
Дополнительное образование
Работы студентов
Библиотека
Исследования
Конференции
Полезные ссылки
NVIDIA
Контакты
О сайте
Имя:
Пароль:
запомнить:
Забыли пароль? Регистрация

Параллельное решение систем линейных уравнений.

Цель лабораторной работы

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

  • Определение задачи решения системы линейных уравнений
  • Изучение последовательного алгоритма Гаусса решения систем линейных уравнений
  • Разработка параллельного алгоритма Гаусса
  • Анализ эффективности параллельных вычислений в отдельности для прямого и обратного этапов метода Гаусса
  • Реализация параллельного алгоритма Гаусса решения систем линейных уравнений

Введение

Системы линейных уравнений возникают при решении многих прикладных задач. Матрицы коэффициентов систем линейных уравнений могут иметь различные структуру и свойства. Мы будем полагать, что решаемая система имеет плотную матрицу высокого порядка. Линейная система n уравнений с n неизвестными x0, x1, …, xn-1 может быть представлена в виде:

В более кратком (матричном) виде система имеет вид

где A=a(i,j) есть вещественная матрица размера n×n, а вектора b и x состоят из n элементов.

Под задачей решения системы линейных уравнений для заданных матрицы А и вектора b обычно понимается нахождение значения вектора неизвестных x, при котором выполняются все уравнения системы.
Метод Гаусса является широко известным прямым алгоритмом решения систем линейных уравнений, для которых матрицы коэффициентов являются плотными. Если система линейных уравнений является невырожденной, то метод Гаусса гарантирует нахождение решения с погрешностью, определяемой точностью машинных вычислений. Основная идея метода состоит в приведении матрицы А посредством эквивалентных преобразований (не меняющих решение системы) к треугольному виду, после чего значения искомых неизвестных может быть получено непосредственно в явном виде.

Изучение последовательного алгоритма Гаусса решения систем линейных уравнений

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

  • Умножение любого из уравнений на ненулевую константу
  • Перестановка уравнений
  • Прибавление к уравнению любого другого уравнения системы
Метод Гаусса включает последовательное выполнение двух этапов. На первом этапе – прямой ход метода Гаусса – исходная система линейных уравнений при помощи последовательного исключения неизвестных приводится к верхнему треугольному виду

где матрица коэффициентов получаемой системы имеет вид

На обратном ходе метода Гаусса (второй этап алгоритма) осуществляется определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной xn-1, после этого из предпоследнего уравнения становится возможным определение переменной xn-2 и т.д.

Прямой ход метода Гаусса

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

На рисунке представлена общая схема состояния данных на i-ой итерации прямого хода алгоритма Гаусса. Все коэффициенты при неизвестных, расположенные ниже главной диагонали и левее столбца i, уже являются нулевыми. На i-ой итерации прямого хода метода Гаусса осуществляется обнуление коэффициентов столбца i, расположенных ниже главной диагонали, путем вычитания строки i, умноженной на нужную ненулевую константу. После проведения (n-1) подобной итерации матрица, определяющая систему линейных уравнений, становится приведенной к верхнему треугольному виду.

При выполнении прямого хода метода Гаусса строка, которая используется для исключения неизвестных, носит наименование ведущей, а диагональный элемент ведущей строки называется ведущим элементом. Как можно заметить, выполнение вычислений является возможным только, если ведущий элемент имеет ненулевое значение. Более того, если ведущий элемент a(i,i) имеет малое значение, то деление и умножение строк на этот элемент может приводить к накоплению вычислительной погрешности и вычислительной неустойчивости алгоритма.
Возможный способ избежать подобной проблемы может состоять в следующем – при выполнении каждой очередной итерации прямого хода метода Гаусса следует определить коэффициент с максимальным значением по абсолютной величине в столбце, соответствующем исключаемой неизвестной, т.е.

и выбрать в качестве ведущей строку, в которой этот коэффициент располагается (данная схема выбора ведущего значения носит наименование метода главных элементов).

Обратный ход алгоритма Гаусса

После приведения матрицы коэффициентов к верхнему треугольному виду становится возможным определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной xn-1, после этого из предпоследнего уравнения становится возможным определение переменной xn-2 и т.д. В общем виде, выполняемые вычисления при обратном ходе метода Гаусса могут быть представлены при помощи соотношений:

Определим вычислительную сложность метода Гаусса. В прямом ходе алгоритма для выбора ведущей строки на каждой итерации должно быть определено максимальное значение в столбце с исключаемой неизвестной. По мере исключения неизвестных количество строк и элементов в строках сокращается.
Текущее число элементов строки (включая правую часть), с которыми производятся действия сложения и вычитания (первый элемент без вычислений полагается равным нулю), равно (n-i), где i, – номер итерации прямого хода. Поскольку кроме выполнения двух операций (умножения и вычитания) с каждым элементом строки предварительно должен быть вычислен масштабирующий коэффициент aik/aii, общие затраты на выполнение действий в одной строке составят 2(n-i)+1 операций.
С учетом того, что на каждой итерации обрабатывается n-i строк, общее число операций в прямом ходе метода Гаусса определяется выражением

Для реализации обратного хода на каждой i-й итерации,(итерация для удобства присваиваем номера от n-2 до 0) необходимо произвести n-i-1 умножений, столько же вычитаний, а также одно деление для определения очередной неизвестной. Следовательно, общая вычислительная сложность обратного хода составит

Суммируя затраты на реализацию прямого и обратного хода, получаем

В последнем равенстве пределы и порядок суммирования изменены с учетом замены j=n-i.

Используя формулы суммирования,

получаем следующее соотношение для оценки вычислительной сложности метода Гаусса при его реализации в виде последовательного алгоритма:

Вычислительная сложность алгоритма Гаусса имеет порядок O(n3).

Построение параллельного алгоритма решения методом Гаусса

Поскольку решение методом Гаусса сводится к последовательности однотипных вычислительных операций умножения и сложения над строками матрицы, в качестве подзадач можно принять вычисления, связанные с обработкой одной или нескольких строк матрицы A и соответствующего элемента вектора b. Каждая итерация, связанная с решением очередной подзадачи, начинается с выбора ведущей строки. Ищется строка с наибольшим по абсолютной величине значением среди элементов i-го столбца, соответствующего исключаемой переменной xi.
Поскольку строки матрицы A закреплены за разными подзадачами, для поиска максимального значения в столбце подзадачи с номерами k, должны обменяться элементами при исключаемой переменной xi. После сбора всех указанных коэффициентов может быть определено, какая из подзадач содержит ведущую строку и какое значение является ведущим элементом.
Для продолжения вычислений ведущая подзадача должна разослать свою строку матрицы A и соответствующий элемент вектора b всем остальным подзадачам с номерами k, kxi.
В обратном ходе метода Гаусса, как только какая-либо, например i–я подзадача, определила свою переменную xi, это значение рассылается всем подзадачам с номерами k. В каждой подзадаче полученное значение неизвестной умножается на соответствующий коэффициент и выполняется корректировка соответствующего элемента вектора b.

Масштабирование и распределение подзадач по процессорам

В качестве подзадач могут быть взяты строки матрицы A, каждая из которых при этом закрепляется за одним процессором. Если число строк матрицы больше, чем число доступных процессоров (s, подзадачи можно укрупнить, объединив несколько строк матрицы.

Анализ эффективности параллельных вычислений метода Гаусса

Пусть n – порядок системы линейных уравнений, а s, s – число используемых процессоров, т.е. матрица А имеет размер n×n, а n/s – размер полосы на каждом процессоре (для простоты полагаем, что n/s – целое число). Определим сложность параллельного варианта метода Гаусса.
В прямом ходе алгоритма для выбора ведущей строки на каждой итерации и каждом процессоре должно быть определено максимальное значение в столбце с исключаемой неизвестной в пределах закрепленной за ним полосы. По мере исключения неизвестных количество строк в полосах сокращается. После сбора полученных максимальных значений, определения и рассылки ведущей строки на каждом процессоре выполняется вычитание ведущей строки из каждой строки оставшейся части строк своей полосы матрицы A.
Как мы установили выше, общие затраты на выполнение действий в одной строке на i-й итерации, составляет 2(n-i)+1 операций. Если применена циклическая схема распределения данных между процессорами, то на i-й итерации каждый процессор будет обрабатывать примерно (n-i)/s строк.
С учетом сказанного, общее число операций параллельного варианта прямого хода метода Гаусса определяется выражением

Заметим, что (n-i)/s, как правило, не будет целым. Для построения приближенных достаточных оценок не будем учитывать операцию округления, но на каждой итерации введем операции с одной дополнительной строкой:

На каждой i-й итерации обратного хода после рассылки очередной вычисленной неизвестной на каждом процессоре обновляются значения правых частей для (n-i)/s еще не обработанных строк из числа закрепленных за ним n / s строк. Поскольку для каждой правой части выполняются 2 операции (умножение и вычитание), общее число операций, необходимых для обновления всех правых частей, составит

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

Наконец, для построения приближенных достаточных оценок, как и ранее, отменим операцию округления и добавим 2(n-1) операций, которые могут дополнительно иметь место на всех 2(n-1) итерациях обновления правых частей, если в результате округления на каждой добавляется одна строка. Тогда оценка сверху общих вычислительных затрат для реализации обратного хода составит

Таким образом суммарные затраты на реализацию прямого и обратного хода составят

Как и ранее осуществим замену j=n-i, при этом пределы суммирования при записи слагаемых в обратном порядке будут j=2..n. Тогда

Применяя те же, что и ранее, элементарные формулы для подсчета сумм, получаем

Если это допустимо, при больших n можно применять приближенную оценку:

Учтем теперь затраты на передачу данных. В прямом ходе на каждой итерации для определения ведущей строки процессоры обмениваются найденными в своей полосе максимальными значениями в столбце с исключаемой переменной. Для выполнения этой операции необходимо log2(s) шагов. С учетом количества итераций общие затраты на передачу максимальных значений

где α – латентность сети передачи данных, β – пропускная способность сети, и ω – размер пересылаемого элемента данных.

На каждой итерации прямого хода метода Гаусса выполняется также рассылка выбранной ведущей строки. Сложность данной операции передачи данных определяется величиной

Наконец, при выполнении обратного хода алгоритма Гаусса на каждой итерации осуществляется рассылка всем процессорам значения очередной вычисленной неизвестной. Общее время, затрачиваемое на рассылку:

Таким образом общая сложность параллельного алгоритма Гаусса составляет

где τ – время выполнения одной вычислительной операции.

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

Нетрудно заметить, что при достаточно большом n и отсутствии потерь на коммуникации могут достигаться значения ускорения и эффективности близкие к предельно возможным: s и 1 соответственно. При малых n характеристики быстро падают. Например, непосредственным подсчетом легко установить, что при n =5 и s =10 ускорение составит около 5,8.

Заключение

В данной лабораторной работе была реализована параллельная программа, которая выполняет решение системы линейных уравнений методом Гаусса. Метод Гаусса является широко известным прямым алгоритмом решения систем линейных уравнений. Если система линейных уравнений является невырожденной, то метод Гаусса гарантирует нахождение решения. В данной курсовой работе также были приведены оценки трудоемкости метода Гаусса в его последовательном и параллельном варианте, а также оценки ускорения и эффективности. На основе полученных результатов можно сделать вывод, что при достаточно большом n и отсутствии потерь на коммуникации могут достигаться значения ускорения и эффективности близкие к предельно возможным: s и 1, при малых же n характеристики быстро падают.

Вычислительные эксперименты

Авторы

Группа: 84-10

Антонова Любовь

Королёв Александр

Новости

22.10.2012
04.09.2012
05.04.2012
06.03.2012
02.03.2012