Решение задач на тему: Ресурсы. Вычислительный кластер. Библиотеки. Метод gмrеs тне gеnеrаlizеd мiniмuм rеsiduаl

Введение

В результате сеточных аппроксимаций уравнений в частных производных могут возникнуть большие разреженные системы линейных уравнений (СЛАУ): Аx = b. В больших системах число неизвестных вполне может достигать ~ 107 ÷ 108. Разреженной система является, если количество ненулевых элементов данной матрицы А размерности n*n составляет величину О(n). Для хранения матриц такого типа используется специальный метод CSR, который будет рассмотрен подробнее.

Такие задачи, как правило, трудно решать без распараллеливания процесса вычислений с использованием кластеров - многопроцессорных ЭВМ с распределенной памятью.

В данной работе рассмотрено создание эффективного параллельного алгоритма переобусловленного метода GMRES (General Minimum Residual Method) для несимметрических блочных трехдиагональных систем линейных алгебраических уравнений с использованием кластеров. В качестве основы для распараллеливаемого алгоритма был выбран аддитивный метод Шварца[4,5]. Этот метод основывается на декомпозиции физической расчетной области в рамках некоторой итерационной процедуры. При реализации данного метода возникают проблемы при "склейке" решений в подобластях. Эти проблемы связаны со способом взаимодействия процессоров и способом передачи информации, а также с необходимостью минимизировать количество арифметических действий.

Первый пункт данной работы посвящен используемым в ней ресурсам. К этим ресурсам относятся библиотека MPI, предназначенная для разработки параллельного кода, и библиотека Intel® Math Kernel Library, в которую входит прямой решатель PARDISO, функция умножения матрицы на вектор DCSRMV и функция умножения двух матриц DCSRMM. Также в пункте 1 описаны характеристики кластера, на котором тестировалась программа.

Во втором пункте описан общий вид системы линейных алгебраических уравнений, возникающий в результате сеточных аппроксимаций уравнений в частных производных. Также в этом пункте описан специальный метод хранения разреженных матриц CSR и метод GMRES, который лег в основу данной работы.

К упомянутым ранее проблемам, возникающим при "склейке" решений в подобластях, относится вычисление переобуславливателя, умножение матрицы на вектор и вычисление скалярного произведения при перекрывании подобластей в методе декомпозиции области. Этому посвящен четвертый пункт работы, в котором описан параллельный алгоритм переобусловленного метода GMRES: параметры метода, способ распределения данных по процессорам, построение параллельного переобуславливателя.

Оглавление

- 1. введение

- Ресурсы

- Вычислительный кластер

- Библиотеки

- Метод gmres the generalized minimum residual

- Переобусловленный метод gmres

- Параллельный переобуславливатель

- Параллельный переобусловленный метод с распределенной памятью

- Сетевой закон Амдала

- Численные эксперименты

- Результаты

- Заключение

- Список литературы

Заключение

Цель данной работы заключалась в разработке и реализации параллельного метода для решения задачи линейной алгебры Ах=b с несимметричной матрицей А. Проблема создания параллельного кода наиболее актуальна в случаях, когда необходимо решать СЛАУ с сотнями миллионов неизвестных(n~107-108), потому как решение подобных задач на одном компьютере требует большого количества времени. Для систем меньшей размерности подобные методы также позволяют получить существенное сокращение времени решения.

В рамках метода декомпозиции области и на основании описанного в данной работе переобусловленного метода обобщенных невязок была реализована и протестирована параллельная программа, использующая встроенные библиотеки Интела.

Тестирование показало хорошую параллельность метода, уменьшение времени при увеличении числа узлов на кластере.

Таким образом, можно считать цель данной работы выполненной.

Список литературы

1. Мацокин А.М. Конспект лекций: Вычислительные методы линейной алгебры. (http://mmfd.nsu.ru/def_koi.htm)

2. Программирование для многопроцессорных систем в стандарте MPI: Пособие / Г. И. Шпаковский, Н. В. Серикова. - Мн.: БГУ, 2002..

. Ю.М.Лаевский, А.М.Мацокин. Методы декомпозиции решения эллиптических и параболических краевых задач. - СибЖВМ, 1999, т.2, © 4, 361-372.

4. Мацокин А.М., Непомнящих С.В. Метод альтернирования Шварца в подпространстве // Известия высш. учебных заведений. Математика.1985. N. 10, Р. 61-66.

6. Корнеев В.Д. Параллельное программирование в MPI. - Новосибирск 2002.