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

В последние десятилетия наблюдается бурное развитие вычислительной техники, создание высокопроизводительных вычислительных комплексов и систем, содержащих несколько сотен или даже тысяч процессоров с большим объемом оперативной памяти, высокой производительностью и большой скоростью обмена данными между процессорами. Так например создан Межведомственный Супер компьютерный Центр МВС 1000 М [48], содержащий 768 процессоров ALpha 21 264 с объемом оперативной на процессор 1 Гб, при этом общий объем оперативной памяти решающего поля 768 Гб. Такой объем оперативной памяти позволяет производить вычисления с большими массивами данных, что в свою очередь позволяет использовать подробные сетки для аппроксимации уравнений и благодаря этому повысить точность расчетов физических задач. Кроме того появилась возможность генерации неструктурированных треугольных сеток большого объема и расчета на них сложных прикладных задач в областях с произвольной геометрией. Высокая производительность процессоров и скорость обмена данными позволяют за разумное время решать сложные нестационарные задачи. Однако при использовании современных многопроцессорных ЭВМ возникает вопрос адаптации к ним существующих однопроцессорных методов и алгоритмов или создания новых.

Адаптация алгоритмов решения нестационарных задач с использованием явных схем [42] для аппроксимации дифференциальных уравнений в настоящее время успешно решена [5,9,13,51]. Однако численное решение уравнений с использованием явных схем, особенно уравнений параболического типа, накладывает жесткие ограничения на шаг по времени [42], тем самым увеличивая время расчета задачи. Использование неявных схем связано с необходимостью решения систем линейных уравнений с сильно разреженной и как правило плохо обусловленной матрицей, что даже в случае использования однопроцессорных ЭВМ является весьма трудоемким [42,45,58,134]. Особенно сложным является решение таких систем в случае аппроксимации дифференциальных уравнений на неструктурированные сетки.

К необходимости решения систем линейных уравнений мы приходим также при решении дискретных аналогов двумерных и трехмерных краевых задач для эллиптических уравнений второго порядка. Следует отметить, что при численном решении многих нестационарных задач математической физики основная часть вычислительных затрат приходится именно на решение краевых задач для двумерных или трехмерных эллиптических уравнений. К таким задачам относятся задачи радиационной газовой динамики, гидродинамики, некоторые задачи микроэлектроники, задачи диффузии, нефтедобычи и другие.

Проблема адаптации методов решения систем линейных уравнений с разреженной матрицей является очень сложной. В настоящее время решение этой проблемы находится на начальной стадии. Существующие параллельные методы решения систем линейных уравнений, возникающих в результате аппроксимации дифференциальных уравнений, либо имеют относительно невысокую скорость сходимости (особенно при большом числе неизвестных), либо очень сложны для реализации, либо имеют ограниченную область применимости.

В настоящее время не существует достаточно хорошо разработанных библиотек для решения систем линейных уравнений с разреженной матрицей, которые можно было бы использовать для расчетов на произвольной параллельной вычислительной системе [80]. Все они находятся в стадии разработки. Для решения систем линейных уравнений с заполненой матрицей наиболее известны пакет ScaLAPACK [137], включающий в основном прямые методы, NAG Parallel Library [108]. Среди библиотек решения систем линейных уравнений с разреженной матрицей следует отметить Aztec (параллельная библиотека итерационных методов), BlockSolve 95, DOUG (Domain decomposition on Unstructured Grids), P-Sparslib, информация о которых находится в интернете (http://www.parallel.ru/tech/tech dev/par libs. html). Вообще говоря, параллельных численных библиотек немного, доступ к ним бывает затруднен по коммерческим соображениям.

Поэтому решение нестационарных задач математической физики на многопроцессорных ЭВМ осуществляется как правило с использованием явных схем [126].

В настоящей диссертации мы остановимся на численном решении краевых задач для эллиптического уравнения вида 0 ди.

Ъ 7ьГХа7ьГ = при xeG' где Ха > с > 0, а = 1, ., m — непрерывные или кусочно непрерывные функции, га — размерность пространства, х — для двумерных по пространству задач и х = (х1,Х2,хз) для трехмерных задач. Область Gпрямоугольная, или двумерная односвязная, или прямоугольный параллелипипед. В результате аппроксимации краевой задачи получим систему линейных алгебраических уравнений вида.

Ау = /, А = Ат > 0, с сильно разреженной симметричной положительно определенной матрицей А. Вид матрицы, А зависит от разностной сетки, введенной в области G, и способа построения дискретного аналога дифференциального уравнения. Заметим, что матрица, А является как правило плохо обусловленной.

Приведенное выше эллиптичекое уравнение можно рассматривать в качестве некоторой модели, на численном решении которой аппробируются предложенные параллельные методы.

Для решения уравнения Ау = / с разреженной матрицей, А можно использовать прямые или итерационные методы [8,37,45,56,58,76,134,149]. В случае больших размеров разностной сетки прямые методы становятся очень трудоемкими и требуют много памяти. Кроме того итерационные методы значительно проще поддаются распараллеливанию. Сад (Saad Y.) и ван дер Ворст (гап der Vorst Н.А.) в работе [136] прогнозируют, что в дальнейшем будут более интенсивно развиваться и использоваться итерационные методы, а также методы, сочетающие технику прямых и итерационных методов.

Среди итерационных методов наиболее экономичными и часто используемыми в настоящее время являются предобусловленные методы проекций на подпространства Крылова [134,149], в случае симметричной положительно определенной матрицы, А — предобусловленные методы сопряженных градиентов [37,45,56,58,76,134]. В качестве предобусловливателя более перспективным с точки зрения скорости сходимости является использование факторизованной матрицы. Использование диагонального предобусловливателя хотя и не представляет проблем при распараллеливании, однако приводит к необходимости выполнения значительно большего числа итераций для сходимости метода. Наиболее часто используемыми в настоящее время являются метод с предобусловливанием неполного разложения Холецкого без заполнения (ICCG (O)), предложенный Мейеринком (Meijerink J.А.) и ван дер Ворстом (van der.

Vorst H.A.) в работе [116], его модифицированный вариант (MICCG (O)), предложенный Густафсоном (Gustafsson I.) [93] и Дюпоном (Dupont Т.), Кендаллом (Kendall R.), Решфордом (Rachford Н.Н.) [83], метод приближенной факторизации (MAFCG), предложенный Кучеровым А. Б. и Макаровым М. М. [24], обобщенный метод симметричной верхней релаксации SSORCG [57], метод неполного разложения Холецко-го с релаксацией (метод RICCG)[60,61] и его различные модификации [65,110,124], попеременно-треугольный метод (ПТМСГ), предложенный А. А. Самарским [41, 42, 45]. Доказано, что для достаточно гладких коэффициентов дифференциального уравнения в случае равномерной ортогональной сетки и пятиточечного шаблона (для двумерных задач) методы MICCG (O), MAFCG, SSORCG, RICCG, ПТМСГ требуют для сходимости 0(ln (2/e)/iVft) итераций. Метод ICCG (O) требует для сходимости примерно 0(ln (2/e)iV/j) итераций. Здесь и далее Nh — число узлов сетки по одному пространственному направлению, е — требуемая относительная точность.

Во всех перечисленных выше методах матрица предобусловливания имеет вид В — LDLT, где L — нижнетреугольная матрица, D — диагональная матрица. Обращение матрицы предобусловливания происходит в два этапа: Lwk = Аук — /, DLTwk = wk, где к — номер итерации в предобусловленном методе сопряженных градиентов, ук — приближенное решение уравнения Ay — / на А'-той итерации.

Для распараллеливания алгоритмов решения многомерных задач с целью расчета на многопроцессорных ЭВМ с распределенной памятью часто используют подход, называемый декомпозицией области или геометрическим параллелизмом [37,51,78]. При этом расчетная область разбивается на подобласти с приблизительно одинаковым числом узлов сетки, и решение задачи в каждой подобласти производится на своем процессоре. Между процессорами происходит необходимый обмен информацией. Однако распараллеливание алгоритмов методов сопряженных градиентов с факторизованным предобусловливателем сталкивается с рядом трудностей, связанных прежде всего с рекурсивным характером вычислений при обращении матрицы предобусловливания.

Кучеровым А.Б. и Николаевым Е. С. в 1984 году в работе [27] предложен алгоритм параллельной реализации методов с факторизованным предобусловливателем, который можно использовать для расчетов на одномерном массиве процессоров. Разбиение области производится в вертикальном направлении, используется стандартное упорядочение узлов ортогональной сетки. При вычислении wk, wk процессоры подключаются к работе не одновременно. Сначала первый процессор обрабатывает некоторое количество столбцов, и осуществляется пересылка найденных значений wk на границе подобластей в соседний процессор. Далее второй процессор обрабатывает эту группу столбцов в своей подобласти, в то время как первый процессор производит расчеты в следующей группе столбцов, расположенной рядом, и так далее. Аналогично происходит вычисление wk. Аналогичный подход для распараллеливания метода BiCGStab (l) с предобусловливанием ILU предложен в работе [121]. Как показали расчеты, проведенные автором диссертации на многопроцессорной станции Parsytec СС [36], использование таких алгоритмов эффективно лишь при небольшом числе процессоров (порядка 10), но с ростом числа процессоров эффективность распараллеливания падает.

Дафф (Duff I.S.), ван дер Ворст (van der Vorst Н.А.), Доигарра (Dongarra J.J.), Сорепсен (Sorensen D.C.) в работах [79,82] рассматривают наиболее существенные результаты и тенденции в построении алгоритмов решения систем линейных уравнений на параллельной вычислительной технике. Сад (Saad Y.) и ван дер Ворст (van der Vorst Н.А.) в работе [136] рассматривают основные результаты развития итерационных методов решения систем линейных уравнений в 20 веке. Большое внимание уделено методам проекций на подпространства Крылова с предобусловливанием и параллельному предобусловливанию.

Одним из первых в развитии параллельного предобусловливания было создание полиноминального предобусловливания, рассмотренного например в работах ван дер Ворста (van der Vorst Н.А.), Сада (Saad Y.), Джонсона (Jonson O.G.), Поля (Paul G.) [98,135]. При этом процедура обращения треугольных матриц заменяется умножением некоторого полинома от матрицы на вектор, что проще для параллельной реализации. Другим направлением является подход «level sheduling» или «wafefront», предложенный в работах ван дер Ворста (van der Vorst Н.А.), Андерсона (Andersson Е.С.) Салтза (Saltz J.) и других авторов [55,67, 147,148], в котором осуществляется распараллеливание на обоих этапах обращения матрицы предобусловливания. Этот подход применялся при проведении расчетов на векторных компьютерах. Он основан на том, что из-за разреженности матрицы многие уравнения могут решаться одновременно. Однако эти 2 подхода имеют ограниченные возможности.

Другой подход в развитии параллельной реализации предобусловленных методов — это domain decomposition method, которому посвящены в частности работы Чана (Chan T.F.), Тана (Tan К.Н.), Танга (Tang W.P.) [71,141,142]. Идея метода состоит в разбиении области расчета на подобласти и решении задачи в каждой подобласти с некоторыми граничными условиями. Основная проблема состоит в нахождении надлежащих граничных условий на границах между подобластями. Возможно налегание подобластей друг на друга. Было показано [70], что этот подход может привести к улучшению скорости сходимости при не очень большом числе подобластей.

В работах Аксельссона (Axelsson О.), Польмана (Polman В.), Эйкхоута (Eijkhout V.) [59,62] представлены параллельные варианты блочного метода неполной факторизации. Радикати (Radicati di Brozolo G.), Роберт (Robert Y.) в работе [131] предложили параллельный предобусловливатель, в котором осуществляется локальная частичная факторизация блоков матрицы с налеганием и без налегания. Фактически осуществляется расщепление матрицы с налеганием блоков (или без налегания) вдоль диагонали, которое может быть рассмотрено как расщепление области. Параллельный предобусловливатель создан на основе предобусловливания ILU факторизации. Значительно более сложное расщепление, ориентированное на область расчета, было предложено в работе [150] для параллелизации блочных методов с факторизацией MILU, SSOR. При этом определение неизвестных на границах подобластей происходит специальным более сложным образом.

Сигер (Seager М.К.) в работе [138] предложил параллельный вариант ICCG, в предобусловливании которого не учитываются узлы сетки из других подобластей. Такой подход приводит к значительному росту числа итераций.

В работах Капорина И. Е., Коньшина И. Н. [19,101] предлагается блочная версия двухстороннего неполного обратного разложения Холецкого ВИС, причем в каждом блоке предобусловливатель заменяется на его аппроксимацию с применением неполного разложения Холецкого второго порядка [102]. Используется налегание подобластей. Благодаря удачному расположению собственных значений предобусловленной матрицы достигается высокая скорость сходимости итераций. В приведенных результатах расчетов задач практически не наблюдается роста числа итераций с ростом числа процессоров, эффективность метода в расчетах на 2−8 процессорах SUN Enterprise 3000 и на кластере из четырех рабочих станций с процессорами Pentium.

II была 45−85%.

Более подробно остановимся на подходах, связанных с использованием различных способов упорядочения узлов расчетной сетки для реконструирования матрицы предобусловливания. Дафф (Duff I.S.), Мюран (IVIcurant G.A.) [81], Эйкхоут (Eijkhout V.) [85], Ортега (Ortega J.) [37] рассматривают использование красно-черного упорядочения для параллелизации метода ICCG (O) в случае решения 5-ти точечного уравнения на ортогональной сетке. Параллельную реализацию вычислений при этом можно осуществлять на большом числе процессоров, до N/2, где Nчисло узлов сетки. Однако, как показано в работах [81,85], число итераций при этом может возрастать в несколько раз. Использование этого упорядочения для методов MICCG, SS0RCG, ПТМСГ приводит к потере асимптотического характера зависимости числа итераций от числа неизвестных, число итераций становится почти пропорционально Nh.

Одним из способов улучшения баланса между параллелизмом и скоростью сходимости является использование многоцветного упорядочения [77,133]. Концепция многоцветного упорядочения обобщена в работе [99] для задач на неструктурированных сетках. В этой работе предлагается иерархический процесс выделения больших независимых подблоков в данной матрице, что обеспечивает достаточный параллелизм метода. Такой подход приводит к значительному ускорению решения по сравнению с натуральным ('natural') упорядочением на одном процессоре. В работе Дои (Doi S.) [77] для методов с предобусловливанием ILU в случае пятиточечных уравнений предложено также блочное упорядочение РВ (т). При этом расчетная область разбивается на квадраты из т х т узлов сетки, вычисления в каждом процессоре двумерного массива процессоров осуществляются в своей подобласти, причем одновременно. Это упорядочение является упорядочением типа Domain Decomposition ordering, то есть упорядочением узлов сетки, согласованным с разбиением на подобласти, причем с одинаковым направлением роста номеров узлов в подобластях. Однако, как показали расчеты, проведенные автором диссертации, использование этого упорядочения для метода MICCG (O) без введения специальных итерационных параметров приводит к потере асимптотического характера зависимости числа итераций от числа узлов сетки.

Другим подходом, предложенным Мюраном (Meurant G.A.) [114], является поворот (twisting). Ван дер Ворст (Van (ler Vorst Н.А.) [146] использовал эту идею по всем пространственным направлениям при решении двумерных и трехмерных задач, что позволило решать двумерные уравнения на 4 процессорах, а трехмерные уравнения на 8 процессорах параллельными аналогами ICCG (O), MICCG (O) (без роста итераций). Такое упорядочение иногда называют упорядочением Ван дер Ворста (Van der Vorst ordering). В работе [115] используются повторяющиеся блоки из четырех для решения двумерной задачи на 8 процессорах, при этом ускорение было около 6. Мюран (Meurant G.A.) считает, что увеличение числа итераций связано с повторением блоков. Заметим, что в работах [114,115,146] фактически используются упорядочения типа Domain Decomposition ordering с разными направлениями возрастания номеров узлов в разных подобластях.

В работе Даффа (Duff I.S.), Мюрана (Meurant G.A.) [81] численно исследуется влияние различных способов упорядочения на скорость сходимости метода ICCG (O) для двумерных задач. Рассматриваются упорядочения Катхилла-Макки (Curthill Mckee) (СМ), обратное упорядочение Катхилла-Макки (RCM), блочное СМ, упорядочение минимальной степени, красно-черное упорядочение, попеременно-диагональное, упорядочения рассечениями (в одном пространственном направлении), спиральное упорядочение, 4-х цветное упорядочение, упорядочения Вал дер Ворста и некоторые другие. Заметим, что СМ упорядочение на ортогональной сетке в случае пятиточечного шаблона фактически является диагональным упорядочением. Расчеты показали, что среди всех способов упорядочения, удобных для распараллеливания, только диагональные упорядочения (diagonal ordering) и упорядочения Ван дер Ворста (Van der Vost ordering) для 4-х процессоров, не приводят к росту числа итераций для всех рассмотренных модельных задач. Диагональное упорядочение удобно для расчетов на векторных машинах, но малоэффективно для расчетов на параллельных вычислительных системах с распределенной памятью [140]. В работе [68] изучение структуры матрицы, обратной к матрице предобусловливания неполного разложения Холецкого, объясняет успешность использования обратного упорядочения Катхилла-Макки с точки зрения скорости сходимости итераций при решении системы уравнений Ау = /, где разреженная матрица, А = Ат > 0.

В работе Ортеги (Ortega J.M.), Стотланда (Stotland S.A.) [140] исследуется скорость сходимости и эффективность метода SSORCG при использовании красно-черного и многоцветного («many colour») упорядочений, упорядочения полосками (strip ordering), упорядочения Ван дер Ворста. В двумерных задачах при оптимальном значении параметра релаксации при всех рассмотренных способах упорядочения число итераций растет с ростом Nh быстрее, чем y/Nh, и, кроме того, при использовании упорядочения полосками число итераций растет с ростом числа процессоров.

Нотей (Notay Y.) в работах [122,123] предложил использовать способ упорядочения неизвестных типа «domain decomposition» («domain decomposition like ordering»), для распараллеливания метода DRIC [124]. Теоретически доказал [123], что число итераций в параллельном методе DRIC пропорционально /NhЧисло итераций в расчетах [122] было почти пропорционально /NkВ параллельном методе DRIC число итераций достаточно медленно растет с ростом числа процессоров.

В работе Маголу монд Маде (Magolu monde Made М.), ван дер Ворста (van der Vorst Н.А.) [Ill] предложен параллельный вариант метода GRICобобщенной неполной факторизации с релаксацией для случая равномерных ортогональных сеток. Разбиение области расчета происходит в одном пространственном направлении. Определение искомых функций при обращении матрицы предобусловливания в узлах сетки вблизи границы, с которой начинается расчет происходит более сложным образом, чем при упорядочении, соответствующему разбиению в одном пространственном направлении полосками. Благодаря этому значительно уменьшается число итераций.

Заметим, что техника ILU факторизации была первоначально развита для М-матриц. В общем случае ILU факторизация может столкнуться с рядом трудностей. Это способствовало развитию методов приближенного обращения («approximate inverse»). Идея конструирования таких методов — найти разреженную матрицу М такую, что || AM — Е || мало в некоторой норме, где Еединичная матрица. При таком предобусловливании обращение двух треугольных матриц заменяется на умножение на разреженную матрицу, что значительно проще распараллеливается. Среди работ в этом направлении следует отметить [73,92,107].

Одним из перспективных направлений в развитии параллельного предобусловливания является многоуровневое предобусловливание [94,125,129]. Многоуровневое предобусловливание приводит к очень быстрой сходимости метода, причем число итераций почти не зависит от размера сетки [129]. Для неструктурированных сеток многоуровневое предобусловливание рассмотрено в работах [63,74]. Однако такие методы чрезвычайно трудоемки, имеют сложный алгоритм, при большом числе уровней требуют хранения большого количества информации. Кроме того методы с многоуровневым предобусловливанием оказываются не всегда эффективно применимы.

Следует отметить, что в настоящее время используются и другие эффективные методы, например методы Гаусса-Зейделя [134, 37], верхней релаксации[45,87], локальной релаксации [84]. Алгоритмы этих методов хорошо поддаются распараллеливанию при использовании красно-черного упорядочения [37]. Как показано в работе [143], лучшей скоростью сходимости по сравнению с методами Гаусса-Зейделя, верхней релаксации и локальной релаксации обладает, а — (3 алгоритм, предложенный Б. Н. Четверушкиным в работе [49] и развитый далее в работе [3]. Параллельная реализация этого метода подробно рассмотрена Б. Н. Четверушкиным и Н. Г. Чурбановой в работе [52]. В работе [143] показано, что при решении уравнения для давления в задачах многофазной фильтрации жидкости, а — (3 метод в 3.5−5.5 раз быстрее метода Гауса-Зейделя, и в 2 раза быстрее метода верхней релаксации (SOR) (при использовании релаксации в, а — (3 алгоритме), и имеет лучшую эффективность параллелизации при расчетах на 8-процессориой станции Parsytec СС. а — (3 алгоритм эффективно распараллеливается на одномерный массив процессоров Parsytec СС (когда разбиение области расчета происходит в одном пространственном направлении). В работе [143] проведено сравнение этого метода с попеременно-треугольным методом сопряженных градиентов и его параллельным вариантом, предложенным в настоящей диссертации, при решении эллиптического уравнения на одном и на 2×2 процессорах. Время решения уравнения ПТМСГ и его параллельным вариантом было существенно меньше, чем при использовании, а — (3 алгоритма (в 3.4 раза на 1 процессоре и в 4.1 раза на 4 процессорах при числе узлов сетки N = 181×181).

Для решения систем линейных уравнений с заполненной матрицей часто используют LU разложение, разложение Холецкого, методы ортогонального приведения [37,79]. Алгоритмы решения систем линейных уравнений с теплицевыми матрицами и матрицами близкими к теплицевым рассматриваются в работе Воеводина В. В. и Тыр-тышникова Е. Е, [2] Параллельные алгоритмы обращения теплицевых матриц предложены вработах [2,100]. В работах Тыртышникова Е. Е. [144,145] предложен метод преобразования алгоритмов определенного типа для решения систем линейных уравнений в параллельные (векторизованные). Однако в получаемых при этом алгоритмах сильно возрастает объем вычислений и требуемой памяти. В работе Тыртышникова Е. Е. [47] предлагаются параллельные алгоритмы решения системы линейных уравнений Az = b, где матрица, А представима в виде суммы парных произведений теплицевых нижнетреугольных и верхнетреутольных матриц, в которых не увеличивается, а иногда даже требуется меньшая арифметическая работа, чем в известных последовательных алгоритмах.

Несмотря на большое количество работ, посвященных построению параллельных итерационных методов решения систем линейных уравнений с симметричной разреженной матрицей, эта проблема по прежнему остается актуальной и требует дальнейшего изучения. Косвенным подтверждением этого является нежелание использовать в расчетах нестационарных задач неявных схем [126], что требует решения систем линейных уравнений. Существующие параллельные методы либо медленно сходятся, либо очень трудоемки, не всегда применимы, библиотеки решения задач линейной алгебры с разреженной матрицей недостаточно разработаны.

Подводя итог приведенному выше обзору литературы, следует отметить, что основное внимание было уделено параллелизации метода сопряженных градиентов с предобусловливанием 1С, RIC и его модификаций. Причем в большинстве случаев для аппроксимации использовалась равномерная ортогональная сетка. Вопрос о построении параллельных аналогов точечных методов MICCG, ПТМСГ в случае использования для аппроксимации ортогональной равномерной и неравномерной сетки для произвольного числа процессоров оставался открытым. Недостаточно изучен вопрос о параллелизации точечных методов ICCG, MICCG или их вариантов при аппроксимации уравнений на неструктурированной треугольной сетке, равномерной треугольной сетке, локально измельчающейся сетке на основе прямоугольных элементов. Существующие подходы являются сложными, трудоемкими, не всегда применимыми.

Целью настоящей работы является создание эффективных параллельных аналогов итерационных методов сопряженных градиентов с факторизованной матрицей предобусловливания для решения систем уравнений Ay — f с симметричной положительно определенной сильно разреженной плохо обусловленной матрицей, А на параллельных вычислительных системах с распределенной памятью, имеющих достаточно высокую скорость сходимости и не слишком сложный алгоритм реализации.

В частности стояла задача построения параллельных вариантов точечных методом MICCG (O) [93], ПТМСГ [41,25,26] для решения дискретных двумерных и трехмерных уравнений на ортогональных равномерных и неравномерных сетках в области расчета, являющейся прямоугольником или прямоугольным параллелипипедом. При этом предполагается, что область расчета не является очень сильно вытянутой в одном пространственном направлении. Для решения эллиптических уравнений в двумерных сильно вытянутых подобластях следует использовать метод MAFS [109], который требует для сходимости в этом случае значительно меньше итераций. Предполагалось также создание параллельных аналогов методов типа ICCG, MICCG в случае использования для аппроксимации дифференциальных уравнений треугольных равномерных сеток и неструктурированных сеток. При построении параллельных аналогов всех этих методов основной задачей было сохранение характера асимптотической зависимости числа итераций от числа узлов сетки в случае равномерной ортогональной и равномерной треугольной сеток. Важность создания именно таких параллельных аналогов связана с тем, что на параллельных вычислительных системах осуществляются расчеты задач с очень большим числом узлов сетки, и потеря характера асимптотической зависимости приведет к колосальному числу итераций в параллельных расчетах.

Второе требование к построенным параллельным методам состояло в том, чтобы рост числа итераций с ростом числа процессоров был бы невелик по сравнению с однопроцессорными методами, чтобы эти параллельные методы были эффективны.

Исследование эффективности предложенных методов осуществлялось с помощью расчетов модельных задач на 32-х процессорной параллельной станции Parsytec СС и на многопроцессорной вычислительной системе МВС-1000М, содержащей 768 процессоров. 32-х процессорная станция Parsytec СС, имела производительность 200 MFLOPS, тактовую частоту каждого процессора 100 Мгц, скорость обмена данными 600 Мбит/с., объем оперативной памяти на процессор 256 Мб. Использовалась библиотека организации обменов PARIX. Вычислительная система МВС-1000М, имеет пиковую производительность 1 TFLOPS, тактовую частоту каждого процессора 667 Мгц, пропускную способность канала 2000 Мбит/сек, объем оперативной памяти на процессор 1 Гб. Использовалась библиотека организации обменов MPI. Программы были написаны на языке Dec Visual Fortran.

Целью диссертации была также аппробация предложенных методов в расчетах некоторых задач гидродинамики.

Научная новизна работы состоит в том, что благодаря использовании стратегии упорядочения узлов сетки созданы параллельные аналоги метода сопряженных градиентов с предобусловливанием MIC, ПТМ (точечные методы), для решения двумерных и трехмерных краевых задач для эллиптических уравнений на ортогональной равномерной и неравномерной сетках для произвольного числа процессоровсконструированы параллельные аналоги вариантов ICCG, MICCG (назовем их VICCG, VMICCG) [37, добавление Капорина И. Е., 105,112], в которых матрица предобусловливания имеет вид В = (D~x + A~)D (D~1 + (yl~)T), где А~ - строго нижнетреугольная часть матрицы, А (элементы диагональной матрицы D определяются из тех же условий, что в методах ICCG, MICCG), для решения двумерных краевых задач для эллиптических уравнений на треугольных равномерных и неструктурированных сетках в произвольной односвязной области расчета и на локально измельчающихся сетках на основе прямоугольных элементов. Заметим, что такой выбор матрицы В продиктован необходимостью теоретического выбора оптимальных итерационных параметров, обеспечивает более простой алгоритм распараллеливания, возможность применения приема Айзенштата [37] с целью удешевить каждую итерацию. В настоящей работе прием Айзенштата не применялся.

Для достаточно гладких коэффициентов в дифференциальном уравнении в предложенных параллельных вариантах методов MICCG (0), MAFCG, ПТМСГ теоретически исследованы характер асимптотической зависимости числа итераций от числа узлов сетки и скорость роста числа итераций с ростом числа процессоров. Получены теоретические оценки числа итераций параллельных вариантов методов MICCG (O), ПТМСГ, VMICCG для модельных задач на ортогональной равномерной сетке или на равномерной треугольной сетке.

В созданных параллельных методах сохраняется характер асимптотической зависимости числа итераций от числа узлов сетки для равномерной ортогональной и равномерной треугольной сеток такой же, как в соответствующих однопроцессорных методах. При этом происходит приемлемый рост числа итераций с ростом числа процессоров по крайней мере для их умеренного количества, то есть число итераций в параллельных вариантах методов возрастает менее, чем в 2 раза по сравнению с однопроцессорными методами. В параллельных аналогах методов ПТМСГ, MICCG, VMICCG — варианта MICCG это достигается благодаря теоретическому выбору параметров, оптимизирующему теоретические оценки числа итераций параллельных методов, полученные в настоящей диссертации.

Предложен способ автоматического выбора параметров в MICCG (O) и параллельных вариантах MICCG (O), который обеспечивает приемлемый рост числа итераций с ростом числа процессоров в случае использования для аппроксимации дифференциальных уравнений сильно неравномерной сетки, автоматический учет разрывов коэффициентов, существенно уменьшает рост числа итераций с ростом числа процессоров при решении анизотропных задач и позволяет в ряде случаев решать такие задачи на многопроцессорной ЭВМ с хорошей эффективностью.

Указаны способы выбора итерационных параметров для метода VMICCG и его параллельных аналогов в случае использования для аппроксимации дифференциальных уравнений неструктурированных треугольных сеток и локально измельчающихся сеток на основе прямоугольных элементов. Эти итерационные параметры обеспечивают приемлемый рост числа итераций с ростом числа процессоров. Такой выбор параметров в случае неструктурированной треугольной сетки позволяет существенно сократить число итераций в расчетах модельных задач на одном процессоре по сравнению с нулевыми параметрами.

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

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

В диссертации предложен алгоритм решения как стационарных, так и нестационарных двумерных и трехмерных задач гидродинамики в естественных переменных «скорость-давление» на параллельных вычислительных системах. При этом для моделирования течений несжимаемой жидкости используется система квазигидродинамических уравнений [53,54], а для решения эллиптического уравнения для давленияпараллельные варианты метода MICCG (O), предложенные в настоящей диссертации.

Практическая значимость диссертационной работы состоит прежде всего в том, что созданы и аппробированы в расчетах эффективные параллельные методы решения систем уравнений Ау = /, где, А = Ат > 0, сильно разреженная плохо обусловленная матрица, имеющие достаточно простой алгоритм. Эти методы могут быть использованы для численного решения задач математической физики на подробных пространственных сетках, в математической модели которых имеются эллиптические уравнения. Кроме того эти методы могут использоваться для решения краевых задач для параболических уравнений, если для аппроксимации последних используются неявные схемы.

Некоторые из предложенных методов включаются в создаваемую в настоящее время параллельную библиотеку программ для решения систем линейных уравнений с разреженной матрицей и создаваемый пакет GIMM — пакет решения задач механики сплошной среды.

Приведенные в главе 4 результаты расчета течений в кубической каверне могут использоваться для тестирования численных алгоритмов расчета трехмерных течений. Результаты численного решения задачи термокапиллярной конвекции в условиях пониженной гравитации помогли выяснить причину неравномерного роста кристаллов в экспериментах, проводимых на искусственных спутниках Земли. СТРУКТУРА ДИССЕРТАЦИИ.

Диссертация состоит из 4 глав, введения, заключения, списка литературы и приложений.

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

содержит 150 работ. Объем диссертации 219 страниц.

Первая глава диссертации посвящена построению параллельных вариатов методов MICCG (O), MAFCG, ICCG (O) для решения двумерных краевых задач для эллиптических уравнений в прямоугольной области расчета. При этом предполагается, что область расчета не является очень сильно вытянутой в одном пространственном направлении.

Разностная аппроксимация дифференциальных уравнений осуществляется на равномерной и неравномерной ортогональной разностной сетке и на локально измельчающейся сетке на основе прямоугольных элементов. При аппроксимации эллиптического уравнения на ортогональной равномерной и неравномерной сетках используется пятиточечный шаблон. Разбиение области расчета происходит в двух пространственных направлениях. Для построения параллельных вариантов методов используются упорядочения Domain Decomposition ordering 1 (DD01) и Domain Decomposition ordering 2 (DD02). В упорядочении DDOl во всех подобластях организуется одинаковый порядок следования узлов сетки, при использовании DD02 существуют 4 типа подобластей с различными упорядочениями узлов сетки внутри них.

Рассматривается метод PICCG — параллельный вариант метода ICCG (O) с DD01 упорядочением узлов сетки для решения дискретных аналогов двумерных эллиптических уравнений. Предлагаются методы PMICCG1, PMICCG2 — параллельные варианты метода MICCG (O) с упорядочениями DD01 и DD02 для решения дискретных эллиптических уравнений на равномерной сетке, а также параллельный вариант метода MAFCG с DD01 упорядочением.

Проводится теоретическое исследование скорости сходимости методов PMICCG1, PMICCG2, параллельного варианта MAFCG в случае ортогональной равномерной сетки и задачи Дирихле. Получены теоретические оценки числа итераций методов PMICCG1, PMICCG2 для модельной задачи. Указываются итерационные параметры, позволяющие сохранить в методах PMICCGl, PMICCG2 характер асимптотической зависимости числа итераций от числа узлов сетки такой же, как в методе MICCG (O), и обеспечивающие приемлемый рост числа итераций с ростом числа процессоров.

Проводится экспериментальное исследование скорости сходимости и эффективности всех рассмотренных параллельных методов с помощью расчетов модельных задач на параллельной станции Parsytec СС.

Исследуется влияние формы подобластей при разбиении прямоугольной области расчета на скорость сходимости предложенных параллельных методов с помощью решения модельных задач. С помощью расчетов модельных задач исследуется влияние анизотропии коэффициентов дифференциального уравнения на скорость сходимости предложенных параллельных аналогов ICCG (O), MAFCG.

Предлагаются способы автоматического выбора итерационных параметров для методов PMICCGl, PMICCG2, которые позволяют использовать эти методы для решения дискретных аналогов двумерных эллиптических уравнений на сильно неравномерной ортогональной сетке и обеспечивают приемлемый рост числа итераций с ростом числа процессоров. Эти способы выбора параметров позволяют автоматически отслеживать точки разрыва коэффициентов дифференциального уравнения. Приводятся расчеты, демонстрирующие, что использование автоматического выбора параметров позволяет существенно уменьшить число итераций при решении анизотропных задач, а в ряде случаев даже эффективно решать анизотропные задачи на многопроцессорной вычислительной системе.

В последнем параграфе главы 1 для решения дискретных эллиптических уравнений на локально измельчающейся сетке предлагается использовать методы VICCG, VMICCG — варианты методов ICCG (O), MAFCG (который является методом MICСG (0) без возмущения, то есть с нулевыми параметрами) [37, добавление], [105,112]. Созданы методы PVICCG, PVMICCGпараллельные аналоги методов VICCG, VMICCG, в которых используется DD01 упорядочение узлов сетки. В методе PVMICCG используются итерационные параметры, полученные для случая равномерной ортогональной сетки с некоторым осредценным шагом. Проводится исследование скорости сходимости и эффективности методов с помощью расчетов модельной задачи.

Вторая глава диссертации посвящена решению краевых задач для двумерных эллиптических уравнений в произвольной односвязной области расчета параллельными вариантами метода сопряженных градиентов с факторизованной матрицей предобусловливания. Построение параллельных методов и исследование скорости их сходимости проводится на примере задачи Дирихле. Для аппроксимации дифференциальных уравнений используется равномерная треугольная или неструктурированная треугольная сетки. В качестве первоначального упорядочения узлов сетки при расчетах на одном процессоре используется КатхиллаМакки упорядочение. Предложены методы PVICCG, PVMICCG — параллельные аналоги методов VICCG, VMICCG — вариантов ICCG, MICCG [37, добавление Капорина И.Е.], [105,112]. При построении параллельных вариантов VMICCG в случае равномерной треугольной сетки рассматриваются различные способы упорядочения узлов сетки, в частности DD01, DD02, DD03. При использовании DD03 упорядочения существуют 2 типа подобластей, в которых используются одинаковые упорядочения узлов сетки. В параллельном варианте VICCG используется DD01 упорядочение. В случае неструктурированной треугольной сетки используется DD01 упорядочение.

В случае равномерной треугольной сетки производится теоретическое исследование скорости сходимости методов PVMICCG (с DD01 упорядочением) и VMICCG на примере модельной задачи, указан способ выбора итерационных параметров, которые практически обеспечивают сохранение в параллельных методах характера асимптотической зависимости числа итераций от числа узлов сетки, такого же, как в методе VMICCG, то есть 0{]n (2/e)tfN).

В случае неструктурированной треугольной сетки для метода PVMICCG предлагается способ выбора итерационных параметров, который является обобщением способа выбора итерационных параметров для случая равномерных треугольных сеток. Рассматриваются различные способы разбиения области расчета на подобласти и производится их сравнение с точки зрения скорости сходимости итераций. Рассматриваются параллельные варианты методов VICCG, VMICCG, в которых используется обратное Катхилла-Макки упорядочение узлов сетки. В этих параллельных вариантах используется один из способов разбиений области расчета на подобласти.

С помощью расчетов модельных задач проводится исследование скорости сходимости методов РVICCG, PVMICCG как для случая равномерной треугольной сетки, так и для случая неструктурированной треугольной сетки. С помощью расчетов на умеренном числе процессоров параллельной вычислительной системы МВС 1000 М проводится исследование эффективности методов PVICCG, PVMICCG для случая равномерной треугольной сетки. Заметим, что расчеты задач, в которых использовались равномерная треугольная и неструктурированная треугольная сетки, происходили почти по одной и той же программе. Эта программа работала для всех рассмотренных способов разбиения области расчета, а также для обращения матриц, присланных из РФЯЦ-ВНИИЭФ (г. Саров).

В последнем параграфе главы 2 предложены методы PVMICCG с автоматическим выбором параметров для решения дискретных эллиптических уравнений с сильно отличающимися коэффициентами на неструктурированной треугольной сетке, указан способ автоматического выбора итерационных параметров. Для модельной задачи, в которой используется равномерная треугольная сетка, с помощью расчетов на умеренном числе процессоров произведено исследование скорости сходимости методов PVMICCG с упорядочениями DD01 и DD02 и автоматическим выбором параметров. Показано, что число итераций существенно уменьшается при использовании автоматического выбора параметров.

Третья глава диссертации посвящена построению параллельных вариантов ПТМ-СГ для решения двумерных и трехмерных краевых задач для эллиптических уравнений на ортогональной равномерной и неравномерной сетках. Областью расчета является прямоугольник или прямоугольный параллелипипед.

Предлагаются методы ППТМСГ1, ППТМСГ2 — параллельные варианты метода ПТМСГ для решения краевых задач для двумерных эллиптических уравнений. При этом используются соответственно DD01 и DD02 упорядочения узлов сетки те же, что в главе 1. Проводится теоретическое и экспериментальное исследование скорости сходимости этих методов в случае решения задачи Дирихле для эллиптических уравнений на равномерной сетке. Доказывается и подтверждается расчетами, что в методах ППТМСГ1, ППТМСГ2 такой же характер асимптотической зависимости числа итераций от числа узлов сетки, как в методе ПТМСГ (для одного процессора), рост числа итераций с ростом числа процессоров допустимый, причем более медленный в методе ППТМСГ2. Проводится сравнение ППТМСГ1 и ППТМСГ2 на примере решения модельных задач. Демонстрируется хорошая эффективность методов ППТМСГ1 и ППТМСГ2 при решении модельной задачи на умеренном числе процессоров.

Предлагаются методы ППТМСГЗ и ППТМСГ4 — параллельные варианты ПТМСГ для решения трехмерных разностных эллиптических уравнений, при построении которых область расчета разбивается соответственно в двух и трех пространственных направлениях. Проводится исследование скорости сходимости предложенных параллельных методов. Показывается, что число итераций растет с ростом числа процессоров очень медленно, в случае постоянных шагов сетки сохраняется характер асимптотической зависимости числа итераций от числа неизвестных при любом фиксированном массиве процессоров. Исследуется влияние формы подобластей на скорость сходимости и время счета методов ППТМСГ2, ППТМСГЗ. Проводится сравнение методов ППТМСГЗ и ППТМСГ4 на примере решения модельных задач. Заметим, что алгоритм метода ППТМСГ4 значительно сложнее, чем алгоритм ППТМСГЗ, и требует больше инициализаций обменов.

Получены теоретические оценки числа итераций в методах ППТМСГ2, ППТМСГЗ, ППТМСГ4 для модельных задач.

Приводятся приближенные формулы для времени счета итерациионного процесса в методах ППТМСГЗ и ППТМСГ4. В этих формулах учитываются времена выполнения арифметических операций и пересылок. Исходя из этих формул произведен анализ условий целесообразности применения метода ППТМСГЗ или ППТМСГ4.

В четвертой главе диссертации предложен параллельный вариант метода MICCG (O) для решения трехмерных эллиптических уравнений на равномерной ортогональной сетке, для модельной задачи проведено теоретическое исследование скорости сходимости метода и указаны теоретически оптимальные итерационные параметры, минимизирующие полученную оценку числа итераций. При использовании этих итерационных параметров в параллельном варианте MICCG (O) сохраняется такой же характер асимптотической зависимости числа итерации от числа узлов сетки, как в методе MICCG (O). Проведено численное исследование скорости сходимости параллельного метода для модельных задач с граничными условиями Дирихле и Неймана.

Во втором параграфе главы 4 построен алгоритм решения как стационарных, так и нестационарных задач гидродинамики в естественных переменных «скорость-давление» на многопроцессорных вычислительных системах на примере трехмерных задач. Для моделирования течений используется система квазигидродинамических (КГД) уравнений [53,54], записанная в эйлеровой системе координат, а для решения второй краевой задачи для уравнения Пуассона для давления — параллельный вариант метода MICCG (O), предложенный в § 1 главы 4 в настоящей диссертации. Осуществляется численное моделирование пространственных течений в каверне с подвижной верхней крышкой. Исследуется сходимость численного решения по сетке. Приведены результаты расчетов течений жидкости для чисел Рейнольдса Re = 100,1000,2000. Полученные численные результаты сопоставляются с имеющимися в литературе данными.

В третьем параграфе главы 4 с помощью вычислительного алгоритма, построенного на основе квазигидродинамической системы уравнений [53,54], проводится численное исследование задачи о термокапиллярной конвекции в прямоугольной полости с учетом микрогравитации. Для решения задачи используются методы 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) рост числа итераций с ростом числа процессоров медленный.

4.Параллельные варианты метода ПТМСГ с различными способами упорядочения узлов сетки типа Domain Decomposition ordering для решения двумерных и трехмерных краевых задач для эллиптических уравнений на ортогональной равномерной и неравномерной сетках в прямоугольнике или в прямоугольном параллелипипедедля трехмерных задач используются разбиения области расчета в двух и трех пространственных направленияхпроведенное теоретическое и численное исследование скорости сходимости параллельных вариантов ПТМСГ в случае равномерной сетки показывает сохранение характера асимптотической зависимости числа итераций от числа узлов сетки во всех предложенных параллельных вариантах такого же, как в ПТМСГ (при фиксированном массиве процессоров), а также допустимый рост числа итераций (для двумерных задач) и медленный рост числа итераций (для трехмерных задач) с ростом числа процессоровполучены теоретические оценки числа итераций параллельных вариантов ПТМСГ для модельных задач.

5.Алгоритм решения задач гидродинамики на многопроцессрных вычислительных системах, в котором используются КГД уравнения и параллельный варианты MICCG (O) — результаты применение этого алгоритма для численного моделирования течения вязкой несжимаемой жидкости в кубической каверне с подвижной верхней крышкой при Re = 100,1000,2000; результаты математического моделирования термокапиллярной конвекции в прямоугольной полости в условиях пониженной гравитациипродемонстрирована зависимость тепломассообмена от колебаний вектора остаточного ускорения, эта зависимость может вызывать неравномерный рост кристаллов даже в режиме ламинарного конвективного движения.

АППРОБАЦИЯ РАБОТЫ. Результаты диссертации докладывались и обсуждались на.

— VI Всероссийской конференции РТА «Транспьютерные системы и их применение» (г. Домодедово, октябрь 199Сг.).

— международной конференции 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 г.).

— научном семинаре им. К. И. Бабенко под руководством члена-корреспондента РАН А. В. Забродина в Институте прикладной математики им. М. В. Келдыша РАН (г. Москва, апрель 2004 г.).

Результаты, полученные автором нашли отражение в учебном курсе лекций члена корреспондента РАН Б. Н. Четверушкина «Параллельные вычисления» для студентов ВМиК МГУ и МФТИ (ГУ), а также в курсе лекции «Математическое моделирование» для студентов МГТУ СТАНКИН.

Общее количество статей по теме диссертации — 13, докладов на международных и всероссийских конференциях 6.

Работа поддержана РФФИ (Гранты 96−01−1 753, 98−01−155, 99−01−1 215, 99−790 388, 01−01−61, 02−01−700, 02−07−90 168), Российской Академией Наук (контракт N 10 002−251 /-17/026−023/70 403−436).

Автор выражает благодарность члену корреспонденту РАН Б.Н. Четверушки-ну за проявленное внимание к работе, полезные обсуждения, замечания и поддержку работы. Автор выражает благодарность профессору Т. Г. Елизаровой и старшему научному сотруднику МГУ факультета ВМиК И. С. Калачинской за постановку задач гидродинамики и обсуждение результатов расчетов, профессору В. Ф. Тишкину за проявленный интерес к работе, ценные советы и поддежку работы. Автор выражает благодарность младшему научному сотруднику С. Н. Болдыреву за предоставленные неструктурированные сетки в квадратной области расчета и за результаты разбиения этой области на подобласти и старшему научному сотруднику И. В. Попову за предоставленные треугольные сетки в треугольной области расчета. Автор благодарит старшего научного сотрудника С. В. Полякова за проявленный интерес к работе и ценные советы. Автор выражает благодарность сотрудникам РФЯЦ-ВНИИЭФ (г. Саров) Бартеньеву Ю. Г. и Щанниковой Е. Б. за проявленный интерес к работе, предоставленные матрицы и результаты расчетов задач используемым ими методом.

ВЫВОДЫ К ГЛАВЕ 4.

В четвертой главе диссертации предложен параллельный вариант метода MICCG (O) для решения трехмерных эллиптических уравнений в прямоугольном параллелипи-педе на равномерной ортогональной сетке на основе упорядочения DD01 при разбиении области расчета в двух пространственных направлениях. Для модельной задачи проведено теоретическое исследование скорости сходимости метода и указаны итерационные параметры, минимизирующие полученную оценку числа итераций. При использовании этих итерационных параметров в параллельном варианте MICCG (O) сохраняется такой же характер асимптотической зависимости числа итераций от числа узлов сетки, как в методе MICCG (O).

Расчеты модельных задач показали, что число итераций в предложенном методе пропорционально /Nh. Средний по Nh коэффициент возрастания числа итераций при решении задачи Дирихле для уравнения Пуассона не превосходил 1.87 до 100 процессоров. При решении задачи Неймана для уравнения Пуассона на 25 процессорах при Nh = 82 этот коэффициент был равен 1.57.

Во втором параграфе главы 4 построен алгоритм решения как стационарных, так и нестационарных трехмерных задач гидродинамики в естественных переменных «скорость-давление» на многопроцессорных вычислительных системах. Для моделирования течений используется система квазигидродинамических уравнений, записанная в эйлеровой системе координат, а для решения второй краевой задачи для уравнения Пуассона для давления — параллельный вариант метода MICCG (O), предложенный в настоящей главе.

Осуществляется численное моделирование пространственных течений в кубической каверне с подвижной верхней крышкой. С помощью расчетов задачи при Re=1000 с Nh = 42, 82,162 продемонстрирована сходимость численного решения по сетке.

Приведены результаты расчетов для чисел Рейнольдса Re = 100,1000,2000. Расчеты показали, что при Re=100 компоненты скорости по оси OZ малы, и в плоскости симметрии z — 0.5 имеется хорошее совпадение с результатами расчета задачи в двумерной постановке. При Re=1000,2000 течение становится трехмерным. Наблюдается существенное усложнение картины течения, связанное с образованием дополнительных источников и стоков в плоскостях х = 0.5, у = 0.5. Полученные численные результаты сопоставляются с имеющимися в литературе данными. Приведенные результаты могут использоваться для тестирования численных алгоритмов расчета трехмерных течений.

В последнем параграфе главы 4 с помощью вычислительного алгоритма, построенного на основе квазигидродинамической системы уравнений, проведено численное исследование задачи о термокапиллярнной конвекции в прямоугольной полости с учетом микрогравитации. Задача решалась на 4-х процессорах станции Parsytec СС и на персональном компьютере INTEL CELERON 433 MHZ, результаты расчетов совпали. Для расчетов использовались методы MICCG (O) и PMICCG1 с итерационными параметрами сг, полученными теоретически для модельной задачи в главе 1.

Расчеты показали, что при совместном действии термокапиллярных сил и постоянного ускорения силы тяжести, ортогонального свободной поверхности при Gr < 106 течение жидкости стационарное, при Gr = 106 устанавливается колебательный режим течения жидкости.

Для практических приложений очень важно выяснить влияние микроускорений на конвективное движение. Расчеты показали, что колебания микроускорения приводят к колебаниям температуры и теплового потока в расплаве, что вызывает колебания в скорости роста кристаллов. Это может вызывать неравномерный рост кристаллов даже в режиме ламинарного конвективного движения. Полученные результаты хорошо согласуются с известными экспериментальными данными.

ЗАКЛЮЧЕНИЕ

.

В диссертации предложены параллельные варианты некоторых методов сопряженных градиентов с факторизованными матрицами предобусловливания для решения двумерных и трехмерных краевых задач для эллиптических уравнений. Рассматривались дискретные аналоги эллиптических уравнений на равномерной и неравномерной ортогональной сетках в областях расчета, являющихся прямоугольником или прямоугольным параллелипипедом, на локально измельчающихся сетках на основе прямоугольных элементов (для двумерных задач в прямоугольнике), на равномерной треугольной и неструктурированной треугольной сетках в произвольной двумерной односвязной области расчета. Построение параллельных методов основано на использовании стратегии упорядочения узлов сетки. Проведено теоретическое и численное исследование скорости сходимости предложенных параллельных методов. С помощью предложенных в диссертации методов произведено численное решение ряда задач гидродинамики.

Сформулируем основные результаты, полученные в диссертации.

1. Созданы методы PMICCGl, PMICCG2 — параллельные варианты метода MICCG (O) с упорядочениями DDOl, DD02, параллельный вариант метода MAFCG с DD01 упорядочением узлов сетки для решения двумерных эллиптических уравнений на равномерной ортогональной сетке в прямоугольной области расчета, параллельный вариант метода MICCG (O) с DD01 упорядочением для решения трехмерных эллиптических уравнений на равномерной ортогональной сетке в прямоугольном парал-лелипипеде. При этом предполагается разбиение области расчета в двух пространственных направлениях, возможно использование произвольного числа процессоров (непростого).

Получены теоретические оценки числа итераций методов PMICCGl, PMICCG2 для модельной задачи — задачи Дирихле для уравнения Пуассона в единичном квадрате на равномерной ортогональной сетке с одинаковым шагом по обоим пространственным переменным. Теоретически доказано и подтверждено расчетами, что в случае достаточно гладких коэффициентов дифференциального уравнения и равномерной ортогональной сетки с одинаковым шагом по обоим пространственным переменным во всех перечисленных выше параллельных методах сохраняется характер асимптотической зависимости числа итераций от числа узлов сетки такой же, как в соответствующих однопроцессорных методах (при фиксированных р и р2, где рх х р2 = рчисло процессоров). Наблюдается приемлемый (достаточно медленный) рост числа итераций с ростом числа процессоров. Это достигается благодаря специальному выбору итерационных параметров. Теоретически доказано, что для достаточно больших р = р2 = у/р для сходимости методов PMICCGl, PMICCG2, параллельного варианта MAFCG требуется 0(1а.(2/е)^/ру/Щ) итераций. В методе PMICCG2 рост числа итераций с ростом числа процессоров медленнее, чем в PMICCGl, а алгоритм сложнее.

Рассмотрен также метод PICCG — параллельный вариант метода ICCG (O). Расчеты модельных задач показали хорошую эффективность методов PICCG, PMICCGl, PMICCG2, параллельного варианта MAFCG для умеренного числа процессоров. С помощью расчетов модельных задач на равномерной сетке показано, что оптимальной с точки зрения скорости сходимости итераций формой подобластей при разбиении прямоугольной области расчета является квадрат. Однако, как показывают расчеты, при решении анизотропных задач в предложенных параллельных методах может наблюдаться быстрый рост числа итераций с ростом числа процессоров.

2.Созданы методы PMICCGl, PMICCG2 — параллельные варианты метода MICCG (O) с упорядочениями DDOl, DD02 для решения двумерных эллиптических уравнений на неравномерной ортогональной сетке, предложен способ автоматического выбора итерационных параметров в методах PMICCGl, PMICCG2, MICCG (O), который обеспечивает допустимый рост числа итераций с ростом числа процессоров в случае использования для аппроксимации дифференциального уравнения сильно неравномерных ортогональных сеток. Этот способ выбора параметров автоматически учитывает точки разрыва коэффициентов, позволяет существенно уменьшить рост числа итераций с ростом числа процессоров при решении анизотропных задач. В ряде случаев автоматический выбор параметров позволяет эффективно решать задачи с анизотропными коэффициентами в дифференциальном уравнении на умеренном числе процессоров.

3.Созданы методы PVICCG, PVMICCG — параллельные аналоги методов VICCG, VMICCG для решения двумерных эллиптических уравнений в произвольной односвязной области расчета на равномерных треугольных и неструктурированных треугольных сетках и в прямоугольных областях расчета на локально измельчающейся сетке на основе прямоугольных элементов.

Используется СМ упорядочение узлов треугольной сетки при решении системы уравнений методами VICCG, VMICCG. В методах PVMICCG в случае равномерных треугольных сеток используются упорядочения DDOl, DD02, DD03, а в методе PVICCG — DDOl упорядочение.

Получены теоретические оценки числа итераций методов VMICCG, PVMICCG с DDOl упорядочением для модельной задачи — задачи Дирихле для уравнения Пуассона в области расчета, являющейся равносторонним треугольником. На примере этой модельной задачи теоретически доказано и подтверждено расчетами, что в случае равномерной треугольной сетки в методе PVMICCG при фиксированных pi и Р2 практически сохраняется такой же характер асимптотической зависимости числа итерации от числа узлов сетки, как в методе VMICCG (i0{n{2le).

Для случая неструктурированной треугольной сетки и локально измельчающейся сетки в методах PVICCG, PVMICCG используется упорядочение DDOl, указан выбор итерационных параметров в методах PVMICCG, который обеспечивает приемлемый рост числа итераций с ростом числа процессоров. В случае неструктурированных треугольных сеток с помощью расчетов модельных задач исследована возможность использования различных способов разбиения области расчета. Показана хорошая эффективность параллельных методов PVICCG, PVMICCG при решении модельной задачи на локально измельчающейся сетке на умеренном числе процессоров.

4.Предложены методы ППТМСГ1, ППТМСГ2 — параллельные варианты метода ПТМСГ с использованием DDOl, DD02 упорядочений узлов сетки для решения двумерных эллиптических уравнений в прямоугольной области расчета на ортогональной равномерной и неравномерной сетках. Предложены методы ППТМСГЗ, ППТМ-СГ4 — параллельные варианты метода ПТМСГ для решения трехмерных эллиптическ их уравнений на ортогональной равномерной и неравномерной сетках в прямоугольном параллелипипеде. При этом для построения параллельного метода производится разбиение области расчета в двух пространственных направлениях (в методе ППТМ-СГЗ) и в трех пространственных направлениях (в методе ППТМСГ4).

Получены теоретические оценки числа итераций методов ППТМСГ2 и ППТМСГЗ, ППТМСГ4 для модельных задач — задач Дирихле для уравнения Пуассона на равномерной ортогональной сетке в прямоугольной области расчета и в области расчета, являющейся прямоугольным параллелипипедом. Теоретически доказано и подтверждено расчетами, что в случае достаточно гладких коэффициентов дифференциального уравнения и равномерной ортогональной сетки в методах ППТМСГ1, ППТМСГ2, ППТМСГЗ, ППТМСГ4 сохраняется характер асимптотической зависимости числа итераций от числа узлов сетки такой же, как в методах ПТМСГ соответственно для двумерных и трехмерных задач (при фиксированных pi и р2 или pi, р2 и рз). Наблюдается приемлемый рост числа итераций с ростом числа процессоров для двумерных задач и медленный рост числа итераций с ростом числа процессоров для трехмерных задач. Теоретически доказано, что в случае одинакового числа узлов сетки Nh по всем пространственным направлениям для достаточно больших pt = р2 или pi = р2 = Рз в методах ППТМСГ1, ППТМСГ2 требуется 0(1а (2/е)^ру/Щ) итераций, а в методе ППТМСГ4 требуется 0(1п (2/е)^ру/Щ итераций для сходимости. Из теоретических исследований следует, что метод ППТМСГ4 целесообразно применять для очень больших Nh и достаточно больших р. Расчеты модельных задач показали хорошую эффективность методов ППТМСГ1, ППТМСГ2 для умеренного числа процессоров.

5. Пред л о жен алгоритм решения как стационарных, так и нестационарных задач гидродинамики в естественных переменных «скорость-давление» на многопроцессорных вычислительных системах. В этом алгоритме для описания течения жидкости используются КГД уравнения, для решения задачи Неймана для эллиптического уравнения для давления — параллельный вариант MICCG (O).

Произведено численное моделирование пространственных течений в кубической каверне с подвижной верхней крышкой для чисел Рейнольдса Re = 100,1000,2000. С помощью расчетов продемонстрирована сходимость численного решения по сетке. Показано, что при Re=1000,2000 течение имеет существенно трехмерный характер. Полученные численные результаты сопоставлены с имеющимися в литературе данными и могут использоваться для тестирования численных алгоритмов расчета трехмерных течений.

Проведено численное исследование задачи о термокапиллярнной конвекции в прямоугольной полости с учетом микрогравитации. При этом использовались предложенные в главе 1 методы решения эллиптического уравнения. Установлено с помощью расчетов, что при совместном действии термокапиллярных сил и постоянного ускорения силы тяжести, ортогонального свободной поверхности, при Gr < 10е течение жидкости стационарное, при Gr = 106 устанавливается колебательный режим течения жидкости.

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

В дальнейшем предполагается построение параллельных аналогов методов ICCG,.

MICCG для решения дискретных эллиптических уравнений на неструктурированной треугольной сетке в произвольной двумерной односвязной области расчета. Методы ICCG, MICCG используют более точное предобусловливание матрицы, А и должны требовать меньшего числа итераций для сходимости. При этом в параллельном варианте метода MICCG предполагается использовать итерационные параметры, определенные для метода PVMICCG.

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

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

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