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

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА1. ПАРАЛЛЕЛЬНЫЕ ВАРИАНТЫ НЕКОТОРЫХ ИТЕРАЦИОННЫХ МЕТОДОВ С ФАКТОРИЗОВАННОЙ МАТРИЦЕЙ ПРЕДОБУСЛОВЛИВА-НИЯ ДЛЯ РЕШЕНИЯ ДВУМЕРНЫХ ЭЛЛИПТИЧЕСКИХ УРАВНЕНИЙ НА ОРТОГОНАЛЬНЫХ СЕТКАХ
§1. Пар аллельные варианты методов MICCG(O), MAFCG, ICCG(O) для решения эллиптических уравнений на равномерной ортогональной сетке 1 .Матрицы предобусловлнвания и алгоритмы параллельного варианта 1 метода MICCG(O), параллельных вариантов методов MAFCG, ICCG(O) для решения эллиптических уравнений на равномерной ортогональной сетке
2.Теоретическое исследование скорости сходимости параллельного варианта 1 метода MICCG(O) и параллельного варианта MAFCG
3.Параллельный вариант 2 метода MICCG(O) для решения эллиптических уравнений на равномерной ортогональной сетке
•1. Результаты расчетов §2.Параллельные варианты метода MICCG(O) для решения эллиптических уравнений на неравномерной ортогональной сетке
1.Теоретическое обоснование автоматического выбора итерационных параметров
2.Рсзультаты расчетов
§3.Параллельные варианты методов с факторизованной матрицей предобусловлнвания для решения эллиптических уравнений на локально измельчающихся сотках на основе прямоугольных элементов
1.Разностные схемы для решения эллиптического уравнения на локально измельчающейся сетке
2. Итерационные методы с факторизованной матрицей предобусловлнвания для решения дискретного эллиптического уравнения
кого уравнения на локально измельчающейся сетке
3. Параллельные варианты методов VICCG, VMICCG для решения эллиптических уравнения на локально измельчающихся сетках
4. Результаты численных расчетов Выводы к главе 1
ГЛАВА2. ПАРАЛЛЕЛЬНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ С ФАКТОРИЗОВАННЫМИ МАТРИЦАМИ ПРЕДОБУСЛОВЛИАНИЯ ДЛЯ РЕШЕНИЯ ДВУМЕРНЫХ ЭЛЛИПТИЧЕСКИХ УРАВНЕНИЙ НА ТРЕУГОЛЬНЫХ СЕТКАХ
§1.Параллельные итерационные методы с факторизованными матрицами предобусловлнвания для решения дискретных эллиптических уравнений на равномерной треугольной сетке
1. Упорядочение узлов сетки DD01 и алгоритм параллельных вариантов методов VICCG и VMICCG
2. Теоретическое исследование скорости сходимости параллельного варианта метода VMICCG и выбор итерационных параметров для модельной задачи
5
21
21
21
28
38
41
50
50
54
57
57
G1
63
65
68
70
70
70
75
2
3. Другие способы упорядочения узлов сетки и алгоритмы параллельных аналогов метода УМЮСв
4. Результаты численных расчетов
§2. Параллельные итерационные методы с факторизованными матрицами предобусловливания для решения дискретных эллиптических уравнений на неструктурированных треугольных сетках
1. Методы УЮСв, УМЮСС и их параллельные варианты для решения эллиптических уравнений на неструктурированной треугольной сетке
2. Результаты численных расчетов
§3. Параллельные варианты метода УМЮСС для решения дискретных эллиптических уравнений с сильно отличающимися коэффициентами на треугольной сетке
1. Теоретическое обоснование автоматического выбора итерационных параметров
2. Результаты расчетов Выводы к главе 2
ГЛАВАЗ. ПАРАЛЛЕЛЬНЫЕ ВАРИАНТЫ ПОПЕРЕМЕННО-ТРЕУГОЛЬ-0Г0 МЕТОДА СОПРЯЖЕННЫХ ГРАДИЕНТОВ ДЛЯ РЕШЕНИЯ ДВУМЕРНЫХ И ТРЕХМЕРНЫХ ЭЛЛИПТИЧЕСКИХ УРАВНЕНИЙ §1. Пар аллельные варианты попеременно-треугольного метода для решения двумерных эллиптических уравнении
1. Матрица предобусловливания и алгоритм параллельного варианта 1 метода ПТМСГ для решения эллиптических
уравнений
2.Матрица предобусловливания и алгоритм параллельного варианта 2 метода ПТМСГ для решения эллиптических
уравнении
3.Теоретическое исследование скорости сходимости параллельного варианта метода ПТМСГ для модельной задачи
4. Возможные обобщения
5. Результаты расчетов
§2. Параллельные варианты попеременно-треугольного метода для решения трехмерных эллиптических уравнении
1.Параллельный вариант 3 попеременно-треугольного метода для решения эллиптических уравнений
2. Параллельный вариант 4 попеременно-треугольного метода для решения эллиптических уравнений
3. Результаты расчетов Выводы к главе 3
ГЛАВА 4. ПАРАЛЛЕЛЬНЫЙ ВАРИАНТ МЮСС(О) ДЛЯ РЕШЕНИЯ ТРЕХМЕРНЫХ ЭЛЛИПТИЧЕСКИХ УРАВНЕНИЙ И ПРИМЕНЕНИЕ ПАРАЛЛЕЛЬНЫХ ВАРИАНТОВ ШССС(О)
ДЛЯ РЕШЕНИЯ ЗАДАЧ ГИДРОДИНАМИКИ
§1.Параллельный вариант метода М1ССС(0) для решения трехмерных эллиптических уравнений на ортогональной равномерной сетке
1.Матрица предобусловливания и алгоритм параллельного варианта метода МЮСС(О)
81
84
80
89
94
102
102
106
108
110
110
НО
117
121
127
127
131
131
138
140
143
145
145
145
3
2. Теоретического исследования скорости сходимости параллельного варианта М1ССС(0) для решения трехмерных задач 149
3. Результаты расчетов 151 §2. Численное моделирование течения вязкой несжимаемой жидкости
в кубической каверне 154
1. Квазигидродинамические уравнения и постановка задачи о течении жидкости в кубической каверне с подвижной верхней крышкой 154
2. Вычислительный алгоритм 157
3. Результаты расчетов 159
§3. Численное моделирование термокапиллярной конвекции в прямоугольной полости в условиях пониженной гравитации 161
1. Постановка задачи 161
2. Вычислительный алгоритм 165
3. Результаты расчетов 165
Выводы к главе 4 167
ЗАКЛЮЧЕНИЕ 169
ЛИТЕРАТУРА 173
ПРИЛОЖЕНИЯ 181
Список сокращений 182
Приложения к главе 2 183
Приложение 1 184
Приложение 2 186
Приложения к главе 4 195
Приложение 1 196
Приложение 2 211
4
ВВЕДЕНИЕ
В последние десятилетия наблюдается бурное развитие вычислительной техники, создание высокопроизводительных вычислительных комплексов и систем, содержащих несколько сотен или даже тысяч процессоров с большим объемом оперативной памяти, высокой производительностью и большой скоростью обмена данными между процессорами. Так например создан Межведомственный Суперкомпьютсриый Центр МВС 1000М [48], содержащий 768 процессоров АЬрЬа 21264 с объемом оперативной на процессор 1 Гб, при этом общий объем оперативной памяти решающего поля 768 Гб. Такой объем оперативной памяти позволяет производить вычисления с большими массивами данных, что в свою очередь позволяет использовать подробные сетки для аппроксимации уравнений и благодаря этому повысить точность расчетов физических задач. Кроме того появилась возможность генерации неструктурированных треугольных сеток большого объема и расчета на них сложных прикладных задач в областях с произвольной геометрией. Высокая производительность процессоров и скорость обмена данными позволяют за разумное время решать сложные нестационарные задачи. Однако при использовании современных многопроцессорных ЭВМ возникает вопрос адаптации к ним существующих однопроцессорных методов и алгоритмов или создания новых.
Адаптация алгоритмов решения нестационарных задач с использованием явных схем [42] для аппроксимации дифференциальных уравнений в настоящее время успешно решена [6,9,13,51]. Однако численное решение уравнений с использованием явных схем, особенно уравнений параболического типа, накладывает жесткие ограничения на шаг по времени [42], тем самым увеличивая время расчета задачи. Использование неявных схем связано с необходимостью решения систем линейных уравнений с сильно разреженной и как правило плохо обусловленной матрицей, что даже в случае использования однопроцессорных ЭВМ является весьма трудоемким [42,45,58,134]. Особенно сложным является решение таких систем в случае аппроксимации дифференциальных уравнений на неструктурированные сетки.
К необходимости решения систем линейных уравнений мы приходим также при решении дискретных аналогов двумерных и трехмерных краевых задач для эллиптических уравнений второго порядка. Следует отметить, что при численном решении многих нсстацноиаршых задач математической физики основная часть вычислительных затрат приходится именно на решение краевых задач для двумерных или трехмерных эллиптических уравнений. К таким задачам относятся задачи радиационной газовой динамики, гидродинамики, некоторые задачи микроэлектроники, задачи диффузии, нефтедобычи и другие.
Проблема адаптации методов решения систем линейных уравнений с разреженной матрицей является очень сложной. В настоящее время решение этой проблемы находится на начальной стадии. Существующие параллельные методы решения систем линейных уравнений, возникающих в результате аппроксимации дифференциальных уравнений, либо имеют относительно невысокую скорость сходимости (особенно при большом числе неизвестных), либо очень сложны для реализации, либо имеют ограниченную область применимости.
В настоящее время не существует достаточно хорошо разработанных библиотек для решения систем линейных уравнений с разреженной матрицей, которые можно было бы использовать для расчетов на произвольной параллельной вычислительной системе [80]. Все они находятся в стадии разработки. Для решения систем линейных
уравнений с заполненой матрицей наиболее известны пакет ScaLAPACK [137], включающий в основном прямые методы, NAG Parallel Library [108]. Среди библиотек решения систем линейных уравнений с разреженной матрицей следует отметить Aztec (параллельная библиотека итерационных методов ), BlockSolvc 95, DOUG (Domain decomposition on Unstructured Grids), P-Sparslib, информация о которых находится в интернете (http://www.parallcl.ni/tecb/tcch dev/par libs.html). Вообще говоря, параллельных численных библиотек немного, доступ к ним бывает затруднен по коммерческим соображениям.
Поэтому решение нестационарных задач математической физики на многопроцессорных ЭВМ осуществляется как правило с использованием явных схем [126].
В настоящей диссертации мы остановимся на численном решении краевых задач для эллиптического уравнения вида
где х<* > с > 0, а = 1,...,тп - непрерывные или кусочно непрерывные функции, т - размерность пространства, х = (хі,хз) для двумерных по пространству задач и х — (хі,Х2,х3) для трехмерных задач. Область Є -прямоугольная, или двумерная односвязная, или прямоугольный параллелипипед. В результате аппроксимации краевой задачи получим систему линейных алгебраических уравнений вида
с сильно разреженной симметричной положительно определенной матрицей А. Вид матрицы Л зависит от разностной сетки, введенной в области G, и способа построения дискретного аналога дифференциального уравнения. Заметим, что матрица А является как пр:шило плохо обусловленной.
Приведенное выше эллиптичекое уравнение можно р.тссматривать в качестве некоторой модели, на численном решении которой аппробируются предложенные параллельные методы.
Для решения уравнения Ау = / с разреженной матрицей А можно использовать прямые или итерационные методы [8,37,45,50,58,70,134,149]. В случае больших размеров разностной сетки прямые методы становятся очень трудоемкими и требуют много памяти. Кроме того итерационные методы значительно проще поддаются распараллеливанию. Сад (Saad Y.) и ван дер BopcT(van der Vorst H.A.) в работе [130] прогнозируют, что в дальнейшем будут более интенсивно развиваться и использоваться итерационные методы, а также методы, сочетающие технику прямых и итерационных методов.
Среди итерационных методов наиболее экономичными и часто используемыми в настоящее время являются прсдобусловленныс методы проекций на подпространства Крылова [134,149], в случае симметричной положительно определенной матрицы А - предобусловлснные методы сопряженных градиентов [37,45,56,58,76,134]. В качестве прсдобусловливателя более перспективным с точки зрения скорости сходимости является использование факторизованной матрицы. Использование диагонального прсдобусловливателя хотя и не представляет проблем при распараллеливании, однако приводит к необходимости выполнения значительно большего числа итераций для сходимости метода. Наиболее часто используемыми в настоящее время являются метод с продобусловливанисм неполного разложения Холецкого без заполнения (ICCG(O)), предложенный Мсйсринком (Mcijcriuk J.A.) и ван дер Ворстом (vau der
^ 0 Ou
Ау = /, А = АТ > 0,
6
Vorst H.Л.) в работе [11С], его модифицированный вариант (MICCG(O)), предложенный Густафсоном (Gustafssou I.) [03] и Дюпоном (Dupont Т.), Кендаллом (Kendall R.), Рсшфордом (Rachford H.H.) [83], метод приближенной факторизации (MAFCG), предложенный Кучсровым А.Б. и Макаровым М.М. [24], обобщенный метод симметричной верхней релаксации SSORCG [57], метод неполного разложения Холецко-го с релаксацией (метод RICCG)[60,G1] и его различные модификации [65,110,124], попеременно-треугольный метод (ПТМСГ), предложенный A.A. Самарским [41, 42, 45]. Доказано, что для достаточно гладких коэффициентов дифференциального уравнения в случае равномерной ортогональной сетки и пятиточечного шаблона (для двумерных задач) методы MICCG(O), MAFCG, SSORCG, RICCG, ПТМСГ требуют для сходимости 0(1п(2/е)\/Ж) итераций. Метод ICCG(O) требует для сходимости примерно 0(\n(2/e)Nh) итераций. Здесь и далее - число узлов сетки по одному пространствен ному направлению, е - требуемая относительная точность.
Во всех перечисленных выше методах матрица предобусловливания имеет вид В = LDLTy где L - нижнетреугольная матрица, D - диагональная матрица. Обращение матрицы предобусловливания происходит в два этапа: Lwk = Аук — /, DLTи>к — ъ)к, где к - номер итерации в прсдобусловленном методе сопряженных градиентов, ук - приближенное решение уравнения Ay — f на А:-той итерации.
Для распараллеливания алгоритмов решения многомерных задач с целью расчета на многопроцессорных ЭВМ с распределенной памятью часто используют подход, называемый декомпозицией области или геометрическим параллелизмом [37,51,78]. При этом расчетная область разбивается на подобласти с приблизительно одинаковым числом узлов сетки, и решение задачи в каждой подобласти производится на своем процессоре. Между процессорами происходит необходимый обмен информацией. Однако распараллеливание алгоритмов методов сопряженных градиентов с факторизованным прсдобусловливателсм сталкивается с рядом трудностей, связанных прежде всего с рекурсивным характером вычислений при обращении матрицы предобусловливания.
Кучеровым А.Б. и Николаевым Е.С. в 1984 году в работе [27] предложен алгоритм параллельной реализации методов с факторизованным предобусловливате-лем, который можно использовать для расчетов на одномерном массиве процессоров. Разбиение области производится в вертикальном направлении, используется стандартное упорядочение узлов ортогональной сетки. При вычислении гйк, тик процессоры подключаются к работе не одновременно. Сначала первый процессор обрабатывает некоторое количество столбцов, и осуществляется пересылка найденных значений гйк на границе подобластей в соседний процессор. Далее второй процессор обрабатывает эту группу столбцов в своей подобласти, в то время как первый процессор производит расчеты в следующей группе столбцов, расположенной рядом, и так далее. Аналогично происходит вычисление wk. Аналогичный подход для распараллеливания метода BiCGStab(l) с прсдобусловливанием ILU предложен в работе [121]. Как показали расчеты, проведенные автором диссертации на многопроцессорной станции Parsytcc СС [30], использование таких алгоритмов эффективно лишь при небольшом числе процессоров (порядка 10), но с ростом числа процессоров эффективность распараллеливания падает.
Дафф (Duff I.S.), ван дер Ворст (van der Vorst H.A.), Донгарра (Dongarra J.J.), Соренсен (Sorensen D.С.) в работах [79,82] рассматривают наиболее существенные результаты и тенденции в построении алгоритмов решения систем линейных урав-
7
нении на параллельной вычислительной технике. Сад (Saad Y.) и ван дер Ворст (van der Vorst H.A.) в работе [136] рассматривают основные результаты развития итерационных методов решения систем линейных уравнений в 20 веке. Большое внимание уделено методам проекций на подпространства Крылова с предобусловливанием и параллельному прсдобусловливанию.
Одним из первых в развитии параллельного предобусловливания было создание полиноминального предобусловливания, рассмотренного например в работах ван дер Ворста (van der Vorst H.A.), Сада (Saad Y.), Джонсона (Jonson O.G.), Поля (Paul
G.) [08,135]. При этом процедура обращения треугольных матриц заменяется умножением некоторого полинома от матрицы на вектор, что проще для параллельной реализации. Другим направлением является подход "level sheduling” или "wafefront”, предложенный в работах ван дер Ворста (van der Vorst H.A.), Андерсона (Andersson E.C.) Салтза (Saltz J.) и других авторов [55,07, 147,148], в котором осуществляется распараллеливание на обоих этапах обращения матрицы предобусловливания. Этот подход применялся при проведении расчетов на векторных компьютерах. Он основан на том, что из-за разреженности матрицы многие уравнения могут решаться одновременно. Однако эти 2 подхода имеют ограниченные возможности.
Другой подход в развитии параллельной реализации прсдобусловленных методов - это domain decomposition method, которому посвящены в частности работы Чана (Chan T.F.), Тана (Тан K.H.), Танга (Tang W.P.) [71,141,142]. Идея метода состоит в разбиении области расчета на подобласти и решении задачи в каждой подобласти с некоторыми граничными условиями. Основная проблема состоит в нахождении надлежащих граничных условий на границах между подобластями. Возможно налегание подобластей друг на друга. Было показано [70], что этот подход может привести к улучшению скорости сходимости при не очень большом числе подобластей.
В работах Акссльссона (Axelsson О.), Польмана (Polman В.), Эйххоута (Eijkliout V.) [59,62] представлены иараллсльиыс варианты блочного метода неполной факторизации. Радикати (Radicati di Brozolo G.), Роберт (Robert Y.) в работе [131] предложили параллельный прсдобусловливатель, в котором осуществляется локальная частичная факторизация блоков матрицы с налеганием и без налегания. Фактически осуществляется расщепление матрицы с налеганием блоков (или без налегания) вдоль диагонали, которое может быть рассмотрено как расщепление области. Параллельный прсдобусловливатель создан на основе предобусловливания ILU факторизации. Значительно более сложное расщепление, ориентированное на область расчета, было предложено в работе [150] для параллслизации блочных методов с факторизацией MILU,SSOR. При этом определение неизвестных на границах подобластей происходит специальным более сложным образом.
Сигср (Seager М.К.) в работе [138] предложил параллельный вариант ICCG, в предобусловливании которого не учитываются узлы сетки из других подобластей. Такой подход приводит к значительному росту числа итераций.
В работах Капорина И.E., Коньшина И.Н. [19,101] предлагается блочная версия двухстороннего неполного обратного разложения Холсцкого BIIC, причем в каждом блоке прсдобусловливатель заменяется на его аппроксимацию с применением неполного разложения Холецкого второго порядка [102]. Используется налегание подобластей. Благодаря удачному расположению собственных значений прсдобусловлснной матрицы достигается высокая скорость сходимости итераций. В приведенных результатах расчетов задач практически не наблюдается роста числа итераций с ростом числа процессоров, эффективность метода в расчетах на 2-8 процессорах SUN Enterprise 3000 н на кластере из четырех рабочих станций с процессорами Pentium
8
II была 45-85%.
Более подробно остановимся на подходах, связанных с использованием различных способов упорядочения узлов расчетной сетки для реконструирования матрицы пре-добусловливания. Дафф (Duff I.S.), Мюран (Mourant G.Л.) (81), Эйкхоут (Eijkhout V.) [85], Ортега (Ortega J.) [37] рассматривают использование красно-черного упорядочения для параллелизации метода ICCG(O) в случае решения 5-ти точечного уравнения на ортогональной сетке. Параллельную реализацию вычислении при этом можно осуществлять на большом числе процессоров, до N/2, где N -число узлов сетки. Однако, как показано в работах [81,85], число итераций при этом может возрастать в несколько раз. Использование этого упорядочения для методов MICCG, SSORCG, ПТМСГ приводит к потере асимптотического характера зависимости числа итераций от числа неизвестных, число итераций становится почти пропорционально Njt.
Одним из способов улучшения баланса между параллелизмом и скоростью сходимости является использование многоцветного упорядочения [77,133]. Концепция многоцветного упорядочения обобщена в работе [09] для задач на неструктурированных сетках. В этой работе предлагается иерархический процесс выделения больших независимых подблоков в данной матрице, что обеспечивает достаточный параллелизм метода. Такой подход приводит к значительному ускорению решения по сравнению с натуральным (’natural’) упорядочением на одном процессоре. В работе Дои (Doi S.) [77] для методов с прсдобусловливанием ILU в случае пятиточечиых уравнений предложено также блочное упорядочение РВ(тп). При этом расчетная область разбивается на квадраты из т х т узлов сетки, вычисления в каждом процессоре двумерного массива процессоров осуществляются в своей подобласти, причем одновременно. Это упорядочение является упорядочением типа Domain Decomposition ordering, то есть упорядочением узлов сетки, согласованным с разбиением на подобласти, причем с одинаковым направлением роста номеров узлов в подобластях. Однако, как показали расчеты, проведенные автором диссертации, использование этого упорядочения для метода MICCG(O) без введения специальных итерационных параметров приводит к потере асимптотического характера зависимости числа итераций от числа узлов сетки.
Другим подходом, предложенным Мюраном (Mourant G.Л.) [114], является поворот (twisting). Ван дер Ворст (Van der Vorst Н.Л.) [14G] использовал эту идею по всем пространственным направлениям при решении двумерных и трехмерных задач, что позволило решать двумерные уравнения на 4 процессорах, а трехмерные уравнения на 8 процессорах параллельными аналогами ICCG(O), MICCG(O) (без роста итераций). Такое упорядочение иногда называют упорядочением Ван дер Ворста (Van der Vorst ordering). В работе [115] используются повторяющиеся блоки из четырех для решения двумерной задачи на 8 процессорах, при этом ускорение было около G. Мюран (Mourant G.Л.) считает, что увеличение числа итераций связано с повторением блоков. Заметим, что в работах [114,115,140] фактически используются упорядочения типа Domain Decomposition ordering с разными направлениями возрастания номеров узлов в разных подобластях.
В работе Даффа (Duff I.S.), Мюрана (Mourant G.Л.) [81] численно исследуется влияние различных способов упорядочения на скорость сходимости метода ICCG(O) для двумерных задач. Рассматриваются упорядочения Катхклла-Макки (Curthill Mckee) (СМ), обратное упорядочение Катхилла-Макки (RCM), блочное СМ, упорядочение мипимальной степени, красно-черное упорядочение, попеременно-диагональное, упорядочения рассечениями (d одном пространственном направлении), спиральное упорядочение, 4-х цветное упорядочение, упорядочения Ban дер Ворста и некоторые дру-
0
гис. Заметим, что СМ упорядочение на ортогональной сетке в случае пятиточечного шаблона фактически является диагональным упорядочением. Расчеты показали, что среди всех способов упорядочения, удобных для распараллеливания, только диагональные упорядочения (diagonal ordering) и упорядочения Ван дер Bopcra (Van der Vost ordering) для 4-х процессоров, не приводят к росту числа итераций для всех рассмотренных модельных задач. Диагональное упорядочение удобно для расчетов на векторных машинах, но малоэффективно для расчетов на параллельных вычислительных системах с распределенной памятью [140]. В работе [68] изучение структуры матрицы, обратной к матрице предобусловливания неполного разложения Холсцкого, объясняет успешность использования обратного упорядочения Катхилла-Макки с точки зрения скорости сходимости итераций при решении системы уравнений Ау = /, где разреженная матрица А = Ат > 0.
В работе Ортеги (Ortega Л.М.), Стотланда (Stotland S.A.) [140] исследуется скорость сходимости и эффективность метода SSORCG при использовании красно-черного и многоцветного (”many colour”) упорядочений, упорядочения полосками (strip ordering), упорядочения Ван дер Ворста. В двумерных задачах при оптимальном значении параметра релаксации при всех рассмотренных способах упорядочения число итераций растет с ростом быстрее, чем \/Nh, н, кроме того, при использовании упорядочения полосками число итераций растет с ростом числа процессоров.
Ноте» (Notay Y.) в работах [122,123] предложил использовать способ упорядочения неизвестных типа "domain decomposition” (’’domain decomposition like ordering”), для распараллеливания метода DRIC [121]. Теоретически доказал [123], что число итераций в параллельном методе DRIC пропорционально y/NÜ. Число итераций в расчетах [122] было почти пропорционально y/Nü. В параллельном методе DR1C число итераций достаточно медленно растет с ростом числа процессоров.
В работе Маголу монд Маде (Magolu monde Made М.), ван дер Ворста (van der Vorst H.A.) [Ill] предложен параллельный вариант метода GRIC- обобщенной неполной факторизации с релаксацией для случая равномерных ортогональных сеток. Разбиение области расчета происходит в одном пространственном направлении. Определение искомых функций при обращении матрицы предобусловливания в узлах сетки вблизи границы, с которой начинается расчет происходит болсс сложным образом, чем при упорядочении , соответствующему разбиению в одном пространственном направлении полосками. Благодаря этому значительно уменьшается число итераций.
Заметим, что техника ILU факторизации была первоначально развита для М-матриц. В общем случае ILU факторизация может столкнуться с рядом трудностей. Это способствовало |>азвитию методов приближенного обращения (”approximate inverse"). Идея конструирования таких методов - найти разреженную матрицу М такую, что II AM — Е II мало в некоторой норме, где Е -единичная матрица. При таком предобусловливании обращение двух треугольных матриц заменяется на умножение на разреженную матрицу, что значительно проще распараллеливается. Среди работ в этом направлении следует отметить [73,92,107].
Одним из перспективных направлений в развитии параллельного предобусловливания является многоуровневое предобусловливание [91,125,129]. Многоуровневое прсдобусловливание приводит к очень быстрой сходимости метода, причем число итераций почти не зависит от размера сетки [129]. Для неструктурированных сеток многоуровневое прсдобусловливание рассмотрено в работах [63,74]. Однако такие методы чрезвычайно трудоемки, имеют сложный алгоритм, при большом числе уровней требуют хранения большого количества информации. Кроме того методы с многоуровневым лрсдобусловливанисм оказываются не всегда эффективно применимы.
10
Следует отмстить, что в настоящее время используются и другие эффективные методы, например методы Гаусса-Зсйдсля [134, 37], верхней рслаксации(45,87], локальной релаксации [84). Алгоритмы этих методов хорошо поддаются распараллеливанию при использовании красно-черного упорядочения [37]. Как показано в работе [143], лучшей скоростью сходимости по сравнению с методами Гаусса-Зейделя, верхней релаксации и локальной релаксации обладает а — (3 алгоритм, предложенный Б.
Н. Чстверушкиным в работе [49] и развитый далее в работе [3]. Параллельная реализация этого метода подробно рассмотрена Б.Н. Чстверушкиным и Н.Г. Чурбановой в работе [52]. В работе [143] показано, что при решении уравнения для давления в задачах многофазной фильтрации жидкости п — (3 метод в 3.5-5.5 раз быстрее метода Гауса-Зендсля, и в 2 раза быстрее метода верхней релаксации (SOR) (при использовании релаксации в a — fi алгоритАю), и имеет лучшую эффективность параллслизации при расчетах на 8-процсссорной станции Parsytcc СС. а — fi алгоритм эффективно распараллеливается на одномерный массив процессоров Parsytec СС (когда разбиение области расчета происходит в одноа! пространственном направлении). В работе [143] проведено сравнение этого метода с попеременно-треугольным методом сопряженных градиентов и его параллельным вариантом, предложенным в настоящей диссертации, при решении эллиптического уравнения на одном и на 2 х 2 процессорах. Время решения уравнения ПТМСГ и его параллельным вариантом было существенно меньше, чем при использовании а — (3 алгоритма (в 3.4 раза на 1 процессоре и в 4.1 раза на 4 процессорах при числе узлов сетки N = 181 х 181).
Для решения систса! линейных уравнений с заполненной матрицей часто используют LU разложение, разложение Холецкого, методы ортогонального приведения [37,79]. Алгоритмы решения систем линейных уравнении с теплицсвыми матрицами и матрицами близкими к тсплицсвым рассматриваются в работе Воеводина В.В. и Тыр-тышникова Е.Е. [2] Параллельные алгоритмы обращения теплицевых матриц предложены вработах [2,106]. В работах Тыртышникова Е.Е. [144,145] предложен метод преобразования алгоритмов определенного типа для решения систем линейных уравнений в параллельные (векторизованные). Однако в получаемых при otoaî алгоритмах сильно возрастает обьем вычислений и требуеАюи памяти. В работе Тыртыш-никова Е.Е. [47] предлагаются параллельные алгоритАШ решения системы линейных уравнений Az — 6, где AiaTpuua А представима в виде суммы парных произведении теплицевых нижнетреугольных и верхнетреугольных матриц, в которых не увеличивается, а иногда даже требуется меньшая арифметическая работа, чем в известных последовательных алгоритмах.
Несмотря на большое количество работ, посвященных построению параллельных итерационных методов решения систем линейных уравнений с симметричной разреженной матрицей, эта проблема по прежнему остается актуальной и требует дальнейшего изучения. Косвенным подтверждением этого является нежелание использовать в расчетах нестационарных задач неявных схем [126], что требует решения систем линейных уравнений. Существующие параллельные методы либо медленно сходятся, либо очень трудоемки, не всегда применимы, библиотеки решения задач линейной алгебры с разреженной А1атрицсй недостаточно разработаны.
Подводя итог приведенному выше обзору литературы, следует отметить, что основное внимание было уделено параллслизации Аютода сопряженных градиентов с прсдобусловливанисм 1С, RIC и его модификаций. Причем в большинстве случаев для аппроксимации использовалась равномерная ортогональная сетка. Вопрос о построении параллельных аналогов точечных методов MICCG, ПТМСГ в случае ис-
11
пользования для аппроксимации ортогональной равномерной и неравномерной сетки для произвольного числа процессоров оставался открытым. Недостаточно изучен вопрос о параллелизации точечных методов ICCG, MICCG или их вариантов при аппроксимации уравнений на неструктурированной треугольной сетке, равномерной треугольной сетке, локально измельчающейся сетке на основе прямоугольных элементов. Существующие подходы являются сложными, трудоемкими, не всегда применимыми.
Целью настоящей работы является создание эффективных параллельных аналогов итерационных методов сопряженных градиентов с факторизованной матрицей прсдобусловливання для решения систем уравнений Лу — f с симметричной положительно определенной сильно разреженной плохо обусловленной матрицей А на параллельных вычислительных системах с распределенной памятью, имеющих достаточно высокую скорость сходимости и не слишком сложный алгоритм реализации.
В частности стояла задача построения параллельных вариантов точечных методом MICCG(O) (93], ПТМСГ [41,25,20] для решения дискретных двумерных и трехмерных уравнений на ортогональных равномерных и неравномерных сетках в области расчета, являющейся прямоугольником или прямоугольным параллелипипедом. При этом предполагается, что область расчета не является очень сильно вытянутой в одном пространственном направлении. Для решения эллиптических уравнений в двумерных сильно вытянутых подобластях следует использовать метод MAFS [109] , который требует для сходимости в этом случае значительно меньше итераций. Предполагалось также создание параллельных аналогов методов типа ICCG, MICCG в случае использования для аппроксимации дифференциальных уравнений треугольных равномерных сеток и неструктурированных сеток. При построении параллельных аналогоп всех этих методов основной задачей было сохранение характера асимптотической зависимости числа итераций от числа узлов сетки в случае равномерной ортогональной и равномерной треугольной соток. Важность создания именно таких параллельных аналогов связана с тем, что на параллельных вычислительных системах осуществляются расчеты задач с очень большим числом узлов сетки, и потеря характера асимптотической зависимости приведет к колосальному числу итераций в параллельных расчетах.
Второе требование к построенным параллельным методам состояло в том, чтобы рост числа итераций с ростом числа процессоров был бы невелик по сравнению с однопроцессорными методами, чтобы эти параллельные методы были эффективны.
Исследование эффективности предложенных методов осуществлялось с помощью расчетов модельных задач на 32-х процессорной параллельной станции Parsytec СС и на многопроцессорной вычислительной системе МВС-1000М, содержащей 708 процессоров. 32-х процессорная станция Parsytec СС, имела производительность 200 MFLOPS, тактовую частоту каждого процессора 100 Мгц, скорость обмена данными 000 Мбит/с., объем оперативной памяти на процессор 250 Мб. Использовалась библиотека организации обменов PARIX. Вычислительная система МВС-1000М, имеет пиковую производительность 1 TFLOPS, тактовую частоту каждого процессора 007 Мгц, пропускную способность канала 2000 Мбит/сек, объем оперативной памяти на процессор 1 Гб. Использовалась библиотека организации обменов MPI. Программы были написаны на языке Dec Visual Fortran.
Целью диссертации была также аппробация предложенных методов в расчетах некоторых задач гидродинамики.
12
Научная новизна работы состоит в том, что благодаря использовании стратегии упорядочения узлов сетки созданы параллельные аналоги метода сопряженных градиентов с предобусловливанием МІС, ПТМ (точечные методы), для решения двумерных и трехмерных краевых задач для эллиптических уравнении на ортогональной равномерной и неравномерной сетках для произвольного числа процессоров; сконструированы параллельные аналоги вариантов ІССв, МІССв (назовем их УІССв, УМІССв) [37, добавление Капорина Н.Е., 105,112], в которых матрица предобуслов-ливания имеет вид В ~ (б)-1 + А~)0(В~1 4- (Л”)т), где Л~ - строго нижнетреугольная часть матрицы А ( элементы диагональной матрицы И определяются из тех же условий, что в методах ЮСЭ, МІССС), для решения двумерных краевых задач для эллиптических уравнений на треугольных равномерных и неструктурированных сетках в произвольной односвязной области расчета и на локально измельчающихся сетках на основе прямоугольных элементов. Заметим, что такой выбор матрицы В продиктован необходимостью теоретического выбора оптимальных итерационных параметров, обеспечивает более простой алгоритм распараллеливания, возможность применения приема Айзснштата [37] с целью удешевить каждую итерацию. В настоящей работе прием Айзснштата не применялся.
Для достаточно гладких коэффициентов в дифференциальном уравнении в предложенных параллельных вариантах методов МІССС(О), МАРСЭ, ПТМСГ теоретически исследованы характер асимптотической зависимости числа итераций от числа узлов сетки и скорость роста числа итераций с ростом числа процессоров. Получены теоретические оценки числа итераций параллельных вариантов методов М1ССС(0), ПТМСГ, УМІССв для модельных задач на ортогональной равномерной сетке или на равномерной треугольной сетке.
В созданных параллельных методах сохраняется характер асимптотической зависимости числа итераций от числа узлов сетки для равномерной ортогональной и равномерной треугольной сеток такой же , как в соответствующих однопроцессорных методах. При этом происходит приемлемый рост числа итераций с ростом числа процессоров по крайней мере для их умеренного количества, то есть число итераций в параллельных вариантах методов возрастает менее, чем в 2 раза по сравнению с однопроцессорными методами. В параллельных аналогах методов ПТМСГ, МІССС, УМЮСв - варианта МІССЄ это достигается благодаря теоретическому выбору параметров, оптимизирующему теоретические оценки числа итераций параллельных методов, полученные в настоящей диссертации.
Предложен способ автоматического выбора параметров в МЮСС(О) и параллельных вариантах МЮСС(О), который обеспечивает приемлемый рост числа итераций с ростом числа процессоров в случае использования для аппроксимации дифференциальных уравнении сильно неравномерной сетки, автоматический учет разрывов коэффициентов, существенно уменьшает рост числа итераций с ростом числа процессоров при решении анизотропных задач и позволяет в ряде случаев решать такие задачи на многопроцессорной ЭВМ с хорошей эффективностью.
Указаны способы выбора итерационных параметров для метода УМЮСЭ и его параллельных аналогов в случае использования для аппроксимации дифференциальных уравнений неструктурированных треугольных сеток и локально измельчающихся сеток на основе прямоугольных элементов. Эти итерационные параметры обеспечивают приемлемый рост числа итераций с ростом числа процессоров. Такой выбор параметров в случае неструктурированной треугольной сетки позволяет существенно сократить число итераций в расчетах модельных задач на одном процессоре по срависпию с нулевыми параметрами.
13
В диссертации указываются наиболее подходящие способы разбиения области расчета с точки зрения скорости сходимости итерационного процесса в предложенных параллельных методах.
Построенные в диссертации методы имеют хорошую эффективность для достаточно большого числа точек и умеренного числа процессоров.
В диссертации предложен алгоритм решения как стационарных, так и нестационарных двумерных и трехмерных задач гидродинамики в естественных переменных "скорость-давление” на параллельных вычислительных системах. При этом для моделирования течений несжимаемой жидкости используется система квазигидродина-мических уравнений [53,5-1], а для решения эллиптического уравнения для давления -параллельные варианты метода MICCG(O), предложенные в настоящей диссертации.
Практическая значимость диссертационной работы состоит прежде всего в том, что созданы и аппробированы в расчетах эффективные параллельные методы решения систем уравнений Ау = /, где А = Ат > 0, сильно разреженная плохо обусловленная матрица, имеющие достаточно простой алгоритм. Эти методы могут быть использованы для численного решения задач математической физики на подробных пространственных сетках, в математической модели которых имеются эллиптические уравнения. Кроме того эти методы могут использоваться для решения краевых задач для параболических уравнении, если для аппроксимации последних используются неявные схемы.
Некоторые из предложенных методов включаются в создаваемую в настоящее время параллельную библиотеку программ для решения систем линейных уравнений с разреженной матрицей и создаваемый пакет GIMM- пакет решения задач механики сплошной среды.
Приведенные в главе 4 результаты расчета течений в кубической каверне могут использоваться для тестирования численных алгоритмов расчета трехмерных течений. Результаты численного решения задачи термокапиллярной конвекции в условиях пониженной гравитации помогли выяснить причину неравномерного роста кристаллов в экспериментах, проводимых на искусственных спутниках Земли.
СТРУКТУРА ДИССЕРТАЦИИ.
Диссертация состоит из *1 глав, введения, заключения, списка литературы и приложений. Список литературы содержит 150 работ. Объем диссертации 210 страниц.
Первая глава диссертации посвящена построению параллельных вариатов методов MICCG(O), MAFCG, ICCG(O) для решения двумерных краевых задач для эллиптических уравнений в прямоугольной области расчета. При этом предполагается, что область расчета не является очень сильно вытянутой в одном пространственном направлении.
Разностная аппроксимация дифференциальных уравнений осуществляется на равномерной и неравномерной ортогональной разностной сетке и на локально измельчающейся сетке на основе прямоугольных элементов. При аппроксимации эллиптического уравнения на ортогональной равномерной и неравномерной сетках используется пятиточечный шаблон. Разбиение области расчета происходит в двух пространственных направлениях. Для построения параллельных вариантов методов используются упорядочения Domain Decomposition ordering 1 (DD01) и Domain Decomposition ordering 2 (DD02). В упорядочении DDOl во всех подобластях организуется одинаковый порядок следования узлов сетки, при использовании DD02 существуют 4 типа подобластей с различными упорядочениями узлов сетки внутри них.
Рассматривается метод PICCG - параллельный вариант метода ICCG(O) с DD01 упорядочением узлов сетки для решения дискретных аналогов двумерных эллипти-
14
ческих уравнений. Предлагаются методы PMICCGl, PMICCG2 - параллельные варианты метода MICCG(O) с упорядочениями DD01 и DD02 для решения дискретных эллиптических уравнении на равномерной сетке, а также параллельный вариант метода MAFCG с DD01 упорядочением.
Проводится теоретическое исследование скорости сходимости методов PMICCGl, PMICCG2, параллельного варианта MAFCG в случае ортогональной равномерной сетки и задачи Дирихле. Получены теоретические оценки числа итераций методов PMICCGl, PMICCG2 для модельной задачи. Указываются итерационные параметры, позволяющие сохранить в методах PMICCGl, PMICCG2 характер асимптотической зависимости числа итераций от числа узлов сетки такой же, как в методе MICCG(O), и обеспечивающие приемлемый рост числа итераций с ростом числа процессоров.
Проводится экспериментальное исследование скорости сходимости и эффективности всех рассмотренных параллельных методов с помощью расчетов модельных задач на параллельной станции Parsytec СС.
Исследуется влияние формы подобластей при разбиении прямоугольной области расчета на скорость сходимости предложенных параллельных методов с помощью решения модельных задач. С помощью расчетов модельных задач исследуется влияние анизотропии коэффициентов дифференциального уравнения на скорость сходимости предложенных параллельных аналогов ICCG(O), MAFCG.
Предлагаются способы автоматического выбора итерационных параметров для методов PMICCGl, PMICCG2, которые позволяют использовать эти методы для решения дискретных аналогов двумерных эллиптических уравнений на сильно неравномерной ортогональной сетке и обеспечивают приемлемый рост числа итераций с ростом числа процессоров. Эти способы выбора параметров позволяют «автоматически отслеживать точки разрыва коэффициентов дифференциального уравнения. Приводятся расчеты, демонстрирующие, что использование автоматического выбора пар.амстров позволяет существенно уменьшить число итераций при решении анизотропных задач, а в ряде случаев даже эффективно решать «анизотропные задачи на многопроцессорной вычислительной системе.
В последнем параграфе главы 1 для решения дискретных эллиптических уравнении на локально измельч.ающсйся сетке предлагается использовать методы VICCG, VMICCG - варианты методов ICCG(O), MAFCG (который является методом MICCG(O) без возмущения, то есть с нулевыми параметрами) [37, добавление], [105,112]. Созданы методы PVICCG, PVMICCG- п«ар«аллсльныс аналоги методов VICCG, VMICCG, в которых используется DD01 упорядочение узлов сетки. В методе PVMICCG используются итерационные п«араметры, полученные для случая р.авномерной ортогональной сетки с некоторым осреднснным шагом. Проводится исследование скорости сходимости и эффективности методов с помощью расчетов модельной задачи.
Вторая глава диссертации посвящспа решению краевых задач для двумерных эллиптических уравнений в произвольной односвязной области расчета параллель-ными вариантами метода сопряженных градиентов с факторизованной матрицей пре-добусловлив.анпя. Построение п«ар«аллсльных методов и исследование скорости их сходимости проводится на примере задачи Дирихле. Для «аппроксимации дифференциальных уравнений используется р«авномерная треугольная пли неструктурированная треугольная сетки. В качестве первоначального упорядочения узлов сетки при расчетах на одном процессоре используется Катхилла- Макки упорядочение. Предложены методы PVICCG, PVMICCG - параллельные аналоги методов VICCG, VMICCG - вариантов ICCG, MICCG [37, добавление Капорииа И.Б.], [105,112]. При постро-
15
снии параллельных вариантов VMICCG в случае равномерной треугольной сетки рассматриваются различные способы упорядочения узлов сетки, в частности DD01, DD02, DD03. При использовании DD03 упорядочения существуют 2 типа подобластей, в которых используются одинаковые упорядочения узлов сетки. В параллельном варианте VICCG используется DD01 упорядочение. В случае неструктурированной треугольной сетки используется DD01 упорядочение.
В случае равномерной треугольной сетки производится теоретическое исследование скорости сходимости методов PVMICCG (с DD01 упорядочением) и VMICCG на примере модельной задачи, указан способ выбора итерационных параметров, которые практически обеспечивают сохранение в параллельных методах характера асимптотической зависимости числа итераций от числа узлов сетки, такого же, как в методе
VMICCG, то есть 0(ln(2/c)v/7'7).
В случае неструктурированной треугольной сетки для метода PVMICCG предлагается способ выбора итерационных параметров, который является обобщением способа выбора итерационных параметров для случая равномерных треугольных сеток. Рассматриваются различные способы разбиения области расчета на подобласти и производится их сравнение с точки зрения скорости сходимости итераций. Рассматриваются параллельные варианты методов VICCG, VMICCG, в которых используется обратное Катхилла-Макки упорядочение узлов сетки. В этих параллельных вариантах используется один из способов разбиений области расчета на подобласти.
С помощью расчетов модельных задач проводится исследование скорости сходимости методов PVICCG, PVMICCG как для случая равномерной треугольной сетки, так и для случая неструктурированной треугольной сетки. С помощью расчетов на умеренном числе процессоров параллельной вычислительной системы МВС 1000М проводится исследование эффективности методов PVICCG, PVMICCG для случая равномерной треугольной сетки. Заметим, что расчеты задач, в которых использовались равномерная треугольная и неструктурированная треугольная сетки, происходили почти по одной и той же программе. Эта программа работала для всех рассмотренных способов разбиения области расчета, а также для обращения матриц, присланных из РФЯЦ-ВШШЭФ (г. Саров).
В последнем параграфе главы 2 предложены методы PVMICCG с автоматическим выбором параметров для решения дискретных эллиптических уравнений с сильно отличающимися коэффициентами на неструктурированной треугольной сетке, указан способ автоматического выбора итерационных параметров. Для модельной задачи, в которой используется равномерная треугольная сетка, с помощью расчетов на умеренном числе процессоров произведено исследование скорости сходимости методов PVMICCG с упорядочениями DD01 и DD02 и автоматическим выбором параметров. Показано, что число итераций существенно уменьшается при использовании автоматического выбора параметров.
Третья глава диссертации посвящена построению параллельных вариантов ПТМ-СГ для решения двумерных и трехмерных краевых задач для эллиптических уравнений на ортогональной равномерной и неравномерной сетках. Областью расчета является прямоугольник или прямоугольный параллелипипед.
Предлагаются методы ППТМСГ1, ППТМСГ2 - параллельные варианты метода ПТМСГ для решения краевых задач для двумерных эллиптических уравнений. При этом используются соответственно DD01 и DD02 упорядочения узлов сетки тс же, что в главе 1. Проводится теоретическое и экспериментальное исследование скорости сходимости этих методов в случае решения задачи Дирихле для эллиптических уравнений на равномериой сетке. Доказывается и подтверждается расчетами, что
1G
в методах ППТМСГ1, ППТМСГ2 такой же характер асимптотической зависимости числа итераций от числа узлов сетки, как в методе ПТМСГ (для одного процессора), рост числа итераций с ростом числа процессоров допустимый, причем более медленный в методе ППТЛ1СГ2. Проводится сравнение ППТМСГ1 и ППТМСГ2 на примере решения модельных задач. Демонстрируется хорошая эффективность методов ППТМСГ1 и ППТМСГ2 при решении модельной задачи на умеренном числе процессоров.
Предлагаются методы ППТМСГЗ и ППТМСГ4 - параллельные варианты ПТМСГ для решения трехмерных разностных эллиптических уравнений, при построении которых область расчета разбивается соответственно в двух и трех пространственных направлениях. Проводится исследование скорости сходимости предложенных параллельных методов. Показывается, что число итераций растет с ростом числа процессоров очень медленно, в случае постоянных шагов сетки сохраняется характер асимптотической зависимости числа итераций от числа неизвестных при любом фиксированном массиве процессоров. Исследуется влияние формы подобластей на скорость сходимости и время счета методов ППТМСГ2, ППТМСГЗ. Проводится сравнение методов ППТМСГЗ и ППТМСГ4 на примере решения модельных задач. Заметим, что алгоритм метода ППТМСГ4 значительно сложнее, чем алгоритм ППТМСГЗ , и требует больше инициализаций обменов.
Получены теоретические оценки числа итераций в методах ППТМСГ2, ППТМСГЗ, ППТМСГ4 для модельных задач.
Приводятся приближенные формулы для времени счета итеращшонного процесса в методах ППТМСГЗ и ППТМСГ4. В этих формулах учитываются времена выполнения арифметических операций и пересылок. Исходя из этих формул произведен анализ условий целесообразности применения метода ППТМСГЗ или ППТМСГ4.
В четвертой главе диссертации предложен параллельный вариант метода МЮСС(О) для решения трехмерных эллиптических уравнений на равномерной ортогональной сетке, для модельной задачи проведено теоретическое исследование скорости сходимости метода и указаны теоретически оптимальные итерационные параметры, минимизирующие полученную оценку числа итераций. При использовании этих итерационных параметров в параллельном варианте М1ССС(0) сохраняется такой же характер асимптотической зависимости числа итераций от числа узлов сетки, как в методе М1ССС(0). Проведено численное исследование скорости сходимости параллельного метода для модельных задач с граничными условиями Дирихле и Неймана.
Во втором параграфе главы 4 построен алгоритм решения как стационарных, так и нестационарных задач гидродинамики в естественных переменных ’’скорость-давление” на многопроцессорных вычислительных системах на примере трехмерных задач. Для моделирования течений используется система квазигидродинамических (КГД) уравнений [53,54], записанная в эйлеровой системе коордииат, а для решения второй краевой задачи для уравнения Пуассона для давления - параллельный вариант метода М1ССС(0), предложенный в §1 главы 4 в настоящей диссертации. Осуществляется численное моделирование пространственных течений в каверне с подвижной верхней крышкой. Исследуется сходимость численного решения по сетке. Приведены результаты расчетов течений жидкости для чисел Рейнольдса Не = 100,1000,2000. Полученные численные результаты сопоставляются с имеющимися в литературе данными.
В третьем параграфе главы 4 с помощью вычислительного алгоритма, построенного па основе квазнгндродинлмичсскои системы уравнений [53,51], проводится численное исследование задачи о термокапиллярной конвекции в прямоугольной полости
17
с учетом микрогравитации. Для решения задачи используются методы MICCG(O), PMICCG1 с итерационными параметрами, полученными теоретически для модельной задачи в главе 1.
Изучается влияние совместного действии термокапиллярных сил и постоянного ускорения силы тяжести, ортогонального свободной поверхности на структуру термокапиллярной конвекции и влияние квазистатичсской составляющей микроускорения на конвективное движение жидкости. Квазистатическая составляющая микроускорения обусловлена движением спутника относительно центра масс как твердого тела, градиентом гравитационного поля Земли и сопротивлением атмосферы.
НА ЗАЩИТУ ВЫНОСЯТСЯ
1.Параллельные варианты методов MICCG(O) с упорядочениями DD01 и DD02 и MAFCG с упорядочением DD01 для решения краевых задач для двумерных эллиптических уравнений на ортогональной равномерной сетке в прямоугольной области расчета, параллельный вариант MICCG(O) для решения трехмерных эллиптических уравнения на равномерной ортогональной сетке в прямоугольном параллслипипеде;
благодаря выбору итерационных параметров с помощью теоретического исследования скорости сходимости параллельных методов и получения оптимальных оценок числа итераций для модельной задачи во всех предложенных методах сохраняется характер асимптотической зависимости числа итераций от числа узлов сетки при фиксированном массиве процессоров такой же, как в их однопроцессорных вариантах, а также происходит приемлемый рост числа итерации с ростом числа процессоров; с помощью расчетов показано, что оптимальной формой подобласти при разбиении прямоугольной области является квадрат.
2. Пар аллельные варианты метода MICCG(O) с упорядочениями DD01 и DD02 для решения краевых задач для двумерных эллиптических уравнений на ортогональной неравномерной сетке с автоматическим выбором параметров;
автоматический выбор параметров обеспечивает допустимый рост числа итераций с ростом числа процессоров при использовании сильно неравномерной сетки, автоматический учет разрывов коэффициентов, в ряде случаев возможность эффективного решения анизотропных задач.
3. Пар аллельные варианты методов VICCG и VMICCG для решения двумерных эллиптических уравнений на равномерных треугольных сетках с различными способами упорядочения узлов сетки типа Domain Decomposition ordering (для параллельных вариантов VMICCG), а также для решения двумерных эллиптических уравнений на неструктурированных треугольных сетках и локально измельчающихся сетках па основе прямоугольных элементов;
с помощью теоретического исследования скорости сходимости итераций и получения оптимальной оценки числа итераций для модельной задачи указан способ выбора итерационных параметров в методе PVMICCG (параллельном аналоге VMICCG) в случае равномерных треугольных сеток, при котором практически сохраняется характер асимптотической зависимости числа итераций от числа узлов сетки в PVMICCG такой же, как VMICCG (при фиксированном массиве процессоров), а также происходит приемлемый рост числа итераций с ростом числа процессоров; указаны способы выбора итерационных параметров в методе PVMICCG в случае неструктурированных треугольных сеток и локально измельчающихся сеток, благодаря которому в расчетах наблюдается допустимый рост числа итераций с ростом числа процессоров; при расчетах методом PVICCG (параллельным аналогом VICCG) рост числа итераций с ростом числа процессоров медленный.
•1.Параллельные варианты метода ПТМСГ с различными способами упорядочения
18
узлов сетки типа Domain Decomposition ordering для решения двумерных и трехмерных краевых задач для эллиптических уравнений на ортогональной равномерной и неравномерной сетках в прямоугольнике или в прямоугольном параллелипипеде; для трехмерных задач используются разбиения области расчета в двух и трех пространственных направлениях;
проведенное теоретическое и численное исследование скорости сходимости параллельных вариантов ПТМСГ в случае равномерной сетки показывает сохранение характера асимптотической зависимости числа итераций от числа узлов сетки во всех предложенных параллельных вариантах такого же, как в ПТМСГ (при фиксированном массиве процессоров), а также допустимый рост числа итераций (для двумерных задач) и медленный рост числа итераций (для трехмерных задач) с ростом числа процессоров; получены теоретические оценки числа итераций параллельных вариантов ПТМСГ для модельных задач.
5.Алгоритм решения задач гидродинамики на многопроцессрных вычислительных системах, в котором используются КГД уравнения и параллельный варианты MICCG(O); результаты применение этого алгоритма для численного моделирования течения вязкой несжимаемой жидкости в кубической каверне с подвижной верхней крышкой при Rc = 100,1000,2000; результаты математического моделирования тер-мокгшиллярной конвекции в прямоугольной полости в условиях пониженной гравитации;
продемонстрирована зависимость тепломассообмена от колебаний вектора остаточного ускорения, эта зависимость может вызывать неравномерный рост кристаллов даже в режиме ламинарного конвективного движения.
АППРОБАЦИЯ РАБОТЫ. Результаты диссертации докладывались и обсуждались на
-VI Всероссийской конференции РТА ’’Транспьютерные системы и их применение” (г. Домодедово, октябрь 199Gr.)
-международной конференции Euro-Par’98:”Parallel Processing” (Великобритания, г. Саутгемптон, сентябрь 1998 г.)
-2 международной конференции ’’Modern Trends in Computational Physics" (г. Дубна, июль 2001г.)
-8 Всероссйском съезде по теоретической и прикладной механике (г.Пермь, август 2001г.)
-15 международной конференции "Parallel Computational Fluid Dynamics” (г. Москва, май 2003г.) (2 доклада)
-научном семинаре математического отделения РФЯЦ-ВНИИЭФ (г. Саров, февраль 2003г.)
-научном семинаре под руководством члена-корреспондента РАН Б.Н. Четверуш-кина в Институте математического моделирования РАН (г. Москва, февраль 2004г.)
-научном семинаре под руководством профессора Е.Е. Тыртышникова в Институте вычислительной математики РАН (г. Москва, апрель 2004г.)
-научном семинаре им. К.И. Бабенко под руководством члена-корреспондента РАН A.B. Забродина в Институте прикладной математики им. М.В. Келдыша РАН (г. Москва, апрель 2004г.)
Результаты, полученные автором нашли отражение в учебном курсе лекций члена корреспондента РАН Б.Н. Четвсрушкина "Параллельные вычисления” для студентов ВМиК МГУ и МФТИ (ГУ), а также в курсе лекций ”Математическое моделирование” для студентов МГТУ СТАНКИН.
19