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

• Автор: Терехов, Андрей Валерьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Новосибирск
• Количество страниц: 134 с. : ил.

Содержание
Введение
Глава 1. Обзор параллельных алгоритмов решения трехдиагональных систем линейных алгебраических уравнений .
Глава 2. Алгоритм параллельной прогонки для решения серии трехдиагональных систем линейных алгебраических уравнений

2.1. Постановка задачи.

2.2. Алгоритм дихотомии

2.2.1. Базовый алгоритм .

2.2.2. Вычисление произвольной компоненты из вектора решения

2.2.3. Основная теорема параллельной прогонки

2.2.4. Дихотомия системы линейных алгебраических уравнений .

2.2.5. Вычислительные и коммуникационные затраты . .

2.3. Реализация алгоритма дихотомии для решения задачи Дирихле для уравнения Пуассона
2.3.1. Метод разделения переменных.
2.3.2. Метод переменных направлений
2.4. Результаты численных экспериментов
Глава 3. Реализация алгоритма дихотомии на мультиком
пыотере. .
3.1. Основные формулы
3.1.1. Вычисление i компонент
3.1.2. I реализация алгоритма дихотомии
3.1.3. Оптимизация межпроцессорных взаимодействий .
3.2. Процесс дихотомии для теплицевых трехдиагональных матриц .
3.2.1. Оптимизация подготовительных вычислений .
3.2.2. Экономичная подготовительная процедура алгоритма дихотомии для решения уравнения Пуассона .
3.3. Результаты численных экспериментов.
Глава 4. Приложение алгоритма дихотомии для моделирования акустических и упругих волновых полей на многопроцессорной вычислительной системе.
4.1. Спектральный метод на основе интегрального преобразования Лагер ра.
4.1.1. Акустические волны
4.1.2. Упругие волны.
4.2. Реализация алгоритма дихотомии для решения эллиптических уравнений с неразделяемыми переменными
4.2.1. Разностная схема
4.2.2. Предобуславливающая процедура
4.3. Результаты вычислительных экспериментов
4.3.1. Оценка производительности параллельного алгоритма
4.3.2. Распространение акустических волн в однородной
4.3.3. Распространение упругих волн в тонком слое .
4.3.4. Распространение упругих волн в среде i
Глава 5. Моделирование взаимодействия электронного релятивистского пучка с плазмой методом частиц в ячейках
5.1. Постановка задачи
5.2. Описание модели и алгоритма решения задачи
5.3. Результаты численных экспериментов.
5.3.1. Возбуждение плазменной волны точечным зарядом
5.3.2. Численное исследование развития двухпотоковой неусто й и вости.
5.3.3. Моделирование бесстолкновитсльного затухания волн
в плазме.
Заключение
Литература


Апробация работы. По мере выполнения работы были сделаны доклады на следующих конференциях и семинарах: Международная конференция Parallel Computing Technologies, РаСТ г. Института Ядерной Физики им. Будксра СО РАН, Новосибирск, г. ИВМиМГ СО РАН Новосибирск, г. ИВМиМГ СО РАН; Научный семинар отдела математических задач геофизики, ИВМиМГ СО РАН(2 доклада); Плазменный семинар ИЯФ им. Г.И. Буд-кера СО РАН; 8-ая международная конференция по открытым системам для удержания плазмы (OS-, 5-9 июля, Новосибирск, Россия); семинар "Проблемы математического и численного моделирования4 Института вычислительного моделирования СО РАН. Публикации. Материалы диссертации опубликованы в 7 печатных работах, из них б статей в рецензируемых журналах, включенных в список ВАК, 1 статья в сборниках трудов конференций. Личный вклад автора. Все выносимые на защиту результаты принадлежат лично автору. Представление результатов совместных исследований в диссертационной работе согласовано с соавторами. Личный вклад соискателя заключается в обсуждении постановок задач; разработке адекватных численных алгоритмов и методов решения; разработке, реализации и тестировании программ, проведении численных экспериментов и интерпретации результатов. СО РАН N0. Рособразования "Развитие научного потенциала ВШ" (проекты РНП 2. РНП 2. РФФИ 4, Фондом содействия отечественной пауке. Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы. Диссертация изложена на 4 страницах, включает библиографический список из 1 наименований работ. Во введении обоснована актуальность работы, сформулирована цель диссертации, приведено краткое изложение полученных результатов. В первой главе дается краткое писание существующих на сегодняшний день алгоритмов параллельной прогонки, проанализированы их основные достоинства, недостатки и область применимости. Во второй главе приведена постановка задачи, рассмотрены вопросы отображения данных задачи на множество процессоров. Сформулирована и доказана "основная теорема параллельной прогонки" , па основе которой предложен новый алгоритм параллельной прогонки (алгоритм дихотомии для решения серии трехдпагональных систем линейных алгебраических уравнений). Получены оценки числа арифметических действий и коммуникационных взаимодействий, необходимые для решения трехдиагональной СЛАУ. На примере параллельной реализации метода переменных направлений и метода разделения переменных для решения задачи Дирихле для уравнений Пуассона показана высокая производительность алгоритма дихотомии как при использовании относительно небольшого числа процессоров, так и нескольких тысяч. Третья глава посвящена реализации процесса дихотомии на основе МРЬл'ехмологии параллельного программирования. Теоретический и на примере численных экспериментов показано, что трехдиагональные матрицы из класса теплицевых можно эффективно обращать как для нескольких, так и для одной правой части. В четвертой главе предложена параллельная реализация численноаналитического алгоритма решения уравнения акустики п динамической задачи теории упругости. В качестве интегрального преобразования по времени выбрано преобразование Лагерра. Приведены результаты численных экспериментов по моделированию распространения акустических и упругих воли в неоднородной среде в аксиалыю-симметрпчпой геометрии. Показано, что моделирование волновых процессов для длительных моментов времени требует использования сеток с высокой разрешающей способностью. В пятой главе рассмотрена реализация алгоритма дихотомии в рамках метода "частиц в ячейках" . На основе проведенных тестов продемонстрирована работоспособность численной модели для изучения турбулентности, возбуждаемой мощным электронным пучком в плазме. Показано согласие результатов численных экспериментов с теорией как для одно части много механизма возбуждения плазменных колебаний, так и для коллективной раскачки двухпотоковой неустойчивости. В заключении дан обзор основных результатов, полученных в диссертационной работе.