Введение к работе
-1 -
Актуальность темы. В последние десять-пятнадцать лет интенсивно развиваются численные методы, которые сводят решение краевых задач в областях сложной формы для эллиптических уравнений второго порядка к решению аналогичных задач в простых областях и основаны на разбиении исходной области на более простые подобласти. Такие методы получили название "методы декомпозиции области" ("domain decomposition (DD)") или "методы разбиения области". Особую актуальность эти методы приобрели в связи с появлением многопроцессорных вычислительных систем. Методы декомпозиции области позволяют решать задачи в подобластях независимо друг от друга на разных процессорах, обмениваясь время от времени информацией между процессорами. DD-методы обладают тем преимуществом перед другими эффективными методами решения эллиптических уравнений, что они естественно параллелизуемы, то есть процесс распараллеливания в них очевиден и нагляден для исследователя. Часто DD-алгоритмы определяют через DD-переобуславливатели, для решения систем с которыми достаточно решать системы с матрицами жесткости в подобластях. Под переобуславливате-лем мы понимаем симметричную положительно определенную матрицу, эквивалентную по спектру матрице жесткости в исходной области. Среди критериев для сравнения различных DD-переобуславливателей можно выделить такие, как зависимость границ спектра переобусловленной матрицы жесткости от числа неизвестных, числа подобластей, структуры разбиения, возможного скачка коэффициента диффузии (для оператора диффузии), простота программной реализации и т. д. Исследование свойств известных DD-переобуславливателей и улучшение соответствующих спектральных характеристик представляют собой актуальную научную и прикладную задачу. В настоящей работе рассматриваются два базовых варианта метода декомпозиции области: DD-переобуславливатель типа Нейман-Дирихле и DD-переобуславливатель типа Нейман-Нейман.
Рассматриваемые DD-методы требуют решения задач в подобластях, что на практике часто также является достаточно сложной задачей. Действительно, если число неизвестных в подзадачах достаточно велико, а геометрия подобластей и структура сетки не позволяют использовать быстрые прямые методы решения систем сеточных уравнений в подобластях, то DD-методы становятся неэффективными из-за больших арифметических затрат на решение подзадач. В связи с этим возникает необходимость конструирования алгоритмов с приближенным решением под-
-2-задач. Под приближенным решением мы будем понимать результат и итераций некоторого итерационного процесса с использованием переобу-славливателя для решения системы с матрицей жесткости в подобласти; в частности, при v = 1 и нулевом начальном приближении это эквивалентно решению системы- с переобуславливателем в подобласти. Наряду с разработкой DD-методов с приближенным решением подзадач возникает проблема оптимальности (под оптимальностью мы.понимаем пропорциональность арифметических затрат числу неизвестных) методов разбиения области: предположим, что в подобластях мы можем использовать пере-обуславливатели, оптимальные по арифметическим затратам; как построить DD-переобуславливатель, оптимальный по арифметическим затратам по отношению к числу неизвестных и использующий оптимальные пере-обуславливатели в подобластях?
Рассмотрению этих и некоторых других вопросов посвящена настоящая диссертация.
Цель работы
-
Конструирование методов декомпозиции области с приближенным решением подзадач.
-
Построение DD-переобуславливателя, оптимального по арифметической сложности.
-
Исследование и развитие двух вариантов метода декомпозиции области: DD-переобуславливателя типа Нейман-Дирихле и DD-переобуславливателя типа Нейман-Нейман.
-
Применение разработанных алгоритмов для решения на параллельной вычислительной системе нелинейной задачи об околозвуковом потенциальном обтекании препятствия в трехмерном канале.
Общая методика исследований. В диссертации использованы результаты и методы теории аппроксимации, матричного анализа и матричных итерационных методов, а также элементы функционального анализа.
Научная новизна. Сформулированы методы декомпозиции с приближенным решением подзадач; для случая регулярных триангуляции построен оптимальный по арифметической сложности переобуславлива-тсль. Устранена зависимость числа обусловленности от числа подобластей для метода декомпозиции с альтернирующими краевыми условиями типа Нейман-Дирихле при разбиении на полосы (одноуровневый метод) и на квадраты (двухуровневый метод). На основе метода балансировки для
-3-DD-переобуславливателя типа Нейман-Нейман в случае оператора Гельм-гольца устранена зависимость числа обусловленности от количества подобластей.
Практическая значимость. Разработан комплекс программ, реализующих построенные методы декомпозиции для случая равномерных сеток. Сформулированный DD-метод с разбиением на слои применен для решения нелинейной задачи — околозвукового потенциального потока в трехмерном канале с препятствием — на параллельной вычислительной системе.
Апробация работы. Основные результаты диссертации докладывались на:
семинарах лаборатории вычислительной математики ИВМ РАН, в ВЦ СО РАН (Новосибирск), в Центре информатики БАН (София, Болгария), в университете г. Юваскюла (Финляндия), в университете г. Штуттгарта (Германия), в научном центре IBM (Гейдельберг .Германия), в университете г. Ганновера (Германия),
2-й Всесоюзной конференции по проблемам численного анализа (Тбилиси, 1989), 3-м Международном симпозиуме по численному анализу (Москва, 1992), 1-м Российско-финском симпозиуме по численному анализу (Юваскюла, Финляндия, 1992), DFG-симпозиуме по параллельным алгоритмам для параллельных вычислительных систем типа MIMD (Ганновер, Германия, 1993), 10-м Франко-итало-российском совместном симпозиуме по вычислительной математике и приложениям (Москва, 1993).
Публикации. По теме диссертации опубликовано семь работ, список которых приведен в конце автореферата.
Структура диссертации. Диссертация состоит из введения, четырех глав и списка литературы из 94 наименований. Общий объем работы 122 страницы.
- Л -
