Параллельные итерационные методы с факторизованной матрицей предобусловливания для решения эллиптических уравнений тема диссертации и автореферата по ВАК РФ 01.01.07, доктор физико-математических наук Милюкова, Ольга Юрьевна

• Милюкова, Ольга Юрьевна
• доктор физико-математических наук
• 2004

Оглавление диссертации доктор физико-математических наук Милюкова, Ольга Юрьевна

ВВЕДЕНИЕ

ГЛАВА1. ПАРАЛЛЕЛЬНЫЕ ВАРИАНТЫ НЕКОТОРЫХ ИТЕРАЦИОННЫХ МЕТОДОВ С ФАКТОРИЗОВАННОЙ МАТРИЦЕЙ ПРЕДОБУСЛОВЛИВАНИЯ ДЛЯ РЕШЕНИЯ ДВУМЕРНЫХ ЭЛЛИПТИЧЕСКИХ УРАВНЕНИЙ НА ОРТОГОНАЛЬНЫХ СЕТКАХ

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

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

2.Теоретическое исследование скорости сходимости параллельного варианта 1 метода MICCG(O) и параллельного варианта MAFCG

3.Параллельный вариант 2 метода MICCG(O) для решения эллиптических уравнений на равномерной ортогональной сетке

4. Результаты расчетов

§2.Параллельные варианты метода MICCG(O) для решения эллиптических уравнений на неравномерной ортогональной сетке

1.Теоретическое обоснование автоматического выбора итерационных параметров

2.Результаты расчетов

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

1.Разностные схемы для решения эллиптического уравнения на локально измельчающейся сетке

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

3. Параллельные варианты методов VICCG, VMICCG для решения эллиптических уравнения на локально измельчающихся сетках

4. Результаты численных расчетов 65 Выводы к главе

ГЛАВА2. ПАРАЛЛЕЛЬНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ С ФАКТОРИ-ЗОВАННЫМИ МАТРИЦАМИ ПРЕДОБУСЛОВЛИАНИЯ ДЛЯ РЕШЕНИЯ ДВУМЕРНЫХ ЭЛЛИПТИЧЕСКИХ УРАВНЕНИЙ НА ТРЕУГОЛЬНЫХ СЕТКАХ

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

1. Упорядочение узлов сетки DD01 и алгоритм параллельных вариантов методов VICCG и VMICCG

2. Теоретическое исследование скорости сходимости параллельного варианта метода VMICCG и выбор итерационных параметров для модельной задачи

3. Другие способы упорядочения узлов сетки и алгоритмы параллельных аналогов метода VMICCG

4. Результаты численных расчетов

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

1. Методы VICCG, VMICCG и их параллельные варианты для решения эллиптических уравнений на неструктурированной треугольной сетке

2. Результаты численных расчетов

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

1. Теоретическое обоснование автоматического выбора итерационных параметров

2. Результаты расчетов 106 Выводы к главе

ГЛАВАЗ. ПАРАЛЛЕЛЬНЫЕ ВАРИАНТЫ ПОПЕРЕМЕННО-ТРЕУГОЛЬ-ОГО МЕТОДА СОПРЯЖЕННЫХ ГРАДИЕНТОВ ДЛЯ РЕШЕНИЯ ДВУМЕРНЫХ И ТРЕХМЕРНЫХ ЭЛЛИПТИЧЕСКИХ УРАВНЕНИЙ

§1.Параллельные варианты попеременно-треугольного метода для решения двумерных эллиптических уравнений

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

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

3.Теоретическое исследование скорости сходимости параллельного варианта метода ПТМСГ для модельной задачи

4. Возможные обобщения

5. Результаты расчетов

§2. Параллельные варианты попеременно-треугольного метода для решения трехмерных эллиптических уравнений

1.Параллельный вариант 3 попеременно-треугольного метода для решения эллиптических уравнений

2. Параллельный вариант 4 попеременно-треугольного метода для решения эллиптических уравнений

3. Результаты расчетов 140 Выводы к главе

ГЛАВА 4. ПАРАЛЛЕЛЬНЫЙ ВАРИАНТ MICCG(O) ДЛЯ РЕШЕНИЯ ТРЕХМЕРНЫХ ЭЛЛИПТИЧЕСКИХ УРАВНЕНИЙ И ПРИМЕНЕНИЕ ПАРАЛЛЕЛЬНЫХ ВАРИАНТОВ MICCG(O) ДЛЯ РЕШЕНИЯ ЗАДАЧ ГИДРОДИНАМИКИ

§1.Параллельный вариант метода MICCG(O) для решения трехмерных эллиптических уравнений на ортогональной равномерной сетке

1.Матрица предобусловливания и алгоритм параллельного варианта метода MICCG(O)

2. Теоретического исследования скорости сходимости параллельного варианта MICCG(O) для решения трехмерных задач

3. Результаты расчетов

§2. Численное моделирование течения вязкой несжимаемой жидкости в кубической каверне

1. Квазигидродинамические уравнения и постановка задачи о течении жидкости в кубической каверне с подвижной верхней крышкой

2. Вычислительный алгоритм

3. Результаты расчетов

§3. Численное моделирование термокапиллярной конвекции в прямоугольной полости в условиях пониженной гравитации

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

2. Вычислительный алгоритм

3. Результаты расчетов 165 Выводы к главе

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

В последние десятилетия наблюдается бурное развитие вычислительной техники, создание высокопроизводительных вычислительных комплексов и систем, содержащих несколько сотен или даже тысяч процессоров с большим объемом оперативной памяти, высокой производительностью и большой скоростью обмена данными между процессорами. Так например создан Межведомственный Супер компьютерный Центр МВС 1000М [48], содержащий 768 процессоров ALpha 21264 с объемом оперативной на процессор 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-01753, 98-01-00155, 99-01-01215, 99-0790388, 01-01-00061, 02-01-00700, 02-07-90168), Российской Академией Наук (контракт N 10002-251 /-17/026-023/070403-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)</N), где N -число узлов сетки). Это достигается с помощью специального выбора итерационных параметров. В расчетах модельных задач наблюдался приемлемый рост числа итераций с ростом числа процессоров. Показана хорошая эффективность методов при решении модельной задачи на умеренном числе процессоров. С точки зрения скорости сходимости и эффективности метода PVMICCG наиболее удачным является использование DD03 упорядочения.

Для случая неструктурированной треугольной сетки и локально измельчающейся сетки в методах 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.

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

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

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

Список литературы диссертационного исследования доктор физико-математических наук Милюкова, Ольга Юрьевна, 2004 год

1. Воеводин В.В., Тыртышников Е.Е. Вычислительные процессы с теплицевыми матрицами //Москва: Наука. 1987. 320С.

2. Волчинская М.И., Четверушкин Б.Н. Об одном итерационном методе решения двумерных уравнений диффузии излучения // Жур. Вычисл. Матем. и Матем. Физ. 1977. Т.17. N 2. С.428-436.

3. Гильманов А.Н. Методы адаптивных сеток в задачах газовой динамики // Москва: Физматлит. 2000.

4. Граур И. А., Елизарова Т.Г., Косарев Л.В., Четверушкин Б.Н. Численное моделирование тепломассообмена в трехмерных кавернах // Математическое моделирование. 1994. Т.6. N 5. С.37-54.

5. Гуров Д.Б., Елизарова Т.Г., Шеретов Ю.В. Численное моделирование течений жидкости в каверне на основе квазигидродинамической системы уравнений// Матем. моделирование. 1996. Т.8. N 7. С.ЗЗ 44.

6. Гуськов С.Ю., Розанов В.Б.,Змитренко Н.В., Мищенко Т.В., Попов И.В., Тишкин

7. B.Ф. Численное моделирование мишеней типа "лазерный парник" для поглощенной энергии ~ ЮОДж. // М. Препринт ФИ АН. 1997. N 57. 28С.

8. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений // М.: Мир. 1984. ЗЗЗС.

9. Дуйсекулов А.Е., Елизарова Т.Г. Использование многопроцессорных вычислительных систем для реализации кинетически согласованных разностных схем газовой динамики // Математическое моделирование. 1990. Т.2. N 7. С. 139-147.

10. Елизарова Т.Г., Калачинская И.С., Ключникова А.В., Шеретов Ю.В. Использование квазигидродинамических уравнений для моделирования тепловой конвекции при малых числах Прандтля// Ж. вычисл. матем. и матем. физ. 1998. Т. 38. N 10.1. C.1732-1742.

11. Елизарова Т.Г., Калачинская И.С., Милюкова О.Ю. Влияние квазистатической компоненты микроускорения на режимы термокапилярных течений //в кн. Сборник трудов факультета ВМиК МГУ (в печати, принято к печати).

12. Елизарова Т.Г., Милюкова О.Ю. Численное моделирование течения вязкой несжимаемой жидкости в кубической каверне // Ж. вычисл. матем. и матем. физ. 2003. Т.43. N 3. С.453-466.

13. Елизарова Т.Г., Четверушкин Б.Н. Применение многопроцессорных транспьютерных систем для решения задач математической физики // Математическое моделирование. 1992. Т.4. N 11. С.75-100.

14. Елизарова Т.Г., Шеретов Ю.В. Теоретическое и численное исследование квазигазодинамических и квазигидродинамических уравнений// Ж. вычисл. матем. и матем. физ. 2001. Т.41. N 2. С.239 255.

15. Исаев С.А., Лучко Н.Н., Судаков А.Г., Сидорович Т.В. Численное моделирование ламинарного циркуляционного течения в квадратной каверне с подвижной границей при высоких числах Рейнольдса //Инж. физ. журнал. 2002. Т.75. N 1. С.54 60.

16. Исаев С.А., Лучко Н.Н., Судаков А.Г., и др. Численное моделирование ламинарного циркуляционного течения в кубической каверне с подвижной гранью //Инж. физ. журнал. 2002. Т.75. N 1. С.49 53.

17. Капорин И.Е. Оценки числа итераций методов типа сопряженных градиентов // в кн.: Актуальные вопросы прикладной математики и математического обеспечения ЭВМ/ Под ред. Шестопалова Ю.В.-М: Изд-во Моск. ун-та. 1990. С.112-113.

18. Капорин И.Е. Альтернативный подход к оценке числа итераций метода сопряженных градиентов // в кн.: Численные методы и програмное обеспечение/ Под ред. Кузнецова Ю.А.-М: ОВМАНСССР. 1990. С.55-72.

19. Капорин И.Е., Коньшин И.Н. Параллельное решение симметричных положительно-определенных систем на основе перекрывающегося разбиения на блоки // Журн. Вычисл. Матем. и Матем. Физ. 2001. Т.41. N 4. С.515-528.

20. Карамзин Ю.Н., Попов И.В., Поляков С.В. Разностные методы в задачах механики сплошной среды на треугольных и тетраидральных сетках // Матем. моделирование. 2003. Т.15. N 11. С.3-12.

21. Коновалов А. Н. Введение в вычислительные методы линейной алгебры // Новосибирск. В. О. "Наука", Сибирская издательская фирма. 1993.

22. Косефф Дж.Р., Стрит P.JI. О влиянии торцевых стенок на течение в каверне с движущейся крышкой // Теор. основы инж. расчетов. 1984. Т. 106. N 4. С.299 308.

23. Кучеров А.Б., Макаров М.М. Метод приближенной факторизации для решения разностных смешанных краевых задач / / Разностные методы математической физики. М.: Моск. Гос. ун. 1984. С.54-65.

24. Кучеров А. Б., Николаев Е. С. Попеременно-треугольный итерационный метод решения сеточных эллиптических уравнений в прямоугольнике // Ж. вычисл. матем. и матем. физ. 1976. Т.16. N 5. С.1164-1174.

25. Кучеров А. Б., Николаев Е. С. Попеременно-треугольный итерационный метод решения сеточных эллиптических уравнений в произвольной области // Ж. вычисл. матем. и матем. физ. 1977. Т.17. N 3. С.664-675.

26. Кучеров А. Б., Николаев Е. С. Параллельные алгоритмы итерационных методов с факторизованным оператором для решения эллиптических краевых задач // Дифференц. уравнения. 1984. Т.20. N 7. С. 1230-1236.

27. Лебо И.Г., Попов И.В., Розанов В.Б., Тишкин В.Ф. Численное моделирование теплового выравнивания и гидродинамической компенсации в мишенях типа "лазерный парник" // Квантовая электроника. 1995. Т.22. Т12. С.1257-1261.

28. Марчук Г.И. Методы вычислительной математики // М: Наука. 1980. 534С.

29. Милюкова О. Ю. Параллельный вариант обобщенного попеременно-треугольного метода для решения эллиптических уравнений // Ж. вычисл. матем. и матем. физ. 1998. Т.38. N 12. С.2002-2012.

30. Милюкова О. Ю. Параллельный итерационный метод с факторизованной матрицей предобусловливания для решения эллиптических уравнений // Дифференц. ур-ния. 2000. Т.36. N 7. С.953-962.

31. Милюкова О.Ю. Параллельные варианты некоторых итерационных методов с факторизованной матрицей предобусловливания. // Ж. вычисл. матем. и матем. физ. 2001. Т. 41. N 11. С.1619-1636.

32. Милюкова О. Ю. Параллельные варианты попеременно-треугольного метода для решения трехмерных эллиптических уравнений // Ж. вычисл. матем. и матем. физ.2002. Т.42. N 10. С.1529-1539.

33. Милюкова О.Ю. Параллельные итерационные методы с фактор изованной матрицей предобусловливания для решения дискретных эллиптических уравнений на неравномерной сетке // Математическое моделирование. 2003. Т.15. N 4. С.3-15.

34. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем // М.: Мир. 1991. 365С.

35. Попов И.В., Поляков С.В. Построение адаптивных нерегулярных треугольных сеток для двумерных многосвязных невыпуклых областей // Математ. моделирование. 2002. Т.14. N б. С.25-35.

36. Похилко В.И. О решении уравнения Навье-Стокса в кубической каверне // Препринт N 11. М.: ИММ РАН. 1994.

37. Сазонов В.В.,Беляев М.Ю.и др. Определение квазистатической составляющей микроускорения на станции Мир //Космические исследования. 2001.Т.39.N2. с.136-147.

38. Самарский А. А. Об одном экономичном алгоритме численного решения систем дифференциальных и алгебраических уравнений // Ж. вычисл. матем. и матем. физ. 1964. Т.4. N 3. С.580-585.

39. Самарский А. А. Теория разностных схем // М.:Наука. 1989. 614С.

40. Самарский А.А., Андреев В.Б. Разностные методы для эллиптических уравнений // М: Наук а. 1976. 352С.

41. Самарский А.А., Колдоба А.В., Повещенко Ю.А., Тишкин В.Ф., Фаворский А.П. Разностные схемы на нерегулярных сетках // Минск. 1996. 254С.

42. Самарский А. А., Николаев Е. С. Методы решения сеточных уравнений // М.: Наука. 1978. 589С.

43. Тхир А.В. Метод продвинутого фронта для построения неструктурированных сеток //в кн. Численные методы и приложения под ред. Ю.А. Кузнецова. Институт вычислительной математики РАН. 1995.

44. Тыртышников Е.Е. Параллельные методы для обобщенных теплицевых систем //Ж. вычисл. матем. и матем. физ. 1996. Т.36. N 6. С.5-19.

45. Фортов В.Е., Левин В.К., Савин Г.И., Забродин А.В. и др. Суперкомпьютер МВС 1000М и перспективы его применения // Информационно-аналитич. журнал Наука и пром-сть России. 2001. (55). N 11. С.49 - 52.

46. Четверушкин Б.Н. Об одном итерационном алгоритме решения разностных уравнений // Жур. Вычисл. Матем. и Матем. Физ. 1976. Т.16. N2. С.519-524.

47. Четверушкин Б.Н. Кинетически-согласованные схемы в газовой динамике // М.: Изд-во МГУ. 1999. 231С.

48. Четверушкин Б.Н., Н.Г. Чурбанова Н.Г. О применении принципа геометрического параллелизма для а— (3 итерационного алгоритма // Математическое моделирование.1991. Т.З. N 3. С.23-28.

49. Шеретов Ю.В. Квазигидродинамические уравнения как модель течений сжимаемой вязкой теплопроводной среды// Применение функц. анализа в теории приближений. Тверь: Тверской гос. ун-т. 1997. С.127-155.

50. Шеретов Ю.В. Математическое моделирование течения жидкости и газа на основе квазигазодинамических и квазигидродинамических уравнений // Тверь: Тверской гос. ун-т, 2000.

51. Anderson Е.С., Saad Y. Solving sparse triangular systems on parallel computers //Internat. J. High Speed Comput. 1989. Vol.1. P.73-9G.

52. Axelsson 0. A class of iterative methods for finite element equations //Comput. Meth. Appl. Mech. Engng. 1976. Vol.9. P. 123-137.

53. Axelsson 0. A Generalized SSOR Method // BIT. 1972. Vol.13. P.443-467.

54. Axelsson 0., Barker V.A. Finite Element Solution of Boundary Value Problems. Theory and Computations // Academic Press, New York. 1984. 432P.

55. Axelsson 0., Eijkhout V. Vectorizable preconditioners for elliptic difference equations in three spase dimensions // J. Comput. Appl. Math. 1989. Vol.27. N 1-2.P.299-321.

56. Axelsson 0., Lindskog G. On the eievalue distribution of class of preconditioning methods // Numer. Math. 1986. Vol.48. P.479-498.

57. Axelsson 0., Lindskog G. On the rate of convergence of the preconditioned conjugate gradient methods // Numer. Math. 1986. V.48. P.499-523.

58. Axelsson 0., Polinan B. On approximate factorization methods for block matrices suitable for vector and parallel processors // Linear Algebra AppL 1986. Vol.77. P.3-26.

59. D'Azevedo E.F., Forsyth F.A., Tang W.P. Ordering methods for preconditioned conjugate gradient methods applied to unstructured grid problems // SIAM J. Matrix Anal. Appl. 1992. Vol.13. P.944-961.

60. Bauer H.F. Stability and vibrational behaviour of cylindrical liquid layers in microgravity // Hydromechanics and heat/mass transfer in microgravity. Gordon and Breach Sci. Publ.1992. P. 197-201.

61. Beauwens R. Modified incomplete factorization strategies // in: 0. Axelsson, L. Kolotilina (Eds.), in:Preconditioned Conjugate Gradient Methods, Lectures Notes in Mathematics N 1457. Springer. Berlin. 1990. P.l-16.

62. Berger M.J., Oliger J. Adaptive mesh refinement for hyperbolic partial equations // Ibid. 1984. Vol.53. P.484-512.

63. Berryman H., Saltz J., Gropp W., Mirchandaney R. Krylov methods preconditioned with incompletely factored matrices on the CM-2 // J.Partial Distrib. Comput. 1990. Vol.8. P.186-190.

64. Bridson R., Tang W. A structural diagnosis of some 1С ordering // SIAM J. Sci. Comput. 2000. Vol.22. N5. P.1527-1532.

65. Cao Z.H., Xie J.C., Tang Z.M., Hu W.R. The influence of buoyancy of the onset of oscillatory convection in a half floating zone. Adv. Space Res. 1991. V.ll. N7. P.163-166.

66. Chan T.F., Goovaerts D. A note on the efficiency of domain decomposed incomplete factorizations // SIAM J. Sci. Statist. Comput. 1990. Vol.11. P.794-803.

67. Chan T.F., Resasco D. A framework for the analysis of domain decomposition preconditioners // SIAM J. Sci. Statist. Comput. 1990. Vol.11. P. 794-803.

68. Chen G., Roux B. Analytical solution and numerical simulation of thermocapillary convection in floating zones // Adv. Space Res. 1991. Vol. 11. N 7. P.151-162.

69. Chow E., Saad Y. Approximate inverse preconditioners via sparse-sparse iterations // SIAM J. Sci. Comput. 1998. Vol.19. P.995-1023.

70. Chow E., Vassilevski P.S. Myltilevel block factorizations in generalized hierarchical bases // Numer. Linear Algebra Appl. 2003. Vol.10. P. 105-127.

71. Doi S. On parallelism and convergence of incomplete LU factorizations // Appl. Numer. Math. 1991. Vol.7. N 5. P.417-436.

72. Domain decomposition methods for partial differential equations. Proc. of 1 st Int. Symp. // (Eds. R. Glowinsti et al.) SIAM. Philadelphia. 1988.

73. Dongarra J.J., Duff I.S., Sorensen D.C., van der Vorst H.A. Numerical Linear Algebra for High-Performance Computers // SIAM. Philadelphia. PA. 1998.

74. Dongarra J.J., Eijkhout V. Numerical linear algebra algorithms and software // J. of Сотр. Appl. Math. 2000. Vol.123. P.489-514.

75. Duff I.S., Meurant G.A. The effect of ordering on preconditioned conjugate gradients // BIT. 1989. Vol.29. P.635-657.

76. Duff I.S., van der Vorst H.A. Developments and trends in parallel solution of linear systems // Parallel Comput. 1999. Vol.25. P.1931-1970.

77. Dupont Т., Kendall R., and Rachford H.H., Jr. An approximate factorization procedure for solving self-adjoint elliptic difference equations // SIAM J. Numer. Anal. 1968. Vol.5. P.559-573.

78. Ehrhich L.W. An ad hoc SOR method // J.Comput.phys. 1981. Vol.44. P.31-45.

79. Eijkhout V. Analysis of parallel incomplete point factorizations // Lin. Alg. Appl. 1991. Vol.154-156. P.723-740.

80. Evans D.J. Parallel SOR iterative methods // Parallel Comput. 1984. Vol.1. P.3-18.

81. Fedoseyev A.I. A regularization approach to solving the Navier-Stokes equations for problems with boundary layer// Comput. Fluid Dynamic J. 2001. V.9. Special number (http://uahtitan.uah.edu/alex/).

82. Golovin A.A., Nepomnyashchy A.A., Pismen L.M. Interaction between short-scale „ Marangoni convection and long-scale deformational instability // Physics Fluids. 1994.1. Vol. 6. N 1. P.34-48.

83. Grote M., Huckle T. Parallel preconditioning with sparse approximate inverses // SIAM J. Sci. Comput. 1997. Vol.18. P.838-853.

84. Gustafsson I. A class of first order factorization methods // BIT. 1978. Vol.18. P.142-156.

85. Hackbush W. Multi-Grid Methods and Applications // Springer. New York. 1985.

86. Hamaclier H., BlumelU., Jild R. Spacelab's Microgravity Environment A Characterization Based on D-l and D-2 Data.// Ninth European Symposium "Gravity-Dependent Phenomena in Physical Sciences. Berlin. Germany, 2-5 May 1995. Abstacts.

87. Hendrickson В., Leland R. A Multilevel Algorithm for Partitioning Graphs // Supercom-puting'95 Proceedings. San Diego, CA,1995.

88. Johnson O.G., Micheli C.A., Paul G. Polynomial preconditioning for Conjugate Gradient calculations // SIAM J. Numer. Anal. 1983. Vol.20. P.363-367.

89. Jones M.T., Plassmann P.E. The efficient parallel iterative solution of large sparse linear systems // in: A.George, J.R.Gilbert, J.W.H.Liu (Eds.), Graph Theory and Sparse Matrix Computations. IMA. Vol.56. Springer. Berlin. 1994.

90. Kajdan D., Shtilman L., Golovin A.A., Pisinen L.M. Nonlinear Waves and Turbulence in Marangoni Convection // Ninth European Symposium "Gravity-Dependent Phenomena in Physical Sciences. Berlin. Germany. 2-5 May 1995. Abstacts.

91. Kaporin I.E. High quality preconditioning of a general symmetric positive definite matrix based on its UTU -f UTR + RT^-decomposition // Numer. Linear Algebra and Appl. 1998. Vol.5. N 5. P.484-509.

92. Kaporin I.E. Explicitly preconditioned conjugate gradient method for the solution of nonsymmetric linear systems // Int. J. Computer Math. 1992. Vol.40. P.169-187.

93. Kaporin I.E. New convergence results and preconditioning strategies for the conjugate gradient method // Numer. Linear Algebra Appl. 1994. Vol.1. P.179-210.

94. Kershaw D. The Incomplete Choleski-Conjugate Gradient Method for the Iterative Solution of Systems of Linear Equations // J. Coinp. Phys. 1978. Vol.26 P.43-65.

95. Krasnov S.A., Tyrtyshnikov E.E. Vectorized algorithms and systolic arrays for Toeplitz systems of equations // Sov. J. Numer. Anal. Math. Modelling. 1987. Vol.2. N2. P.99-111.

96. Kolotilina L.Yu., Yeremin A.Yu. Factorized sparse approximate inverse preconditioning I, Theory // SIAM J. Matrix Anal. Appl. 1993. Vol.14. P.45-58.

97. Kutcherov A.B., Makarov M.M. An Approximate Factorization Method for Solving Discrete Elliptic Problems on Stretched Domains // J. of Numer.Linear Algebra with Appl. 1992. Vol. 1. P. 1-26.

98. Magolu inonda Made M. Taking advantage of potentialities of dynamically modified block incomplete factorizations // SIAM J. Sci. Comput. 1998. Vol.19. P.1083-1108.

99. Magolu monga Made M., van der Vorst H. Parallel incomplete factorization with pseudo-overlapped subdomains // Parallel Comput. 2001. Vol.27. P.989-1008.

100. Manteuffel Т. An Incomplete Factorization Technique for Positive Definite Linear Systems // Math. Сотр. 1980. Vol.34. P.473-497.

101. Meseguer J., Perales J.M. Non-steady Phenomena in the Vibration of Viscous Cylindrical Long Liquid Bridges // Microgravity Sci. and Technology. 1992. Vol.5. P.69-72.

102. Meurant G. Numerical experiments for the preconditioned Conjugate Gradient method on the CRAY X-MP/2 // Technical Report LBL-18023, University of California. Berkeley. CA. 1984.

103. Meurant G., The Conjugate Gradient method on vector and parallel supercomputers // Technical Report CTAC-89, University of Brisbane, July, 1989.

104. Meijerink J.A., van der Vorst H.A. An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix // Math. Comput. 1977. Vol.31. N 137. P. 148-162.

105. Milyukova 0. Yu. Parallel approximate factorization method for solving discreate elliptic equations // Parallel Comput. 2001. 27. P.1365-1379.

106. Milyukova O.Yu., Parallel Version of Approximate Factorization Method For Solving 2D and 3D Elliptic Eequations // J. of Comput. Meth. in Scien. and Engin. 2002. Vol.2. No 1-2. P. 195-200.

107. Napolitano L.G., Monti R., Russo G. Marangoni Convection in One and Two Liquid Floating Zones // Natur Wissenschaften. 1986. Vol. 73. P.352-355.

108. Nodera Т., Tsuno N. The Parallelization of Incomplete LU Factorization on AP1000 // Euro-Par'98 Parallel Processing, Pritchard D. and Reeve J., Eds. Berlin: Springer-Verlag. 1998. P.788-792.

109. Notay Y. An efficient parallel discrete PDE solver // Parallel Comput. 1995. Vol.21. P. 1725-1748.

110. Notay Y. DRIC: a dinamic version of the RIC method // Journ. Num. Lin. Alg. with Appl. 1994. Vol.1. P.511-533.

111. Oosterlee C.W., Washio T. An evaluation of parallel multigrid as a solver and a preconditioner for singularly perturbed problems // SIAM J. Sci. Statist. Comput. 1991. Vol.19. P.87-110.

112. Parallel Computational Fluid Dynamics (Moscow, Russia, May 13-15, 2003). Edited by B.Chetverushkin, A. Ecer, J. Periaux and N. Satofuka-Assistant Editor: Pat Fox, Elsevier Science B.V., Amsterdam. 2004. 542 P.

113. Pascal J.F., Paul-Louis G. Mesh Generation application to finite elements // Oxford: Hermes Science Publishing. 2000.

114. Pervaitz M.M., Baron J.R. Spatiotemporal adaptation algorithm for two dimensional reacting flows // AIAA. 1989. Vol.27. N 10. P.1368-1376.

115. Van der Ploeg A., Botta E.F.F., Wubs F.W. Nested grids ILU-factorization(NGILU) // J. Сотр. Appl. Math. 1996. Vol.66. P.515-526.

116. Radicati di Brozolo G., Robert Y. Parallel conjugate gradient-like algorithms for solving sparse nonsymmetric linear systems on a vector multiprocessor // Parallel Coinput.1989. Vol. 11. N 2. P.223-239.

117. Ramachandran N., Winter C.A. Effects of g-Jitter and Marangoni Convection on Float Zones // Journal of Spacecraft and Rockets. 1992. Vol. 29. N 4. P.514-522.

118. Rothberg E. Exploring the traeofF between imbalance and separator size in nested dissection ordering //Tecnical Report Unnumbered, Silicon Graphics Inc. 1996.

119. Saad Y. Iterative methods for sparse linear systems. PWS Publishing Co., Int. Tompson Publ. Co. 1995. 447P.

120. Saad Y. Krylov subspace methods on supercomputers // SIAM J. Sci. Statist. Comput. 1989. Vol.10. P.1200-1232.

121. Saad Y., van der Vorst H. Iterative solution of linear systems in 20th centure // Jorn. Сотр. and Appl. Math. 2000. Vol.123. P.l-33.

122. ScaLAPACK user's guide/Eds. L.S. Blackford et al. SIAM, Philadelphia, 1997.

123. Seager M.K. Parallelizing conjugate gradient for the CRAYX-MP // Parallel Comput. 1986. Vol.3. P.35-47.

124. Stotland S.A., Ortega J.M. Ordering for parallel conjugate gradient preconditioners // SIAM J. Sci. Comput. 1997. Vol.18. N 3. P.854-868.

125. Tan K.H. Local coupling in domain decomposition // Ph.D.Thesis, Utrecht University, Utrecht. The Netherlands. 1995.

126. Tang W.P. Generalized Schwarz splitting // SIAM J. Sci. Statist. Comput. 1992. Vol.13. P.573-595.

127. Trapeznikova M.A., Churbanova N.G. Simulation of Multi-Phase Fluid Filtration on Parallel Computers with Distributed Memory //in Computational Fluid Dynamics'98, Proceeding, 7-11 September 1998. Athens. Greece. Vol.1, part 2. P.929-934.

128. Tyrtyshnikov E.E. Constructive approach to develop vectorized and fast algorithms for special-type matrices // Sov. J. Nuiner. Anal. Math. Modelling. 1988. Vol.3. N5. P.409-430.

129. Tyrtyshnikov E.E. New approaches to deriving parallel algorithms // Parallel Comput.1990. Vol.15. P.261-265.

130. Van der Vorst H.A. Large tridiagonal and block tridiagonal linear systems on vector and parallel computers // Parallel Comput. 1987. Vol.5. P.45-54.

131. Van der Vorst H.A. High performance preconditioning // SIAM J. Sci. Stat. Comput. 1989. Vol.10. N 6. P. 1174-1185.

132. Van der Vorst H.A. IICG and related method for 3-D problems on vector computers // in: D. Truhlar (Ed.) Workshop oon Practical Iterative Methods for Large Scale Computations, Minneaopolis, MN, October 23-25, 1988. Comput.Phys. Comm. 1989. Vol.53.

133. Van der Vorst H.A. Parallel iterative solution methods for linear systems arising from discretized PDE's // In: Special course on parallel computing in CFD, AGARD-R-807, AGARD, Neuily-sur-Seine, France.-Workshop Lecture Notes, 1995.-39P.

134. Washio Т., Hayami K. Parallel block preconditioning based on SSOR and MULU //Numer.Linear Algebra Appl. 1991. Vol.1. P.533-553.