Введение к работе
Диссертационная работа посвящена разработке параллельного алгоритма для решения систем линейных алгебраических уравнений с одной и той же трехдиагональной матрицей и различными правыми частями. Разработанный алгоритм обладает высоким коэффициентом ускорения, в том числе и при использовании нескольких тысяч процессоров. Эффективность предлагаемого подхода продемонстрирована на примере параллельной реализации численно-аналитического метода в рамках решения динамической задачи теории упругости, а также при моделировании взаимодействия релятивистского электронного пучка с плазмой методом "частиц в ячейках" .
Актуальность работы. Прогресс в численных методах решения "больших задач" невозможен без применения мощных параллельно действующих вычислительных систем, поэтому необходимы исследования численных алгоритмов, допускающих эффективную параллельную реализацию.
Проблема решения трехдиагональных систем линейных алгебраических уравнений (СЛАУ) является одной из часто решаемых задач вычислительной математики. Такие системы возникают при трехточечной аппроксимации задач для обыкновенных дифференциальных уравнений второго порядка с постоянными и переменными коэффициентами, а также при реализации разностных схем для уравнений в частных производных. Для решения трехдиагональных СЛАУ используются различные варианты метода прогонки: монотонная, немонотонная, потоковая, встречная, ортогональная.
Разработка и усовершенствование параллельных алгоритмов прогонки представляет значительных интерес, который подтверждается большим количеством публикаций, посвященных решению этой трудной задачи. Анализ работ по данной тематике позволяет сделать вывод о снижении эффективности, а главное масштабируемости существующих на сегодняшний день алгоритмов параллельной прогонки при их реализации на современных многопро-
цессорных системах. Это связано с тем, что эффективные в теоретическом плане параллельные алгоритмы, например алгоритм циклической редукции, будучи реализованными на различных многопроцессорных вычислительных системах, теряют свои преимущества из-за наличия таких операций как коммуникации и синхронизации.
Довольно часто при решении задач конечно-разностными методами требуется решить не одну трехдиагональную СЛАУ, а серию с различными правыми частями, причем число задач в серии может достигать нескольких сотен тысяч. Таким образом, заслуживает внимания вопрос создания эффективного параллельного алгоритма для решения серий СЛАУ с одной и той же трехдиагональной матрицей и различными правыми частями.
Цель диссертационной работы: Разработка и программная реализация параллельного алгоритма для решения трехдиагональных систем линейных алгебраических уравнений на многопроцессорной вычислительной системе.
Для достижения указанной цели были сформулированы и решены следующие задачи:
Разработка параллельного алгоритма для решения систем линейных алгебраических уравнений с одной и той же трехдиагональной матрицей и различными правыми частями.
Разработка параллельного алгоритма для решения систем линейных алгебраических уравнений с теплицевыми(квази-теплицевыми) трехдиаго-нальными матрицами и единственной правой частью.
Исследование эффективности алгоритма параллельной прогонки в различных приложениях
а) решение задачи Дирихле для уравнения Пуассона методом разделения переменных и методом переменных направлений;
б) численно-аналитический метод решения уравнения акустики и ди
намической задачи теории упругости;
в) моделирование взаимодействия релятивистского электронного пуч
ка с замагниченной плазмой методом "частиц в ячейках" .
Научная новизна заключается в том, что
разработан новый параллельный алгоритм для решения трехдиагональ-ных систем линейных алгебраических уравнений, позволяющий достигать значительной величины ускорения, в том числе и при использовании нескольких тысяч процессоров;
предложена высокопроизводительная параллельная реализация метода разделения переменных и метода переменных направлений для решения эллиптических уравнений с разделяемыми переменными;
предложена параллельная реализация численно-аналитического метода для решения уравнения акустики и динамической задачи теории упругости;
с учетом возможности проведения расчетов с использованием тысяч процессоров, на примере моделирования акустических и упругих волновых полей для реальных пространственно-временных масштабов получены практические оценки точности решения для сеток высокого разрешения;
исследована точность метода "частиц в ячейках" при моделировании таких физических явлений как затухание Ландау, двухпотоковая неустойчивость, возбуждение плазменной волны точечным зарядом; показано, что предложенный алгоритм позволяет эффективно использовать ресурсы современных многопроцессорных вычислительных систем и, как
следствие, повысить точность расчетов методом "частиц в ячейках";
Практическая значимость состоит в том, что
разработанный параллельный алгоритм позволяет эффективно реали-зовывать широкий класс численных методов, требующих решения систем линейных алгебраических уравнений с одной и той же трехдиагональнои матрицей и различными правыми частями;
разработанный программный комплекс для решения задач сейсмической разведки позволяет проводить высокоточное моделирование акустических и упругих волновых полей для реальных пространственно-временных масштабов с использованием многопроцессорных вычислительных систем;
разработанный программный комплекс на основе метода "частиц в ячейках" позволяет моделировать процессы релаксации мощных релятивистских электронных пучков в плазме с использованием многопроцессорных вычислительных систем;
На защиту выносятся следующие основные результаты и положения:
Параллельный алгоритм (алгоритм дихотомии) для решения систем линейных алгебраических уравнений с одной и той же трехдиагональнои матрицей и различными правыми частями.
Параллельный алгоритм для решения систем линейных алгебраических уравнений с трехдиагональнои теплицевой матрицей и единственной правой частью.
Параллельный алгоритм и программный комплекс для решения уравнения акустики и динамической задачи теории упругости, позволяющий за счет использования многопроцессорных вычислительных систем проводить высокоточные расчеты для задач сейсмической разведки.
Параллельный алгоритм и программный комплекс для моделирования взаимодействия релятивистского электронного пучка с замагниченной плазмой методом "частиц в ячейках".
Апробация работы. По мере выполнения работы были сделаны доклады на следующих конференциях и семинарах: Международная конференция Parallel Computing Technologies, РаСТ 2007 г.; конкурс молодых учёных Института Ядерной Физики им. Будкера СО РАН, Новосибирск, 2008 г. и 2010 г.; конференция молодых учёных ИВМиМГ СО РАН Новосибирск, 2004 г. и 2010 г.; семинары математическое и архитектурное обеспечение параллельных вычислений(3 доклада), ИВМиМГ СО РАН; Научный семинар отдела математических задач геофизики, ИВМиМГ СО РАН(2 доклада); Плазменный семинар ИЯФ им. Г.И. Будкера СО РАН; 8-ая международная конференция по открытым системам для удержания плазмы (OS-2010, 5-9 июля, Новосибирск, Россия); семинар "Проблемы математического и численного моделирования" Института вычислительного моделирования СО РАН.
Публикации. Материалы диссертации опубликованы в 7 печатных работах, из них б статей в рецензируемых журналах, включенных в список ВАК, 1 статья в сборниках трудов конференций.
Личный вклад автора. Все выносимые на защиту результаты принадлежат лично автору. Представление результатов совместных исследований в диссертационной работе согласовано с соавторами. Личный вклад соискателя заключается в обсуждении постановок задач; разработке адекватных численных алгоритмов и методов решения; разработке, реализации и тестировании программ, проведении численных экспериментов и интерпретации результатов.
Диссертационная работа выполнялась в соответствии с планами Института вычислительной математики и математической геофизики, поддерживалась интеграционным проектом СО РАН No. 26, программами Рособразо-
вания "Развитие научного потенциала ВШ" (проекты РНП 2.1.1/3983, РНП 2.2.1.1/3653), грантами РФФИ 09-02-00594, Фондом содействия отечественной науке.
Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы. Диссертация изложена на 134 страницах, включает библиографический список из 141 наименований работ.
