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

На правах рукописи

Милюкова Ольга Юрьевна

ПАРАЛЛЕЛЬНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ

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

01.01.07 - вычислительная математика

Автореферат

Диссертации на соискание ученой степени доктора физико-математических наук

Москва -2004

Работа выполнена в Институте математического моделирования РАН

Официальные оппоненты:

член-корреспондент РАН

доктор физико-математических наук,

профессор Забродин А.В.

доктор физико-математических наук, профессор Исаев С. А.

доктор физико-математических наук, профессор Тыртышников Е.Е.

Ведущая организация

Институт автоматизации проектирования РАН

2004 г. в

Защита состоится

на заседании диссертационного совета Д 002.058.01 при Институте математического моделирования РАН по адресу 125047, Москва, Миусская площадь, дом 4а.

С диссертацией можно ознакомиться в библиотеке ИММ РАН.

Автореферат разослан "7,4" ,ллх> - А. 2004 г.

Ученый секретарь диссертационного совета доктор физико-математических наук

I Л/^В^"

Н.В. Змитренко

Общая характеристика работы

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

Адаптация алгоритмов решения нестационарных задач с применением явных схем для аппроксимации дифференциальных уравнении в настоящее время успешно решена в работах Четверушкина Б.Н., Елизаровой Т.Г., Дуйсекулова А.Е. в 1990 году. Использование неявных схем для аппроксимации дифференциальных уравнений резко сократит время расчета многомерных задач, однако связано с необходимостью решения систем линейных уравнений с сильно разреженной и как правило плохо обусловленной матрицей. К необходимости решения систем линейных уравнений с сильно разреженной и плохо обусловленной матрицей мы приходим также при решении дискретных аналогов двумерных и трехмерных краевых задач для эллиптических уравнений второго порядка. Следует отметить, что при численном решении многих нестационарных задач математической физики основная часть вычислительных затрат приходится именно на решение краевых задач для двумерных или трехмерных эллиптических уравнений.

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

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

(1)

где Ха > с > 0, а = 1, ...,т - непрерывные или кусочно непрерывные функции, т - размерность пространства, х = (х1,х2) для двумерных по пространству задач и х = (х,, х, х) дня трехмерных задач. Область О -прямоугольная, или двумерная односвязная, или прямоугольный параллелишшед. В результате аппроксимации краевой задачи для эллиптического уравнения получим систему линейных алгебраических уравнений вида

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

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

- ос НАЦИОНАЛЬНАЯ | вс.пЛН°ТЕКА

^ д ди .

матрицей предобусловливания. Часто используются метод с предобусловливанием неполного разложения Холепкого без заполнения (ICCG(O)), предложенный Мейе-рннком (Meijeiink J.A.) и ван дер Ворстом (van der Voist H.A.) в 1977г., его модифицированный вариант (MICCG(O)), предложенный Густафссоном (Gustafsson I.) в 1978г. и Дюпоном (Dupont Т.), Кендаллом (Kendall R.), Решфордом (Rachford Н.Н.) в 1968г., метод приближенной факторизации (MAFCG), предложенный Кучеровым А.Б. и Макаровым М.М. в 1984г., обобщенный метод симметричной верхней релаксации SSORCG, предложенный Акселссоном (Axebson О.) в 1972г., метод неполного разложения Холецкого с релаксацией (RICCG), предложенный Акселссоном (Axelsson О.) и Линдскогом (Lindskog G.) в 1986г. и его различные модификации , попеременно-треугольный метод (ПТМСГ), предложенный А.А. Самарским в 1964г.

Во всех перечисленных выше методах матрица предобусловливания имеет вид В = LDLT, где L - нижнетреугольная матрица, D - диагональная матрица. Обращение матрицы предобусловливания происходит в два этапа: LW* = — /, DLTvik — ©*, где ук - приближенное решение уравнения (2) на k-той итерация.

Распараллеливание алгоритмов методов сопряженных градиентов с факторизо-ванным предобусловливателем с использованием подхода, называемого декомпозицией области, сталкивается с рядом трудностей, связанных прежде всего с рекурсивным характером вычислений при обращении матрицы предобусловливания. Для преодоления этой трудности используют блочную технику или стратегию переупорядочения узлов сетки. Параллелизацией блочных методов занимаются Капорин И.Б., Коныпин И.Н., Роберт (Robert Y.), Радикати (Radicati di Brozolo G.), Акселссон и ряд других авторов. Стратегии переупорядочения узлов сетки посвящены работы Даффа (Duff I.S.), Мюрана (Meurant G.A.), Ортеги (Ortega J.), ван дер Ворста, Дои (Doi S.), Но-тея (Notay Y.). В работах последних трех авторов используются упорядочения узлов сетки, связанные с разбиением области расчета, то есть упорядочения типа Domain Decomposition ordering (DDO).

Следует отметить, что в настоящее время используются и другие эффективные методы, например методы верхней релаксации, локальной релаксации с использованием красно-черного упорядочения, параллельный алгоритм, предложенный Б. Н. Четверушкиным и Н.Г. Чурбановой в 1991г.

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

Целью настоящей работы является создание параллельных аналогов итерационных методов сопряженных градиентов с факторизованной матрицей предобусловли-

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

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

Научная новизна работы состоит в том, что благодаря использованию стратегии упорядочения узлов сетки созданы параллельные аналоги метода сопряженных градиентов с предобусловливанием MIC, ПТМ (точечные методы) для решения краевых задач для эллиптических уравнений на ортогональной равномерной и неравномерной сетках в области расчета, являющейся прямоугольником или прямоугольным параллелипипедом для произвольного числа процессоров; сконструированы параллельные аналоги вариантов ICCG, MICCG (назовем их VICCG, VMICCG) [Ортега Дж. Введение в параллельные и векторные методы решения линейных систем // М.: Мир. 1991. 365С , добавление Капорина И.Б.], в которых матрица предобусловлива-ния имеет вид

B = (D-l+A~)D(D-l+(A-)T), (3)

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

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

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

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

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

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

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

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

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

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

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

СТРУКТУРА ДИССЕРТАЦИИ. Диссертация состоит из 4 глав, введения, заключения, списка литературы и приложений. Список литературы содержит 150 работ. Объем диссертации 219 страниц.

НА ЗАЩИТУ ВЫНОСЯТСЯ

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

2.Параллельные варианты метода MICCG(O) с двумя способами упорядочения

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

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

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

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

АППРОБАЦИЯ РАБОТЫ. Результаты диссертации докладывались и обсуждались на VI Всероссийской конференции РТА "Транспьютерные системы и их применение" (г. Домодедово, октябрь 1996г.), на международной конференции Euro-Par'98: "Parallel Processing" (Великобритания, г. Саутгемптон, сентябрь 1998 г.), на 2 международной конференции "Modern Trends in Computational Physics" (г. Дубна, июль 2001г.), на Всероссйском съезде по теоретической и прикладной механике (г.Пермь, август 2001г.), на 15 международной конференции "Parallel Computational Fluid Dynamics" (г. Москва, май 2003г.) (2 доклада), на семинаре математического отделения РФЯЦ-ВНИИЭФ (г. Саров, февраль 2003г.), научном семинаре под руководством члена-корреспондента РАН Б.Н. Четверушкина в Институте математического моделирования РАН (г. Москва, февраль 2004г.), научном семинаре под руководством профессора Е.Е. Тыртышникова в Институте вычислительной математики РАН (г. Москва, апрель 2004г.), научном семинаре им. К.И. Бабенко под руководством члена-корреспондента РАН А.В. Забродина в Институте прикладной математики им. М.В. Келдыша РАН (г. Москва, апрель 2004г.).

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

Содержание работы

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

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

При использовании для аппроксимации уравнения (1) ортогональной равномерной или неравномерной сетки матрица А- пятидиагональная. Построение параллельных методов и теоретическое исследование их скорости сходимости проводится на

примере задач с граничными условиями Дирихле. При стандартном упорядочении неизвестных уравнение (2) может быть записано в виде

[Ау]{ = -ад,-! - ку^л + еда - о^цу*., - = /{, г € и, (4)

где N = N1-l- число расчетных точек в направлении ц. Предполагается, что

\ <Ч>

О в остальных случаях,

Ч г>,

(5)

если 1 < * < ' 0 в остальных случаях,

и-сц-к- <К+1 - >0, »6 и, ы = {£,» = Щи - 1) +л,1 < и < ЛГа - 1,а = 1,2},

Ы2 — 1 - число узлов сети в направлении х2. Здесь и далее предполагается, что компоненты любой сеточной функции, которые не определены, должны быть заменены нулем.

Как известно, в методах МЮСО(О), МАРСО, ЮСО(О) в случае, когда матрица Л задается в виде (4), матрица предобусловливания имеет вид В = (£)~1 + +

(•А~)т):, элементы диагональной матрицы В в методах М1ССО(0), МАБСО определяются из УСЛОВИИ М + АЛм = Ве, в котором БА - диагональная часть матрицы А, (Лу),- = (гу{, где для достаточно гладких коэффициентов дифференциального уравнения а = в методе М1ССО(0) и а = 0 в методе МАБСО, Л - шаг равномерной ортогональной сетки в обоих пространственных направлениях. В методе ¡ССО(О) элементы диагональной матрицы В определяются из условия совпадения диагональных элементов матриц Л и В. Алгоритм предобусловленного метода сопряженных градиентов имеет вид

(б)

где у* приближенное решение уравнения (2) на к-той итерации. Доказано, что для достаточно гладких коэффициентов дифференциального уравнения методы МЮСО(О), МАБСО требуют для сходимости 0(1п(2/е)у^39л) итераций, где Ы- число узлов сетки по одному пространственному направлению, е - требуемая относительная точность.

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

_а)___б)_

2

1

О

U 6 з U 6 3 L

2 4 1 2 4 1 2

7 8 5 7 8 5 7

L 6 3 U.6 3 U

2 4 1 2 4 1 2

7 8 5 7 8 5 7

L 6 3 L 6 3 L

2

1

О

U t 2 6 J t 4 2 з L 1 2

Г I 7 6 n i 8 7 з Г 5 7

L t 6 J"t 3 L

Рис. 1. Разбиение области расчета на р — pt * р2 подобластей и порядок следования узлов сетки в параллельных методах: a)Domain Decomposition ordering 1 (DDO1), б)Domain Decomposition ordering 2 (DDO2) (p1 = p2 = 3).

Для разбиения, изображенного на рис. 1 а), используется упорядочение узлов сетки Domain Decomposition ordering 1 (DDOl), вводится множество узлов разделителей. При упорядочении DDO1 сначала идут узлы сетки, не принадлежащие множеству разделителей, причем в том порядке, который был до переупорядочения. Затем следуют узлы разделителей в рассматриваемом случае в следующем порядке: все узлы, расположенные в точках 4, затем в точках 5, далее на всех линиях 6,7 и наконец в точках 8.

Для разбиения, изображенного на рис. 1 б), вводится упорядочение узлов сетки Domain Decomposition ordering 2 (DDO2), при котором сначала идут все узлы сетки, расположенные в точках 1, затем на всех линиях 2, 3, далее узлы, являющиеся внутренними точками в подобластях, затем узлы, расположенные в точках 4,5, на всех линиях 6,7, в точках 8. Порядок следования узлов сетки внутри подобластей указан стрелками на рис. 1 а), б).

В методе PMICCG1 (параллельном варианте MICCG(O) с DDO1 упорядочением) и в параллельном варианте MAFCG матрица предобусловливания

где

~<4Vi-1 - bi!/i_J?> если * £ шо,

О, если i € o»i,

—a.l/i-1, если i 6 ojj,

-iij/i-}?, если i e u>3,

-aiVi-i - Oi+iVi+ь если t 6 и>4,

-bVi-N ~ h+NVi+N' если * e ws,

-a,y,-i - a;+il/.+i - jj, ecjmi €

-biVi-j? - bi+NVi+N ~ <bVi-1. если i 6 <o7, -a,Vi-i - 6iVi_57 - Oi+iy.+i - h+кУц-jr. если ' € w«»

(7)

а в методе PMICCG2 (параллельном варианте MICCG(O) с DD02 упорядочением)

-ан^К-н», - ^+1,лгУ1+И1,37, если t € u>0,

О, если » 6

—1Oi+i,y¿+mi, если i 6 Wji

-b¿+í,SV¡-H»,J7. если * € wSl

~ Oi+iVi+i, если i €

-kyi-T7-bi+j¡yi+y, если fe oíSi

-Oíy¡_i - Oí+iVí+i - bi+hj}yi+míjj, если» e u<¡,

-b¿y¡JÑ ~ k+Wi+Ñ ~ a¡+liV¡+n41 если i € <^7.

(8)

-OiVi-1 - b¡y¿_j7 - a<+1y1+1 - Ь{+цу{+л, если i 6 u>>,

где

для четных ka, для нечетных

—1 для четных ka, для нечетных ка,

к1 и к, - номера столбца и строки в массиве подобластей (ка = 0,1, ...,ра—1), а = 1,2. Здесь и далее ыр- множества узлов сетки на всех линиях с номером /3 (см рис. 1 а) и рис. 16)), либо во всех точках с номером 0, ыо-множество внутренних узлов всех подобластей.

В параллельных вариантах методов М1ССО(0), МАБСО обращение матрицы пре-добусловливания теперь легко распараллеливается: все процессоры начнут вычисления одновременно с вычисления значений то* в точках 1.

Диагональная матрица Б в параллельных вариантах методов М1ССО(0), МАБСО определяется из условия:

Ае + GDAe = Be, (Gy)¡ = сгда.

(9)

Бели в прямоугольной области расчета задана равномерная ортогональная сетка с шагом к по обоим пространственным направлениям, то параметры о1 определяются следующим образом

Сr. = J + если t € о>0 для /? = 1,2,3,4,5, ' \ (oh1 в остальных случаях,

(10)

где в методах РМ1СС01, РМ1ССС2 & > 0, & > 0 для = 1,2,3,4,5, & > 0, в

параллельном варианте МАБСО ¿)>0, {о = {/9 = 0 для 1 < р < 5. Введение = О(к) на линиях 2,3 и в точках 1,4,5 необходимо для сохранения характера асимптотической зависимости числа итераций от числа узлов сетки такого же, как в методах МЮСО(О), МАБСО при стандартном упорядочении узлов сетки.

В методах РМ1СС01, РМ1СС02 (р, (о определяются из условия минимума теоретических оценок числа итераций этих методов для модельной задачи - задачи Дирихле для уравнения Пуассона в единичном квадрате, полученных в диссертации, и вычисляются например следующим образом:

При этом оптимальная оценка числа итераций метода РМ1СС01 для модельной задачи имеет вид

п > по и 0.51п(2/е)^2[1 + жтах(р(р1)1у>(р2))/8][1 + !/(»*)],

где <р(ра) = Ра для четных ро, <p(j>a) = Ра - 1 /р* для нечетных ра, у?(р„) -монотонно возрастающая функция, <р(ра) ~ ра для достаточно больших ра, а = 1,2. Оптимальная оценка числа итераций метода PMICCG2 для модельной задачи, полученная в диссертации имеет вид

п > По « 0.

где ф(ра) = ра при ра кратном 4, ф{ра) =ра— 4/ра при ра четном, но не кратном 4, ф(ра) = ра + {ра ± 2)/р£ при ра нечетном. Знак "+" соответствует случаю (р0 —1)/2 - нечетное, знак " -случаю (ра — 1)/2 - четное. ф{ра) монотонно возрастает при Ра ^ 2, Ф(ра) ~ Ра Ш достаточно больших ра, а ~ 1,2.

В случае решения задачи Дирихле для уравнения (1) в единичном квадрате на равномерной ортогональной сетке зададим теперь <т; следующим образом

{£0Аа, если » € шо и о>в и а>7 и и», ,..„..

если » € и иа)2 и «$иш4иа>Б,$1 > 0, * '

где ¿о > 0. Обозначим Хд-о.бд) ~ аппроксимацию коэффициента в точке х = — 0.5)А,7}А), аХй¿,-0.5 ~ аппроксимацию коэффициента хг в точке х = (л А, (Уг—0.5)Л), где п = К» - + 1, Л = > - Щ;': - 1), К» - \)(Щ - челая часть от (» - 1)1 N.

Заметим, что

- _ ¿1 I _ Л -о» - _ Хд-О .»А +0 5 А Хй»»-О» А+0Л

— . (13)

Доказана

Теорема 1. Пусть коэффициенты уравнения (4) заданы в (5), (13), причем выполнены условия

О <ci<xa<c2, для а = 1,2,

Xji-0.S,n *)" Xf, ji-o.5 _ ,

-1 . -,"» —

Xj,+O.BA + Xji J3+0.5

< ¡ioh, если i 6 ü>o,

где fto не зависит от h, ci = const, cj = const. Тогда итерационные методы PMICCGl, PMICCG2 с итерационными параметрами, заданными в (12), требуют для сходимости при фиксированных р\ ирг п > по = 0(1д(2/е)л/77ь) итераций, при-чем для достаточно большого max(pi,pj) верио по =

Заметим, что теорема 1 справедлива также в случае произвольной прямоугольной области расчета.

В параллельном варианте MAFCG можно использовать

{г = 1.5*, 6 = 6 = U = ^ = 0.75тг, = & = 0, /3 = 1,2,3,4,5.

В диссертации доказано, что для достаточно гладких коэффициентов xi, Xi параллельный вариант MAFCG с итерационными параметрами (12), причем (о = 0, при фиксированных pi и р2 требует для сходимости 0(1а(2/е)\/7Ул) итераций и 0(\n(2/e)y/Nh4/p) итераций для достаточно больших p\=pi = \fp-

Параллельная реализация предложенных в диссертации методов для двумерных задач на ортогональной сетке подробно изложена в работах [2,3,4,10].

Расчеты различных модельных задач показали, что для достаточно гладких \а число итераций в методах PMICCGl, PMICCG2, параллельном варианте MAFCG примерно пропорционально i/Щ, как в методах MICCG(O), MAFCG, наблюдается

приемлемый рост числа итераций с ростом числа процессоров. Заметим, что использование параметров (10), (11) в расчетах модельных задач с переменными коэффициентами, а также в прямоугольной области расчета приводит к вполне удовлетворительному результату. Результаты расчетов модельных задач приведены в работах автора [3,4,10,11].

В частности при решении модельной задачи среднее по

Nh значение коэффициента возрастания числа итераций с ростом числа процессоров по сравнению с числом итераций в методе MICCG(O) со стандартным упорядочением узлов сетки (расчеты на одном процессоре) для метода PMICCG1 было 1.33,1.49,1.60,1.72 при/) = 4,9,16,25, для PMICCG2 было 0.93,1.34,1.15,1.50,1.21,1.35 при р = 4,9,16,25,36,64. Таким образом число итераций в методе PMICCG2 растет медленнее с ростом числа процессоров, особенно при четных p1 и р2, что согласуется с выводами теоретического исследования, однако алгоритм метода сложнее, чем алгоритм метода PMICCG1. Среднее по Nh значение коэффициента возрастания числа итераций с ростом числа процессоров в параллельном варианте MAFCG по сравнению с числом итераций в методе MAFCG со стандартным упорядочением узлов сетки (расчеты на одном процессоре) было 1.17, 1.25, 1.31, 1.39, 1.57, 1.66, 1.91 соответственно при р = 4,9,16,25,64,100,256. При решении модельной задачи параллельным вариантом ICCG(0) с DDO1 упорядочением, который строится аналогично, число итераций возрастало не более, чем на 7%, при р < 64 и было примерно пропорционально Nh.

Расчеты модельной задачи на 32-х процессорной станции Par sy tec С С продемонстрировали хорошую эффективность предложенных параллельных вариантов методов. Эффективность на 4-25 процессорах (pt = р2) метода PMICCG1 была 66%-49%, метода PMICCG2 - 95% - 55%, параллельного варианта MAFCG - 86%-67%, параллельного варианта ICCG(0) - 86%- 88%.

Заметим, что аналогичным образом строятся параллельные варианты методов MICCG(O), MAFCG для решения задачи Неймана для уравнения (1).

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

Однако расчеты анизотропных задач параллельными вариантами методов MAFCG, ICCG(0) показали, что при таком разбиении квадратной области расчета число итераций может быстро расти с ростом числа процессоров. Расчеты показали, что в этом случае с точки зрения скорости роста числа итераций может оказаться целесообразным производить разбиение области расчета только в направлении переменной Х2 при Xl » XI-

В случае слабо неравномерной сетки в методах PMICCG1, PMICCG2 параметры tri можно вычислять по формулам (10), (11), однако использовать Ла = S/Ni/Ni„ где S - площадь прямоугольной области расчета. Для сильно неравномерной сетки такой подход приводит к сильному росту числа итераций с ростом числа процессоров. Во втором параграфе главы 1 предложены способы автоматического выбора параметров в методах PMICCG1, PMICCG2, MICCG(O) для решения двумерных эллиптических уравнений с граничными условиями Дирихле на сильно неравномерной сетке. Будем вычислять (Tj по формуле [6]

где для метода PMICCG1

Л =

О,

*/i+o sjJbJJ/hJ11+1+xjl1j2+o

если t 6 если » 6 utj,

xA-o.^/Ч'.+й+оZa'A+^U+o' еслк,6ц"

Xj'i -0 ffii +0 SjA'

Xn jj+o 5%!

2 > 2

Ja-0

*A-o iJ^Vb/i -о

X,'1+o sjjbjj/bj'i+l+zj'uj+o 5bji/hjJ,+i

если » € u>4,

если » G u>5,

в остальных случаях

Здесь и далее Л" = (я«),. - (ха)„.и = О 5(Л°+1 + Л" ), в = 1,2. Для РШССС2 формула для вычисления р, выглядит аналогично Следует отметить, что в случае неравномерной сетки

(14)

= SÎ.-0Ш4&К, ~Ь> = с, = с,1 + с?,

где с,1 = xh-osjXAi

Вещественное число а > 0 определяется из условия минимума теоретической оценки числа итерадий- а — l/CV^i — bj — 1), где ¿i = max,, max,,.. mar,, ¿2 = maXa тахЛ_в maiJa а»^, - решения трехточечных задач

+ СХЛ - = с.7(р. + 1).

(15)

+ сУпМ ~ = С,7(Р. + 1).

+ ~ 0.+1Ч+1Л = &с.7(р. + 1), -Цл-1 + - = + 1).

где = шах(1 — 0), уа = 1,2,..., — 1, а = 1,2, » = — 1) Таким образом для вычисления ах сначала решаются системы трехточечных уравнений (15), затем

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

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

вычисляются bj, b2

a

использовать методы "VTCCG, VMICCG - варианты методов ICCG(O), MAFCG (или MICCG(O) без возмущения, когда <г< = 0) с матрицей предобусловливания, имеющей вид (3), и конструируются параллельные аналоги [12] этих методов. Предполагается, что число уровней в сетке невелико (3-8 уровней). Заметим, что если матрица предобусловливания имеет вид (3), то можно использовать прием Айзенштата [Ортега Дж. Введение в параллельные и векторные методы решения линейных систем // М.: Мир. 1991. 365С] с целью удешевить каждую итерацию.

Разбиение области в вертикальном направлении производится по линиями х3 = const, проходящим строго по границам ячеек (если это возможно). Разбиение каждого получившегося слоя в горизонтальном направлении происходит по линиям х, = const. Разбиение области расчета происходит с учетом требования приблизительно равного числа узлов в каждой подобласти. На рис.2а) схематически изображено разбиение квадратной области расчета на 9 подобластей в случае сетки, локально измельчающейся к центру области. Будем использовать упорядочение узлов сетки DDO1, причем на разделителях, состоящих из узлов сеткиз точках 4,5,8 и на линиях 6, 7, установим следующий порядок следования узлов: все узлы, расположенные во всех точках 4 и на всех линиях а (см. рис. 2 6)), затем узлы во всех точках 5 и на всех линиях Ь, далее все узлы на всех линиях с.

6 2 4 3 6 1 2 4 3 1 2

7 2 3 5 7 8 3 6 4 12 4 5 7 5 2

7 8 6 5 7 8 3 6 15 7 3

Рис. 2. а) Разбиение области расчета на р = рх х ра подобластей (рх = ра = 3). б) Порядок следования узлов на разделителе для внутренних подобластей: 4,а,5,Ь,с,8.

Для этого упорядочения в диссертации построены методы РУГССв, РУШССС - параллельные варианты УЮСв, УМ1ССС. Диагональная матрица £) выбирается из условия равенства диагональных элементов матриц А я В в методе РУ1ССС и из условия (9) в методе РУМГССО. В РУШССС будем использовать £г» =

точках 1, <т» = аЛЬъфзЩ на линиях 2,3 и в точках 4,5, <т; = 0 в остальных случаях.

Численное исследование скорости сходимости методов РУТССв, РУШССС проводится с помощью решения модельной задачи - задачи Неймана для уравнения — и = —ф(х). В единичной квадратной области расчета вводится трехуровневая локально измельчающаяся сетка со сгущением к центру. Предполагается, что рх = р2- При решении системы уравнений (1) методом РУГССв на 9, 16, 25 процессорах число итераций возрастало по сравнению с решением методом У1ССС на 20-30%. Средний по N коэффициент возрастания числа итераций в методе РУШССС по сравнению с методом УМ1ССС был 1.52 1.55 1.66 соответственно для 9, 16, 25 процессоров. Расчеты на уыерепдом числе процессоров параллельной системы МВС 1000М показали хорошую эффективность методов РУЮСв, РУШССС.

Вторая глава диссертации посвящена построению параллельных вариантов ме-

тодов У1ССО, УМ1ССО, в которых с матрица предобусловливания имеет вид (3), для решения двумерных эллиптических уравнений в произвольной односвязной области расчета. Дня аппроксимации дифференциальных уравнений используется равномерная треугольная или неструктурированная треугольная сетки. Построение параллельных вариантов методов и исследование их скорости сходимости производится на примере задачи Дирихле. В качестве первоначального упорядочения узлов сетки при расчетах на одном процессоре используется Катхилла- Макки (СМ) упорядочение. Уравнение (2) может быть записано в виде

(16)

В §1 главы 2 рассматривается построение параллельных вариантов [7] методов У1ССО, УШССО для решения задачи Дирихле для уравнения (1) на равномерной треугольной сетке. В качестве модельной задачи рассматривается задача Дирихле для уравнения Пуассона в области расчета, являющейся равносторонним треугольником, причем для аппроксимации уравнения (1) используется равномерная треугольная сетка. Коэффициенты в уравнении (16) в этом случае имеют вид

ау = 1/у/З при « ф если узлы »,У связаны в графе матрицы А, ау = О при 1 ф ], если узлы », ] не связаны в графе матрицы А, а» = б/УЗ.

(17)

Разбиение области расчета на подобласти производится в два этапа, причем на обоих этапах по линиям уровня, то есть линиям, соединяющим узлы сетки одного уровня в структуре уровней, полученной в результате построения СМ упорядочения узлов сетки [Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений // М.: Мир. 1984.] всей области или подобласти, полученной на первом этапе. Порядок нумерации подобластей должен соответствовать первоначальному упорядочению узлов сетки. На рис. 3 схематически изображено разбиение треугольной области расчета на 9 подобластей, числами указаны номера подобластей.

Рис. 3. Разбиение области расчета на р = р1 х р2 подобластей и номера подобластей (р1 = р2 = 3).

Для построения методов РУ1ССО, РУМ1ССО - параллельных вариантов методов У1ССО, УМ1ССО используется упорядочение ББ01. В качестве разделителей рассматривается множество узлов сетки на границах с подобластями с большим номером. Порядок следования узлов сетки на разделителях следующий: сначала следуют узлы разделителей с большим номером, то есть номера подобластей в последовательности узлов разделителей не возрастают, внутри каждой подобласти порядок узлов на разделителях тот же, что в первоначальном упорядочении с точностью до эквивалентности. Эквивалентными упорядочениями будем называть упорядочения, в которых для каждого узла сетки узлы шаблона, которые предшествуют ему, и которые следуют после него, одни и те же. На рисунке 3 стрелками указан порядок следования узлов сетки в каждой подобласти.

Матрица предобусловливания в методах РУ1ССО, РУМ1ССО имеет вид

В = (D'1 + Лз)Р(/)~1 + Ä£),

(18)

где Аз = P^Ä'P, Ä~ - строго нижнетреугольная часть матрицы А = PAP'1, Р -матрица перестановок. Заметим, что система уравнений (2) после переупорядочения узлов сетки и перестановки строк и столбцов матрицы А преобразуется к системе уравнений Ау — f. Элементы диагональной матрицы D в PVICCG определяются из условия совпадения диагональных элементов матриц А и В, а в методе PVMICCG -из условия (9).

Для модельной задачи в параллельном методе PVMICCG параметры гц вычисляются по формуле

a\f5l + 0.5а'5в, если ггц = О,

2а-\/Зб/3 + 0.5а25« если гтч = 1, на границах с подобластями

ay/St/Z + 0.5a7Se, если то^ = 2, с меньшим номером,

0.5а3St, если тщ > 3,

(19.в)

«г« = 0.5а15в, в остальных случаях, (19.ф

где - число элементов в матрице А, для которых вд ф 0 и к < >, - площадь ячейки Дирихле. В методе УМГССО параметры а; вычисляются по формуле (19.6) для всех г. Параметр а определяется из условия минимума теоретической оценки числа итераций для модельной задачи, полученной в диссертации, и вычисляется по формуле _

а = у/хфД, (20)

где А1 > 0 -удовлетворяет неравенству

(21)

в котором - произвольный вектор. Для определенияможно использовать

асимптотическое свойство метода скорейшего спуска. Как показывают расчеты, приведенные в разделе 4 §1 главы 2, А1 на очень слабо зависят от М, поэтому их определение можно производить на менее подробной сетке.

Способ параллельной реализации методов РУ1ССО, РУМ1ССО рассмотрен в работе [7]. В разделе 2 §1, а также в работе [7] доказана

Теорема 2. Пусть в уравнении (16) коэффициенты заданы в (17), матрица В определена в (18) , диагональная матрица Б определяется из условия (9), где о: заданы в (19). Тогда для числа итераций в методе РУМ1ССОпри решении модельной

задачи справедлива оценка

« > «о = 0.51n(|)^(2 + a*(pllft))(l + ^) а 0.5Ь(^ (22)

где монотонно возрастающая функция > 0 ме зависит от Se, N, ограни-

чена при фиксированных pi, pit <* задано в (20), Aj > 0 удовлетворяет неравенству

В диссертации доказано, что для числа итераций в методе VMICCG при решении модельной задачи справедлива оценка

п > По =

Из сравнения оценок (22),(23) следует, что коэффициент возрастания числа итераций с ростом числа процессоров почти не зависит от N.

В случав решения задачи Дирихле для уравнения Пуассона в произвольной одно-связной области на равномерной треугольной сетке и проведении разбиения области, как описано выше, в методах РУМ1ССО, УМ1ССО следует использовать параметры оъ, определенные в (19), (20), (21). Для числа итераций методов РУШССО, УМ1ССО справедливы аналогичные оценки.

При решении модельной задачи методами РУ1ССО и У1ССО число итераций в методе РУ1ССО в расчетах возрастало не более, чем на 12% до 100 процессоров и было примерно пропорционально

Средний по N коэффициент возрастания числа итераций в методе РУМ1ССО по сравнению с числом итераций в методе УМ1ССО был 1.54, 1.66, 1.76 соответственно для р = 9,16,25, число итераций возрастало в РУШССО не более, чем в 2 раза до 49 процессоров (р1 = р2) и было примерно пропорционально

Расчеты модельной задачи на умеренном числе процессоров параллельной системы МВС 1000М показали хорошую эффективность методов РУ1ССО, РУМ1ССО.

Как показывают расчеты, приведенные в разделе 4 §1, использование параметров

полученных для модельной задачи, позволяло эффективно решать задачу Дирихле для уравнения (1) с достаточно гладкими коэффициентами х1 = х2 в той же треугольной области расчета.

В разделе 3 §1 рассматриваются другие способы упорядочения узлов равномерной треугольной сетки, в частности ББ03, ББ02. При использовании ББ03 упорядочения существуют 2 типа подобластей, в которых используются одинаковые упорядочения узлов сетки (спроецированное СМ упорядочение для четного и спроецированное обратное СМ упорядочение в противном случае) для разбиения, построенного как указано выше и изображенного на рис. 3 для треугольной области расчета. В параллельном варианте УМЮСО с ББОЗ упорядочением при решении модельной задачи число итераций было примерно пропорционально и возрастало не более, чем в 2 раза до 100 процессоров, однако алгоритм параллельного метода с упорядочением ББ03 сложнее, чем с ББ01. Алгоритм метода с ББ02 упорядочением сложнее, чем алгоритм метода с ББ03 упорядочением, при примерно одинаковой скорости сходимости методов.

В §2 предлагаются параллельные варианты методов У1ССО, УМ1ССО в случае, когда для аппроксимации задачи Дирихле для уравнения (1) используется неструктурированная треугольная сетка. Заметим, что в этом случае не всегда удается построить разбиение области расчета предложенным выше способом (способом 1). Кроме

того, как показывают расчеты модельных задач, такое разбиение не является оптимальным с точки зрения скорости сходимости параллельных методов. Поэтому для разбиения области расчета будем использовать метод, предложенный в работе [Болдырев С.Н., Леванов Е.И., Якубовский М.В. Обработка и хранение нерегулярных сеток большого размера на многопроцессорных системах // В сб. Сеточные методы для краевых задач и приложения. Материалы четвертого всероссийского семинара. Казань, 13-16 сентября 2002. С.33-39] (способ 2). Пронумеруем полученные в результате такого разбиения подобласти, стараясь приблизительно учесть порядок следования узлов в СМ упорядочении узлов всей области расчета.

Построение параллельных вариантов методов "УТССО, УМТССО с использованием ББ01 упорядочения узлов сетки проводится аналогично тому, как это сделано в случае равномерных треугольных сеток. В методе РУМТССО используются следующие значения итерационных параметров [12]

где т,- количество элементов матрицы А (матрицы в системе уравнений после переупорядочения') удовлетворяющих условию а,* / 0 при к < », 5 -площадь расчетной области, а = В методе "УМТССО <ц = 0.5а'5/./У, для всех 1.

Для определения А1 > 0 следует построить аппроксимацию уравнения (1) с коэффициентом х1 = х2 = 1 и граничными условиями Дирихле в рассматриваемой области расчета на равномерной треугольной сетке или в области расчета, близкой к рассматриваемой, но на равномерной треугольной сетке, причем число узлов в равномерной треугольной сетке может быть значительно меньше N. При этом получим матрицу А. Пусть А! удовлетворяет неравенству ^¡^Уя^в < (Ау>у)- Заметим, что в методе УМТССО можно также использовать = 0, однако в расчетах число итераций при этом получается больше, иногда даже в несколько раз.

Численное исследование скорости сходимости предложенных параллельных методов в случае неструктурированной треугольной сетки осуществляется в разделе 2 §2 с помощью расчетов трех модельных задач - задач Дирихле для уравнения Пуассона в разных областях расчета. Для построения дискретного аналога уравнения (1) использовался метод Ритца с кусочно линейными базисными функциями.

В задаче 1 область расчета та же, что в модельной задаче §1, использовалась неструктурированная треугольная сетка, в которой тах 8{/ тш 5, < 3, где & - площади ячеек Дирихле. Разбиение области расчета производилось первым способом. В задачах 2, 3 область расчета представляла собой единичный квадрат, в области расчета строились неструктурированные треугольные сетки со сгущением в 5 раз в центре области (задача 2) и со сгущением в 100 раз в центре области (задача 3). Разбиение области расчета в задачах 2, 3 происходило вторым способом. В приложении к главе 2 приведены картины разбиения области расчета на подобласти в задачах 2, 3 при N и 32000.

При решении задачи 1 методами "УТССО, РУТССО число итераций возрастало не более, чем на 11% (до 25 процессоров). При решении задачи 1 методами "УМТССО, РУМТССО средний по N коэффициент возрастания числа итераций с ростом числа процессоров был 1.49, 1.53, 1.58 соответственно на 9, 16, 25 процессорах. При решении задачи 2 методами "УТССО, РУТССО число итераций возрастало не более, чем

I

ат/Б/л/Ы + 0.5а5 если гщ = 0, на границах с

+ 0.Ьo^S¡N, если то, = 1, с подобластями с а + 0.5аÍS/N, если ш, > 2, меньшим номером,

(24)

<т; = 0.5 а'5/ЛГ,

в остальных случаях.

на 25% (до 25 процессоров); средний по N коэффициент возрастания числа итераций с ростом числа процессоров был 1.52,1.66,1.71 соответственно на 9, 16, 25 процессорах. При решении задачи 3 методами УГССО, РУГССО число итераций возрастало не более, чем на 11% (до 25 процессоров); средний по N коэффициент возрастания числа итераций с ростом числа процессоров в методе РУМГССО был 1.6, 1.65, 1.74 соответственно на 9, 16, 25 процессорах.

В §2 рассматриваются также параллельные варианты методов УГССО, УМГССО, в которых используется обратное Катхилла-Махки (ЯСМ) упорядочение узлов сетки в качестве первоначального. При построении параллельных вариантов методов используется второй способ разбиений области расчета на подобласти. Число итераций, полученное при расчете параллельными методами, мало отличалось от числа итераций в методах РУГССО, РУМГССО при использовании первоначального СМ упорядочения.

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

В §3 главы 2 предложены методы РУМГССО с автоматическим выбором параметров для решения дискретных эллиптических уравнений с сильно отличающимися коэффициентами на неструктурированной треугольной сетке или равномерной треугольной сетке. В этом случае использование параметров (19) или (24) может привести к сильному росту числа итераций с ростом числа процессоров. Указан способ автоматического выбора итерационных параметров, аналогичный предложенному в главе 1. Для модельной задачи с анизотропными коэффициентами, в которой используется равномерная треугольная сетка, с помощью расчетов на умеренном числе процессоров произведено исследование скорости сходимости методов РУМГССО с различными упорядочениями узлов сетки и автоматическим выбором параметров. Показано, что число итераций существенно уменьшается при использовании автоматического выбора параметров.

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

Пусть в прямоугольной области расчета введена ортогональная равномерная или неравномерная сетка, матрица А- пятидиагональная. Уравнение (2) можно записать в виде (4), где а,, Ъ, удовлетворяют условиям (5), а а,-, Ь1 определены в (13) или в (14).

Как известно, в ПТМСГ при стандартном упорядочении узлов сетки матрица предобусловливания имеет вид

В = (£> + ь>о(0.5Ца + Л-))ГГ'(Я + + А+)).

Апприорная информация задается в неравенствах Цйу, у) < [Ау,у), (Дх £>-1 Л2У, у) < 0.25Д(Лу,у), где Д2 = 0.50д + А+, ^ = 0.5£л + А~, В = Вг > 0, у ф 0 - произвольный вектор, а (и, г) = Доказано, что и»о = 2/\/6А является оптимальным, и при оптимальном щ для числа итераций ПТМСГ справедлива оценка

. Ь(2/£) ,/А

При этих п справедливо неравенство (Ауп — },уп — у) < е'(Л«/0 — /,у0 — у).

Элементы диагональной матрицы Б и параметр и0 определяются из условия минимума оценки числа итераций (25). Для их определения используют алгоритм, приведенный в работе [Самарский А. А., Николаев Б. С. Методы решения сеточных уравнений // М.: Наука. 1978. 589С]. Доказано, что для достаточно гладких Ха метод ПТМСГ требует для сходимости 0(1п(2/г)\/Ж) итераций.

Для построения параллельных вариантов ПТМСГ производится разбиение области расчета на подобласти в двух пространственных направлениях, как изображено на рис.1 а) и рис.1 б) и вводятся соответственно упорядочения узлов сетки ББ01 и ББ02, как в главе 1. В методе ППТМСГ1 - параллельном варианте ПТМСГ с упорядочением ББ01 матрица предобусловливания имеет вид

в методе ППТМСГ2 - параллельном варианте ПТМСГ с упорядочением Б002

где матрицы А,, и А2 были определены в (7) и (8). Элементы диагональной матрицы Б и параметр о>о определяются из условия минимума оценки числа итераций для параллельного метода. В результате проведенного теоретического исследования получилось, что для определения Б и ша в ППТМСГ2 следует [2]

1. Решить трехточечные задачи

<£/№><»)> Уа€о£,

Оа/(/»-Йа), Уа € О»*,

(а+/Л+ + аа//>-)/Й„, У„ 6 <4, О, Уа е

мх = -

(27)

»о = »«. = О,

(п „,« \ _ / 0-5 | а+/А+ - | /Ьа, уа 6 и .

=0. а =1,2.

Здесь и далее в! = а* = х)1+о.5л>а2 = Йл-"' = Х?,л+о.8> ^ = (Л")л+1>

и1а = {^„2па + 1 < У„ < (2я„ + 1) - 1,= 0, ...Ми}, «4 = {^¿.(2па + 1) +1 < Уа < М}.(2па + 2) - 1,па = 0,...Ми}, = {%2па,па = 1 ,...Ми}, и*а = {^„(2па + 1),па = 0 ,...МаЛ, Л*. = ЛГа/ра, М1а +1 и +1 - количество подобластей в одном пространственном направлении при четных и нечетных ра, а = 1,2.

2.0пределить Ь" с" по формулам Ьа = тах^0 иа, С" = таху0 га". 3. Определить элементы диагональной матрицы и параметр ы0 с использованием расположенных ниже формул.

(0+/А+ + 0.5^ | «ПК - аа!К I)/(Ь° + Уа 6

<Р =

+ 0.5^ | *ИК - аа!К \)/(Ъ" + }а 6 ц|,

(1 + 0.5^)(а+/Л+ + аа/Н~)/(Ьа + 0.5^(а£/Л+ +аа/к-)/(Ь° + уДг<?)1Па,

(29 .а)

¿а е "а.

Справедлива

Теорема 3. Пусть матрица А заданна в (4), (5), (13) или (14), матрица предобусловливания В определена в (26), (8), (31), причем диагональные элементы 4> диагональной матрицы 17 вычисляются по формулам (29), 5 = 1, А дано в (30), Ь" = тах3„ и", с" = тах^ т", где V", - решения задач (27), (28), а = 1,2. Тогда ППТМСГ2 (6), (26), (8), (29), (31) сходится, и для выполнения неравенства (Ауп — />уп — у) < £1(Лу° —/,у0 —у) достаточно п итераций, где п удовлетворяет неравенству (25).

Аналогичным образом определяются матрица Б и параметр и>о в методе ППТМ-СГ1 [4], формулируется теорема о сходимости метода ППТМСГ1.

Пусть коэффициенты Ха ограничение функции, которые при любом Х3 й имеют конечное число точек разрыва в направлении ха. В диссертации доказано, что в случае равномерной ортогональной сетки и одинакового количества узлов сетки по обоим пространственным направлениям для сходимости методов ППТМСГ1, ППТМСГ2 при любых фиксированных рх, рз требуется 0(1п(2/£)\/^) итераций, для достаточно больших рг = рг требуется 0(1п(2/е)^/ру/77^) итераций. В общем

случае По = 1п(2/£)^/тах<, \/Д°, где для достаточно больших рг, р? справедливо т/&=0(раМа),а = 1,2.

В диссертации получена оценка числа итераций метода ППТМСГ2 для модельной задачи - задачи Дирихле для уравнения Пуассона в прямоугольнике [8]

|1п(2/£)

По(£) « ШаХ [/Йа\Л + 3°(Ра)] '

где

Г *ра/8,_ при ра - четном,

'и(Ро) " 1 - 1)[1 + (Ра ± 2)/р„]/8, при ра - нечетном,

(32)

знак " + " соответствует случаю (ра — 1)/2 - нечетное, знак " — " -случаю (ра — 1)/2 -четное, gа монотонно возрастающая функция, а = 1,2. Из этой оценки числа итераций видно, что при Л1 > Л2 рост числа итераций с ростом числа процессоров будет меньше при рг < р. Теоретический коэффициент возрастания числа итераций с ростом числа процессоров по сравнению ПТМСГ в частном случае, когда выполнены равенства = >12 и р1 = р2 имеет вид 5 = + да(ра), а = 1,2, д < 2.03 дляр < 64.

Расчеты модельных задач в единичной квадратной области расчета показали, что число итераций пропорционально наблюдается приемлемый рост числа

итераций с ростом числа процессоров, более медленный в методе ППТМСГ2. Заметим, что алгоритм ППТМСГ2 сложнее алгоритма ППТМСГ1. При решении задачи Дирихле для уравнения Пуассона в единичном квадрате при Е = 10-4, р, = р2 для метода ППТМСГ1 средний по Лк коэффициент возрастания числа итераций был 1.38,1.56,1.59,1.70 дляр = 4,9,16,25, а для ППТМСГ2 - 1.27,1.33,1.37,1.34,1.37 для р = 4,9,16,25,64. При решении задачи с переменным коэффициентом хг — х2 методом ППТМСГ2 этот коэффициент был равен 1.28,1.40,1.55 для р = 4,9,12. Эффективности предложенных параллельных методов определялись при решении модельной задачи при рг = р1 на 32-х процессорной станции Рагеу1ес СС. Эффективность на 4-25 процессорах метода ППТМСГ1 была 60%-45%, метода ППТМСГ2 - 68%-56%.

В §2 главы 3 предлагаются методы ППТМСГЗ и ППТМСГ4 - параллельные варианты ПТМСГ для решения трехмерных разностных эллиптических уравнений с граничными условиями Дирихле с разбиением области расчета соответственно в двух и в трех пространственных направлениях [5]. Пусть в области расчета, являющейся прямоугольным параллелипипедом, введена ортогональная равномерная или неравномерная сетка, матрица А- семидиагональная.

Для построения ППТМСГЗ - параллельного варианта ПТМСГ для решения трехмерных задач область расчета разбивается в двух пространственных направлениях, как изображено на рис.4а). Используется упорядочение узлов сетки , указанное цифрами и стрелками на рис.4а). Матрица предобусловливания в методе ППТМСГЗ -параллельном варианте ПТМСГ с упорядочением узлов сетки, изображенном на рис. 4 а), имеет вид В = (Г>+а)о(0.5ил+12))Д-1(^+«о(0.5£>А+^)), где32 = Р^ЗГА, - строго нижнетреугольная часть матрицы - матрица переста-

Рис.4. Разбиения области расчета на а)р = рг х р2 подобластей и порядок следования узлов сетки в ППТМСГЗ (р1 = р2 = 3), б)р = р1 х р2 х р3 подобластей и порядок следования узлов сетки в ППТМСГ4 (рз = 2).

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

Диагональная матрица Б и параметр иц в методах ППТМСГЗ, ППТМСГ4 определяются из условия минимума оценки числа итераций этих методов с использованием алгоритмов, приведенных в работе [5], аналогичных рассмотренному выше для метода ППТМСГ2. Параллельная реализация методов ППТМСГЗ," ППТМСГ4 подробно описана в работе [5].

Пусть коэффициенты хй - ограничение функции, которые при любом хр, г, (а ф ¡3, а ф 7, /3 ф 7) имеют конечное число точек разрыва в направлении хй. Доказано , что в случае равномерной ортогональной сетки с одинаковым числом узлов по всем направлениям методы ППТМСГЗ и ППТМСГ4 требуют для сходимости 0(\п(2/е)у/ТИЦ) итераций при любых фиксированных р„ р2 и р1; р2, р3. В методе ППТМСГ4 для достаточно большого числа р1 = рг = рз щ = Для модельной задачи - задачи Дирихле для уравнения Пуассона в прямоугольном

параллелепипеде для числа итераций метода ППТМСГЗ получена оценка по и max[y/F^l + j,(ft), ^ + v^lЬ(2/s)/v^/2,

а для числа итераций метода ППТМСГ4 получена оценка

п0« max + За(ра)) Ь (2/е)/,/?/2,

л—1|2|3 * "

где да(ра) определена в (32). Из оценки числа итераций метода ППТМСГЗ видно, что при Ni > Nj рост числа итераций с ростом числа процессоров будет меньше при Pi < Pit что подтверждается расчетами.

В формулах (33) приведены времена счета итерационного процесса в методах ППТМСГЗ (ti), ППТМСГ4 (<j) без учета времени, идущего на пересылки при вычислении скалярных произведений.

t\ « щ[20гу + UNfa/p1'1 + Л£(18т. + 1Тг+)/р], (ППТМСГЗ)

(33)

t, « n,[42ry + UNfa/p7'3 + ЛГ»(18г. + 17г+)/р], (ППТМСГ4)

где ту - время установки на обмен, та - время пересылки единицы информации, т., т+ - времена выполнения арифметических операций, ni, nj - числа итераций. Как видно из (33), при Ее очень больших значениях р и при ту >> Гц имеем: tj > и предпочтительнее использовать ППТМСГЗ. Однако для достаточно больших р и ЛГк наступит ситуация, когда ii > tj и целесообразно использовать ППТМСГ4. Заметим, что алгоритм ППТМСГ4 значительно сложнее алгоритма ППТМСГЗ и требует больше инициализаций обменов.

Расчеты модельных задач показали, что число итераций в методах ППТМСГЗ, ППТМСГ4 примерно пропорционально т/Щ, медленно растет с ростом числа процессоров. При решении задачи Дирихле для уравнения Пуассона в единичном кубе средний по Nh коэффициент возрастания числа итераций с ростом числа процессоров был в методе ППТМСГЗ 1.09,1.16,1.14,1.17,1.16,1.21,1.23 для р = 4,9,16,25,36,64,81, а в методе ППТМСГ4 - 1.09,1.15 для р = 8,27. Время счета модельной задачи на 32-х процессорной станции Parsytec СС методом ППТМСГЗ t = 13.39,7.32,5.09,4.38 для р = 4,9,16,25, а ППТМСГ4 - t = 8.62,4.16 для р = 8,27.

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

Используется DD01 упорядочение для построения параллельного варианта MIC-CG(0). На множестве узлов разделителей, указанном ниже, устанавливается следующий порядок узлов сетки: все узлы на всех линиях 4,5, на всех плоскостях 6,7, на всех линиях 8. Матрица предобусловливаиия в параллельном варианте MICCG(O) для трехмерных задач имеет вид

где где Ai = Р^А'Рг, А~ - строго кижнетреугольная часть матрицы А = Р2АР,-1, Р2 - матрица перестановок; вид матрицы ~Ai приведен в работах [1,9].

//

2 L6 з L б 3 L

2 4 1 2 4 1 2

7 8 5 7 8 5 7

1 L 6 3 U 6 3 L

2 4 12 4 1 2

7 8 5 7 8 5 7

0 L 6 3 L 6 3 L

У 0 1 2

/

/ и /

I/

Рис. 5. Разбиение области расчета на подобласти для решения трехмерных . X эллиптических уравнений параллельным вариантом MICCG(0)(pi =рз = 3).

Элементы диагональной матрицы Б определяются из условия (9), где

+ если I € йр, для /3 = 1,2,3,4,5, (оН* в противном случае ,

(34)

где шр - множество узлов на линиях с номером /3 или плоскостях с юмером ¡3 {J3 = 1,2,3,4,5, б, 7,8), ¿>о -множество внутренних узлов всех подобластей, > 0, £о > О Алгоритм параллельной реализации предложенного метода описан в работе [1]. Можно доказать, что в случае достаточно гладких коэффициентов Ха при любых фиксированных р1; р2 параллельный вариант MICCG(O) для трехмерных задач требует для сходимости 0(1п(2/е)\/ЗУл) итераций.

определяются из условия минимума оценки числа итераций для модельной задачи - задачи Дирихле для уравнения Пуассона в единичном кубе, полученной в диссертации:

При этом оценка числа итераций для модельной задачи имеет вид •

п>п0ъО.Ь 1п(2/е) у/2[1 + ж max(v>(í>i), V(P2))/8][1 + 1/(*Л)], (36)

где vÍPa) = Ра для четных ра, <р(ра) = Ра — 1 /Ра для нечетных ра, а = 1,2. Заметим, что оценка (36) грубая, однако использование параметров (34), (35) в расчетах модельных задач позволяло сохранить характер асимптотической зависимости числа итераций от числа узлов сетки при фиксированных p1, p2 такой же, как в MICCG(O). Наблюдался приемлемый рост числа итераций с ростом числа процессоров. Средние по Nh коэффициенты возрастания числа итераций с ростом числа процессоров, полученные в результате решения задачи Дирихле для уравнения Пуассона в единичном кубе были [11] 1.33,1.38,1.47,1.52,1.61,1.76 для р = 4,9,16,25,36,64, а полученные в результате решения задачи Неймана для уравнения Пуассона в единичном кубе - 1.23,1.30,1.46,1.50,1.55 для р = 4,8,16,20,25. Следует ожидать, что если использовать экспериментальный подбор параметров ^з, то рост числа итераций с ростом числа процессоров будет медленнее.

Во втором параграфе главы 4 построен алгоритм решения как стационарных, так и нестационарных задач гидродинамики в естественных переменных "скорость-давление" на многопроцессорных вычислительных системах на примере трехмерных

задач. Для моделирования течений используется система хвазигидродинамических (КГД) уравнений, записанная в эйлеровой системе координат, а для решения задачи Неймана для уравнения Пуассона для давления - параллельный вариант метода. М1ССО(0), предложенный в §1 главы 4 в настоящей диссертации, при этом полагалось р(1,1, 1) = 1.

Рассматривается трехмерное течение изотермической жидкости в кубической каверне с ребром Я. Верхняя крышка каверны движется с постоянной скоростью и. Система КГД уравнений, описывающая течение в каверне, после обезразмеривания имеет вид

дих диу 8и, _ дшх дту дш.

■+ —- + дх ду дх

дх ду дх '

дих д{и1) д(ихиу) д(ихи,) др _ 2 дЧх 1 д /дих диу\ Ш дх ду дх Яе дх1 Яе ду^ ду дх ' +

1 0 (дих дис^ ^д{ихтх) ^ д(иуюх) ^ д^Юу) ^ д(и,и)х) ^ д(ихы.)

НедЛдг ду>

дх

ду

ду

дх

д^ д(ихиу) д{и\) д(ихиу) др _ 1 д ,дих дщ,} 2 ач т + дх ду + дх ду Яедх^ду + дх' + Яе ду2 +

1 д /диу ди,\ д(иху>у) д(иуУх) д^щ) д(и,Юу) д(иую.)

Яедх^дх ду'+ дх. + дх + ду + дх * дх '

ди, Э(ц,ц.) д{иуиж) 5(и') др_ 1 д /ди, ди,\ 1 д ,диу ди,х & + дх + ду + дх + дх~ Яедх^дх + дх) + Яеду^дх + ду )

+7Г-

2 д2и, д(игтг) д(и2гих) д(и,юу) д(и,ю.)

---1---1---1------1--£--

где

Яе дх1

, = т(г

дх

дх

ду

ду

дих 'дх

ди.

дих

ди,

+ а

дих др\ дх

ир\ г дщ, аиу ащ ар\

^у = т{их— + иу^- + и,— +

диу

диу др\

'дх

( ои, ои, ди, др\

ду

дх ду'

Поле давления находится по уже известному полю скорости путем решения уравнения Пуассона

д2р д3р д'р _ 1 гдих диу ди,л _ д / дих дих

ду

+ и.

дих\ дх)

а,Л

ду^'дх

диу диу дПу\ д

ди,

дх ) дг^1" дх

> ,

ди,

ду

. ди,\

Используются следующие граничные условия: на неподвижной твердой поверхности и = 0; на поверхности у = 1 условия и1. = 1,и> = 0, и2 = 0; граничные условия для давления др/дп = 0, где и -нормаль к поверхности.

В качестве начального состояния выбиралось состояние покоя. В настоящей работе использовалось г = 0.01,0.001,0.0005 для случаев Кв = 100,1000,2000 соответственно. Решалась задача на установление. Поле скоростей определяется с использованием явной разностной схемы.

Для параллельной реализации решения разностных уравнений, аппроксимирующих КГД систему, трехмерная область расчета разбивается в двух пространственных направлениях ОХ и 0Y, как было изображено на рис.5. Алгоритм параллельной реализации решения уравнений явной разностной схемы для КГД системы, которая используется для определения поля скоростей, аналогичен разработаному ранее для двумерных задач Четверушкиным, Елизаровой, Дуйсекуловым. Решение разностного аналога задачи Неймана для уравнения Пуассона для определения давления осуществляется параллельным вариантом метода MICCG(O) для трехмерных задач, предложенном в диссертации. Отметим, что решение уравнения Пуассона для определения давления занимает большую часть времени счета.

Задача о течении в кубической каверне с подвижной крышкой решалась при числах Рейнольдса Re = 100, Re = 1000, Re = 2000 на равномерных пространственных сетках с одинаковым числом узлов Nk по всем трем направлениям. При Re = 100 расчеты проводились при Nt = 22 и Nt = 42, At = 0.0025, при Re = 1000: Nt = 42, Nh = 82 и Nh = 162, At = 0.002, при Re = 2000: Nh = 82, At = 0.002. Результаты расчетов описаны в работах [1,9].

При расчете задачи с Re = 1000, Nh = 82 на 50 временных слоях получилось время счета t = 21.18,5.69,4.10 на 4,16, 25 процессорах МВС 1000М, что подтверждает эффективность использования параллельной вычислительной техники для расчетов. В диссертации продемонстрирована сходимость численного решения по сетке с помощью расчетов на сетках с Nh = 42,82,162 при Re — 1000.

В диссертации (в приложении 1 к главе 4) представлены картины течения жидкости при различных числах Re в сечениях z = 0.5, х = 0.5, у = 0.5. Как видно из этих рисунков, при Re= 1000,2000 течение становится трехмерным, картина течения существенно усложняется, появляются дополнительные источники и стоки. Наблюдается хорошее совпадение полученных результатов с имеющимися в литературе данными.

В §3 главы 4 с помощью вычислительного алгоритма, построенного на основе КГД системы уравнений, проводится численное исследование задачи о термокапиллярной конвекции в прямоугольной полости длины L и высоты Я (L/H =2) в условиях пониженной гравитации. Предполагается, что полость имеет твердую нижнюю границу и свободную верхнюю, которая считается недеформируемой. Для численного решения задачи вводится равномерная ортогональная сетка с шагом h по обоим пространственным направлениям. Поле скоростей и температуры определяется с использованием явной разностной схемы для КГД системы. Для решения задачи Неймана для уравнения Пуассона для определения давления используются методы MICCG(O), PMICCG1 с итерационными параметрами, полученными теоретически для модельной задачи в главе 1. Расчеты проводились на 4-х процессорах станции Parsytec CC и на персональном компьютере INTEL CELERON 433 MHZ, результаты расчетов совпали. При использовании для расчетов сетки 162 х 82 счет на 4-х процессорах Parsytec CC происходил примерно в 3.5 раза быстрее, чем на одном процессоре.

Изучалось влияние совместного действии термохалиллярных сил и постоянного ускорения силы тяжести ортогонального свободной поверхности на структуру термокапиллярной конвекции и влияние квазистатической составляющей микроускорепия на конвективное движение жидкости. Результаты расчетов приведены в приложении 2 к главе 4 и в работе [13].

Для исследования влияния гравитационных сил на структуру термокапиллярного течения проведена серия расчетов в прямоугольной полости на равномерной сетке при Рг=0.018, Re=l, Ma=500 и при различных числах Грасгофа (в диапазоне 100-

1000000). В результате расчетов установлено, что слабая гравитационная конвекция (0г«500) не оказывает существенного влияния на структуру начального термокапиллярного течения (при От — 0). Развитая гравитационная конвекция существенно влияет на структуру начального термокапиллярного течения. Характерные для режима развитой гравитационной конвекции линии уровня функции тока и изотермы представлены в приложении 2 к главе 4. При От = 10е течение становится нестационарным, устанавливается колебательный режим.

Для практических приложений очень важно выяснить влияние микроускорений на конвективное движение. Квазистатическая составляющая микроускорений обусловлена движением спутника относительно центра масс как твердого тела, градиентом гравитационного поля Земли, сопротивлением атмосферы и может быть весьма точно вычислена по информации о движении спутника. В КГД системе появляются дополнительные члены: ОттТ, ОткТ, где Ота — Сгосов^, Сг„ = Сг05шы£.Для выяснения влияния микроускорений на конвективное движение расчеты проводились при следующих значениях параметров: От0 = 1000, w = 10, Рт = 0.018, Яе = 1, Ма — 500 и Ма = 1000. Установлено, что несмотря на то, что структура конвективного движения в данном диапазоне параметров определяется термохапиллярной конвекцией, колебания вектора микроускорений приводят к колебаниям температуры и теплового потока в расплаве, что вызывает колебания скорости роста кристалла. Зависимость тепломассообмена от колебаний вектора остаточного ускорения может вызывать неравномерный рост кристаллов даже в режиме ламинарного конвективного движения. Полученные результаты хорошо согласуются с известными экспериментальными данными.

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

1.Созданы параллельные варианты методов МЮСО(О), МАБСО для решения двумерных эллиптических уравнений, параллельный вариант М1ССО(О) для решения трехмерных уравнений на равномерной ортогональной сетке, с помощью теоретического и численного исследования показано, что в параллельных вариантах методов сохраняется характер асимптотической зависимости числа итераций от числа узлов сетки и наблюдается приемлемый рост числа итераций с ростом числа процессоров; получены теоретические оценки числа итераций методов РМ1СС01, РМ1СС02 для модельной задачи.

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

3.Созданы параллельные варианты методов У1ССО и УМ1ССО для решения двумерных эллиптических уравнений на равномерных треугольных сетках, а также на неструктурированных треугольных сетках и на локально измельчающихся сетках на основе прямоугольных элементов, в параллельных методах наблюдается приемлемый рост числа итераций с ростом числа процессоров и сохраняется характер асимптотической зависимости числа итераций от числа узлов сетки в случае равномерной треугольной сетки; получены теоретические оценки числа итераций методов РУМ1ССО, УМ1ССО для модельной задачи.

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

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

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

Автор выражает благодарность члену корреспонденту РАН Б.Н. Четверушкину за проявленное внимание к работе, полезные обсуждения и замечания и поддержку работы. Автор выражает благодарность профессору Т.Г. Елизаровой за постановку задач гидродинамики и обсуждение результатов расчетов, старшему научному сотруднику И.В. Попову и младшему научному сотруднику С.Н. Болдыреву за предоставленные неструктурированные треугольные сетки и за результаты разбиения области расчета на подобласти.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ.

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

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

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

2000. Т.Зб. N 7. С.953-962.

4. Милюкова О.Ю. Параллельные варианты некоторых итерационных методов с фак-торизованной матрицей предобусловливания // Ж. вычисл. матем. и матем. физ.

2001. Т. 41. N 11. С.1619-1636.

5. Милюкова О. Ю. Параллельные варианты попеременно-треугольного метода для решения трехмерных эллиптических уравнений // Ж. вычисл. матем. и матем. физ.

2002. Т.42. N 10. С.1529-1539.

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

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

8. Милюкова О.Ю., Четверушкин Б.Н. Параллельный вариант попеременно-треугольного метода // Ж. вычисл. матем. и матем. физ. 1998. Т. 38. N 2. С. 219-229.

9. Elizarova T.G., Miliukova O.Yu. Parallel algoiithm for numerical simulation of 3D incompressible flows // Parallel Computational Fluid Dynamics (Moscow, Russia, May 13-15, 2003). Edited by B.Chetvcruslikin, A. Ecer, J. Periaux and N. Satofuka-Assistant Editor: Pat Fox, Elsevier Science B.V., Amsterdam. 2004. P.65-72.

10. Milyukova 0. Yu. Parallel approximate factorization method for solving discreate

elliptic equations // Parallel Comput. 2001. 27. P. 1365-1379.

11. 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.

12. Milyukova O.Yu. Parallel Iterative Methods with Factored Preconditioning Matrices for Solving Discrete Elliptic Equations // 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. P.97-104.

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

Издательство 0 0 0 "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 18.05.2004 г. Формат 60x90 1/16. Усл.печ.л. 1,75. Тираж 100 экз. Заказ 602. Тел. 939-3890,939-3891,928-1042. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

»1228t

ВВЕДЕНИЕ

ГЛАВА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.

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

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

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

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.