автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Параллельные алгоритмы решения задач грави-магнитометрии и упругости на многопроцессорных системах с распределенной памятью

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

8. —

АКИМОВА ЕЛЕНА НИКОЛАЕВНА

□□34 77929

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

05.13.18 — математическое моделирование, численные методы и комплексы программ

-1 ОКТ 2009

АВТОРЕФЕРАТ • диссертации на соискание ученой степени доктора физико-математических наук

Челябинск - 2009

003477929

Работа выполнена в Институте математики и механики УрО РАН.

Научный консультант: доктор физико-математических наук

член-корр. РАН Владимир Васильевич Васю

Официальные оппоненты: доктор физико-математических наук

член-корр. РАН Петр Сергеевич Мартышко, доктор физико-математических наук профессор Леонид Давидович Менихес, доктор физико-математических наук Михаил Владимирович Якобовский.

Ведущая организация: Институт вычислительной математики

и математической геофизики СО РАН, г. Новосибирск

Защита состоится 14 октября 2009 г. в 12-00 часов на заседании диссертационного совета Д 212.298.14 по защите диссертаций на соискание ученой степени доктора наук при Южно-Уральском государственном университете по адресу: 454080, г. Челябинск, пр. им. В.И. Ленина, 76.

С диссертацией можно ознакомиться в библиотеке Южно-Уральского государственного университета.

Автореферат разослан "_" сентября 2009 г.

Ученый секретарь

диссертационного совета Д 212.298.14 л^

доктор физ.-мат. наук, профессор С—-'г' Л.Б. Соколински

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальность темы.

Важнейшими задачами исследования структуры земной коры являются обратные задачи грави-магнитометрии: задача гравиметрии о нахождении переменной плотности'в слое и структурные задачи грави-магнитометрии о восстановлении геологической границы. Задачи описываются линейными и нелинейными интегральными уравнениями Фредгольма первого рода и после дискретизации с использованием итерационных процессов сводятся с системам линейных алгебраических уравнений (СЛАУ) с плохо обусловленными заполненными матрицами большой размерности.

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

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

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

Таким образом, данные задачи описываются дифференциальными либо интегральными уравнениями и сводятся к решению СЛАУ.

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

эффективности решения задач математического моделирования является распараллеливание алгоритмов и использование многопроцессорных вычислительных систем (МВС).

. Проблемам распараллеливания алгоритмов посвящено множество статей и монографий отечественных и зарубежных авторов. Работы В.В. Воеводина 1,2 посвящены совместному исследованию параллельных численных методов и параллельных вычислительных систем. В качестве математических объектов, используемых как посредники для описания алгоритмов и МВС, применяются ориентированные графы. Среди работ, посвященных параллельным прямым и итерационным методам решения систем линейных уравнений, отметим обзоры В.Н. Фаддеевой и Д.К. Фаддеева 3, монографии Е. Валяха, И.Н. Молчанова, Дж. Ортега 4, сборник статей под редакцией Г. Родрига5, монографию под редакцией Д. Ивенса, и др.

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

т О

и эффективности: 5т = трЛ- , Ет — , где Т\ — время выполнения

т т

последовательного алгоритма на одном процессоре, Тт — время выполнения параллельного алгоритма на МВС с числом процессоров т (т > 1). Тт = Тс + Т0- совокупность чистого времени счета и накладных расходов. В общем случае эффективность распараллеливания 0 < Ет < 1. В идеальном случае Ет близко к единице, но при решении практических задач она уменьшается за счет накладных расходов и дисбаланса нагрузки.

Основной целью при построении параллельных алгоритмов является получение максимального ускорения и эффективности: 5т ~ т и Ет~ 1.

В некоторых случаях удается получить Ет > 1. Данный факт связан с уменьшением времени обращения к данным за счет кэш-памяти.

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

Другой подход предложен в работе В.А. Вальковского, В.Е. Котова,

1 Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. 296 с.

2Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 599 с.

3 Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре -1,2. // Кибернетика. 1977. № 6. С. 28-40; 1982. №3. С. 18-31.

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

5 Параллельные вычисления / под ред. Г. Родрига. М.: Наука, 1986. 376 с.

А.Г. Марчука и H.H. Миренкова. Он включает в себя однородное распределение массивов и других структур данных по ветвям параллельного алгоритма. При таком распределении имеют место:

1) равенство объемов распределяемых частей массивов;

2) разделение массивов на части параллельными линиями;

3) дублирование массивов или частей одинаковым образом.

Один из подходов к распараллеливанию связан с методами разделения или декомпозиции областей, которые применяются при решении сеточных задач математической физики в областях сложной формы. Основная идея этих методов заключается в декомпозиции области, в которой ищется решение краевой задачи,, на подобласти простого вида. Различные варианты методов разделения областей исследовались многими авторами в нашей стране (Е.С. Николаев и A.A. Самарский, В.К. Агапов, Ю.А. Кузнецов, С.А. Финогенов, A.M. Мацокин, В.И. Лебедев и В.И. Агошков, и др.).

В работах А.Н. Коновалова и H.H. Яненко вопросы распараллеливания вычислений рассматриваются с точки зрения изучения модульной структуры вычислительных алгоритмов для решения определенного класса задач (математической физики). Решение исходной задачи сводится к последовательному решению "простых" задач в стандартной области. Эти задачи названы базисными задачами, а последовательность решения таких задач, обеспечивающая решение исходной задачи, — представлением исходной задачи в данном базисе. Модуль есть программная реализация базисной задачи. Вычислительный алгоритм и программа одновременно приобретают модульную структуру. Модульная декомпозиция алгоритма упрощает его распараллеливание.

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

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

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

Научная новизна.

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

1. Построены прямые параллельные алгоритмы решения СЛАУ с пяти-диагояальными матрицами и параллельные алгоритмы матричной прогонки для решения СЛАУ с блочно-трехдиагональными матрицами.

2. Доказаны теоремы об устойчивости параллельных алгоритмов решения СЛАУ с трехдиагональными, пятидиагональными и блочно-трехдиагональными матрицами в зависимости от соотношения коэффициентов исходных систем уравнений.

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

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

5. Разработан и реализован на МВС-1000 комплекс параллельных программ решения линейной обратной задачи гравиметрии и нелинейных обратных задач грави-магнитометрии на основе метода Ньютона с использованием регулярных параллельных прямых (типа Гаусса) и итерационных (градиентного типа) алгоритмов.

6. На базе комплекса программ В.й. Машукова разработан и реализован на МВС-1000 комплекс параллельных программ МГИУ-2 решения трехмерной статической задачи упругости в ограниченных областях с различными типами граничных условий. В случае смешанных граничных условий реализован итерационный альтернирующий метод Шварца.

Защищаемые положения.

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

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

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

раллельные вычислительные технологии и выполнены численные расчеты для реальных гравитационных и магнитных полей для различных областей (Средний Урал, Казахстан, Оренбург и Башкирия).

4. Разработан и реализован на МВС-1000 комплекс параллельных программ решения линейной обратной задачи гравиметрии и нелинейных обратных задач грави-магнитометрии на основе метода Ньютона с использованием регулярных параллельных прямых и итерационных алгоритмов.

5. Разработан и реализован на МВС-1000 комплекс параллельных программ МГИУ-2 решения трехмерной статической задачи упругости в ограниченных областях с различными типами граничных условий с использованием параллельных вычислительных технологий на всех этапах решения задачи и протестирован на серии модельных расчетов.

Практическая значимость.

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

В 2001 г. комплекс параллельных программ МГИУ-2 решения трехмерной задачи упругости методом граничных интегральных уравнений передан в Институт автоматики и процессов управления (ИАПУ) ДВО РАН для решения задач упругости на многопроцессорном комплексе МВС-1000.

Комплекс параллельных программ решения линейной задачи гравиметрии о восстановлении плотности в слое и решения нелинейных задач грави-магнитометрии о нахождении поверхности раздела между средами успешно используется в реальных расчетах для различных областей совместно с сотрудниками Института геофизики УрО РАН (ИГФ УрО РАН).

Разработан специализированный Web-сервер, предназначенный для запуска программ, реализующих параллельные, алгоритмы решения линейной обратной задачи гравиметрии на МВС-1000 через Web-интерфейс.

Разработанные параллельные алгоритмы легли в основу создания спецкурса "Параллельные вычисления" для студентов специальности "Математическое обеспечение и администрирование информационных систем".

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Всероссийских и Международных конференциях и семинарах: Международных конференциях "Parallel Computing Technologies - РаСТ" (Обнинск, 1993; Санкт-Петербург, 1995; Ярославль, 1997), Международных конференциях "Numerical Methods in Continuum Mechanics" (Липтовский Ян - Словакия, 2000; Жилина - Словакия, 2003), Восьмом Всероссийском съезде по теоретической и прикладной механике (Пермь, 2001), Дальневосточной школе - семинаре им. академика Е.В. Золотова (Владивосток, 2001), Международной конференции "Numerical

Methods and Computational Mechanics" (Мишкольц - Венгрия, 2002), Международных летних школах - конференциях "Advanced Problems in Mechanics - АРМ" (Санкт-Петербург, 2002, 2003, 2004), I, II и III Всероссийских конференциях, посвященных памяти академика А.Ф. Сидорова "Актуальные проблемы прикладной математики и механики" (Екатеринбург-Трубник, 2003; Абрау-Дюрсо, 2004; Абрау-Дюрсо, 2006), Всероссийской конференции "Декомпозиционные методы в математическом моделировании и информатике" (Москва, 2004), XIV Всероссийской конференции "Алгоритмический анализ неустойчивых задач" (Екатеринбург-Трубник,

2004), XV Всероссийской конференции "Теоретические основы и конструирование численных алгоритмов для решения задач математической физики с приложением к многопроцессорным системам" , посвященной памяти К.И. Бабенко.(Абрау-Дюрсо, 2004), XI Всероссийской Школе-семинаре "Современные проблемы математического моделирования" (Абрау-Дюрсо,

2005), Международном семинаре им. Д.Г. Успенского "Вопросы теории и практики геологической интерпретации гравитационных, магнитных и электрических полей" (Екатеринбург, 2006), XXIV Генеральной ассамблее международного союза геодезии и геофизики "Earth: our changing planet" (Перуджа - Италия, 2007), Международной конференции, посвященной 50-летию Института геофизики УрО РАН "Геофизические исследования Урала и сопредельных регионов" (Екатеринбург, 2008), V Международной конференции "Алгоритмический анализ неустойчивых задач, посвященной 100-летию со дня рождения В.К. Иванова" (Екатеринбург - Трубник, 2008), Международной конференции "Математические методы в геофизике - 2008" (Новосибирск, 2008), Международных конференциях "Параллельные вычислительные технологии - ПаВТ" (Челябинск, 2007; Санкт-Петербург, 2008; Нижний Новгород, 2009).

Публикации. Основные результаты диссертации опубликованы в 29 работах, в том числе в научных изданиях, рекомендованных ВАК [1-7], в рецензируемых российских и иностранных журналах [8-12], В работе [3] E.H. Акимовой принадлежит разработка параллельных алгоритмов решения трехмерной задачи упругости с заданным на границе вектором усилий и выполнение модельных расчетов. В работах [4 - 5] E.H. Акимовой принадлежит разработка и реализация параллельного алгоритма матричной прогонки на МВС-1000 при решении задач многокомпонентной диффузии. В работах [6 - 8] E.H. Акимовой принадлежит разработка и реализация регулярных параллельных алгоритмов решения линейной обратной задачи гравиметрии о восстановлении плотности в слое. В работе [21] E.H. Акимовой принадлежит разработка регулярных параллельных алгоритмов решения упруго-пластической задачи. В работах [12,22 - 29] В.В. Васину при-

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем диссертационной работы составляет 255 страниц. Библиография содержит 143 наименования.

Исследования по теме диссертации выполнены в период с 1990 по 2008 годы в Отделе некорректных задач анализа и приложений Института математики и механики УрО РАН.

Автор выражает искреннюю признательность своему учителю главному научному сотруднику ИВМиМГ СО РАН академику РАН Анатолию Николаевичу Коновалову.

Автор выражает благодарность за постановку ряда математических проблем, поддержку, полезные замечания и обсуждения заведущему Отделом некорректных задач анализа и приложений ИММ УрО РАН члену-корреспонденту РАН Владимиру Васильевичу Васину.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

В §1 алгоритмы распараллеливания прогонки, предложенные А.Н. Коноваловым и H.H. Яненко 6'7 для решения задачи Дирихле для трехточечного разностного уравнения на отрезке, обобщаются для решения СЛАУ с трехдиагональными матрицами. В §2 построены параллельные алгоритмы решения СЛАУ с пятидиагональнымй матрицами. В §1 и §2 проведено

6Яненко H.H., Коновалов А.Н., Бугров А.Н., Шустов Г.В. Об организации параллельных вычислений и распараллеливании прогонки // Численные методы механики сплошной среды. Новосибирск: ВЦ и ИТиПМ СО АН СССР, 1978. Т. 9. № 7. С. 139-146.

7Бугров А.Н., Коновалов А.Н. Об устойчивости алгоритма распараллеливания прогонки // Численные методы механики сплошной среды. Новосибирск: ВЦ и ИТиПМ СО АН СССР, 1979. Т. 10. № 6. С. 27-32.

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

Исходный отрезок (0, п) разбивается на Ь интервалов распараллеливания (к, к + тп), к = 0,т,..., п — т так, что п = Ь • то (рис. 1). Точки разбиения отрезка к = 0, то,..., п выбираются в качестве узлов распараллеливания, а искомые неизвестные в узлах — в качестве параметров Уь Относительно Ук строится редуцированная система уравнений, после решения которой остальные искомые неизвестные находятся на Ь интервалах

независимо. |_|_|_|

0 т 2т - п

Рис. 1. Разбиение исходного отрезка на интервалы

Для решения систем уравнений с трехдиагональными матрицами

ад-ВД = ¿о, г — 0,

-ДЯ-г + ЗУ, - = Я, г = 1,2,... ,п-1, (1)

-л„у„_ 1 + спу„ = , г = тг.

редуцированная система уравнений относительно параметрических неизвестных Ук имеет вид исходной системы (1) с коэффициентами А¡, В;, С;, но меньшую размерность.

Построим параллельный алгоритм 1 для решения систем уравнений с пятидиагональными матрицами:

i^o , i = 0;

-ад + схух - dxy2 + ад = ¿ = 1;

aiyi-2 — вде-i + еде — A^i+i + eiyi+2 = я, * = 2.....

апуп-1 — вд-i + с„гп — dnyn+1 = F 1 П ) г = n;

д,-иУп-1 — дад+e„+iyn+i = ■Pn+1 , г = n + 1

(2)

Исходный отрезок (0, п +1) разобьем на L пересекающихся интервалов вида (&, к+т) и (к+1, к+т+1). к = 0, тп,..., п—т так, что п+1 — L-m+1 (рис. 2).

0 1 m m+1 2m 2m+l 3m 3m+l n-m n-m+1 n n+1

Рис. 2. Разбиение отрезка на пересекающиеся интервалы

Точки разбиения отрезка к, к + 1, к = 0,т,... ,п выберем в качестве узлов распараллеливания, а неизвестные в узлах Ук и — в качестве параметрических.

Для построения редуцированной системы уравнений введем оператор

дАу, = Агу_2 - + еде - яде« + дде+г 10

и на интервалах (к, к + т + 1), к = 0, т,..., п — m рассмотрим задачи

ahui = 0, uk = 1, £4+i = О, uk+m = 0, uk+m+i = О,

= Ук = 0, I4+i = l, 14+m = 0, V4+m+i = 0,

ДЛД = 0, А = 0, Pfc+1 = 0, Pfc+m = l, Ль+m+l = 0, (3)

AhQi = 0, Qk — 0, Qk+1 = 0, Qk+m = 0, Qk+m+i = li

AhWi = Fu Wk = 0, Wk+1 = 0, Wfc+m = 0, Wfc+m+i = 0,

где г = к + 2,..., к + т — 1.

Если Ui, Vi, Pi, Qi, Wi — решения задач (3) на (к,к + т + 1), то по принципу суперпозиции решение задачи (2) на (к, к + m + 1) будет иметь вид

Yi = YkUi + Yk+1Vi + Yk+mPi + Yk+m+1Qi + W4) (4)

где Yk, Yk+i, Yk+m, Yk+m+i — параметрические неизвестные.

После подстановки выражения (4) в точках к,к + 1, к = 0,т,... ,п в исходную систему уравнений (2), получим редуцированную систему уравнений относительно параметрических неизвестных следующего вида

_ _C0Y0 — D0Yi + E$Ym — H0Ym+i

—BiYQ + C\Y\ — D\Ym + Е{Ут+1 — 0 ■ Ym 0 • Yk-2m+i + AkYk~m - BkYk -m+1 + _ +CkYk — DkYk+ijf EkYk+m — HjXk+m+i

_ —Gi+lYi-m + Ak+lYk-m+l — Bk+\Yk+ Dk+iYk+m + Ek+\Yk+jn+\ — 0^Yk+2m 0 • Yn-2m+i + AnYn-m — BnYn_m+i 4- CnYn — DnYn+i —Gn+iYn-m + An+\Yn^m+i — Bn+{Yn + Cn+1Yn+1

где к = m, 2m,... ,n — m.

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

После вычисления параметров Yk и Yk+i остальные искомые неизвестные находятся в каждом из L интервалов распараллеливания независимо по формуле (4). Параллельный алгоритм 1 состоит из следующих шагов:

(3) - (5) (4)

Задачи (3) могут быть решены методом пятиточечной прогонки (формулы метода пятиточечной прогонки см. в работе 8).

Задача (5) решается методом семиточечной прогонки (вывод формул метода семиточечной прогонки приводится в §2 главы 1).

8 Самарский Л.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978. С. 97-99.

= Fp, = Fi,

= Fk' (5)

= Fj+ъ = JFn, = Fn+1 ,

Алгоритмы прогонки являются корректными и устойчивыми, если при вычислении прогоночных коэффициентов не происходит деления на нуль и для основных прогоночных коэффициентов выполняется неравенство |c*i| < 1, гарантирующее невозрастание погрешности ^ = щ — у» (см. 8,s).

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

Основной результат следующий.

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

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

Выпишем для системы трехточечных уравнений (1) достаточные признаки корректности и устойчивости метода решения системы — прогонки 9.

Признак А. ~ ~ j^j > 9, в > О, max{|Cfc|, \Ак\, \Вк\} > С > 0.

Признак В. IQj > |Aj| + |В;| + 5, ¿>0.

Справедливо следующее соотношение признаков: А —> В.

Теорема 1. Если для исходной системы уравнений (1) выполняются достаточные признаки корректности и устойчивости метода прогонки А или В, то в обоих случаях для редуцированной системы уравнений будут выполняться признаки А и В.

Далее рассмотрим систему с кусочно-постоянными коэффициентами на интервалах распараллеливания (к, к + т)

CoFo — Y\ = Fq ,

( -^-i + ИУ{ - QYi+i = Fi,

—Yk-i + CkYk — BkYk+i = Ft ,

~Y„-1 + CnYn — Fn ,

3Годунов C.K., Рябенький B.C. Разностные схемы. M.: Наука, 1977. 439 с.

г = 0,

г = fc + 1,... + m - 1, к = т,2т, ...,п — т, i = п.

В системе (6) все уравнения поделены на один из коэффициентов.

Теорема 2. Если коэффициенты исходной системы (6) удовлетворяют следующим условиям: 1. а) |Д| > |Q| + 1 + <5, ¡5 > 0;

Ь) |С0|>1шш |Со| < щ - <5', г<?е 5' ^ ;

2. a) Вк и Q имеют одинаковые знаки и \Ск\ < 1^-ilSl

одно из неравенств - строгое, тогда для редуцированной системы уравнений выполняется в случае а) условие строгого диагонального преобладания матрицы системы: \Ck\> \Ak\+\Bk\+S, 5 — 5i~6'-\Bk\, ii — jfsj; в случае b) условие нестрогого диагонального преобладания матрицы системы: \Ск\ > |At| + \Bk\, и она решается методом обычной прогонки, причем решение устойчиво.

Следствие. Если ни одно из условий 2 теоремы 2 не выполняется, то редуцированная система уравнений при \Ск\ < \Вк\ + 1 решается методом немонотонной прогонки.

Теорема 2 обобщается на случай кусочно-постоянных коэффициентов Rk+m и Qk+m на интервалах распараллеливания (к, к + т).

Достаточные признаки устойчивости для системы (2) располагаются в порядке ослабления следующим образом:

Признак А. \С{\ > M + IBil + IAl + l^il + i, S > 0. Признак В: 1. |С;| > Щ + + Щ + S, S > 0; или 2. \Ci\ > |Aj| + |Д| + \Ei\ + 5,. â>0,

где а==тах{|Д|,|С;|,|Д|}. Признак С. \Ci\ > )Ai) + \Et) + 5, à > 0.

Справедливо следующее соотношение признаков: Л —► В —> С. Достаточные признаки устойчивости для системы (5) имеют вид

Признак Â: 1. |Cfc| > Й*| + \Вк\ + \Dk\ + \Ёк\ + \Нк\ + 5, ¿>0;

И 2. |Cfc+l| > |Gfc+l| + + \Вк+\[ + |Â;+l| + |ï?i:+l| + 6, ô>0.

Признак В: 1. \Ck\ > \Ak\ + |Bfc| + |lfc| + \Hk\ + S, 5> 0; и 2. |Ck+i| > |Gfc+i| + p4fc+i| + \~Dk+i\ + ¿>0.

ПризнакС: 1. |С*| > + \Щ + \Нк\ + S, ô > 0; и 2. |C,t+i| > IGi+il + |Afc+i| + |Êfc+i| + 5, 5>0.

Справедливо следующее соотношение признаков: А —> В —*■ С. Теорема 3. Имеют место следующие соотношения признаков: А -> А; В{ 1) А{2) и В{ 1); В{2) и В{2); С -» С.

Для системы пятиточечных уравнений с постоянными коэффициентами 5, Р, Л, <5, Т во внутренних точках интервалов распараллеливания (к, к+т+1), к = 0, то,..., п — т

СоУо-ад + ад = «= 0; -ВД + ОД- АГ2 + ВД = л, ¿ = 1; ЙУм-РЯ-а + ДИ-дУш+ТПьг = ^ ,

г = к+2,.. ,,к+тп-1; ( .

к — т, то+1,.. .,п—ш+1; А-пУп-2 — ВпУп-г -1- С„У„ — £)пУп+1 = Рп , г = п; -4п+гУг-1 ~ Вп+1Уп + Сп+хУп+х = , 1=п + 1;

имеет место следующая

Теорема 4. Если коэффициенты системы (7) удовлетворяют условиям:

1.о) |д| > |5| + |р| + |в| + |г| + г, ¿>о, д2< |рд(р + д)|;

6) 5, Р, Д, <2, Т одного знака; Ак, Вк, Ок) Ек одного знака; 2. а) при \Вк\ < |Ак\, |Дь+1| < |Я*+г|,

\Ск\ + \Ик\ < + |Я*||; \СМ\ + < + ;

или Ъ) при > 1.4*1, \Ок+1\ > 1^+11,

|С*| + < |Л|| + ; \Ск+1\ + \Вк+1\ < \Ак+1^\ + \Ек+1^\;

или

с.) при |Вк\ < > \ЕМ\,

|С*| + |Л*| < |В*|| + )Ек^\; \Ск+1\ + \Вк+1\ < \Ак+1^\ + ; или й) при |Вк| > 1Л1, |Ат| < \Ек+1\,

|С*| + |Аь| < |4=|| + |Як||; |С*+1| + \Вк+1\ < \Ак+1^\ + ,

тогда для системы (5) выполняется условие диагонального преобладания матрицы системы, т.е. имеет место признак А :

\ск\ > И + \Щ + \Щ + + \Нк\ + 6, 14

\Ск+х\ > IGn.ll + \АШ\ + IBjh.iI + I Ат! + \ЕЫ\ + 5, 5 > 0;

и она решается методом прогонки, причем решение устойчиво.

Параллельный алгоритм 2 отличается от алгоритма 1 тем, что в узлах разбиения отрезка задаются произвольные значения параметров. В результате исходная задача разбивается на независимые подзадачи с заданными краевыми условиями. Искомые значения в узлах находятся в явном виде.

Построим параллельный алгоритм 2 для системы пятиточечных уравнений вида

'АЖ-2 ~ ВК-г + ОД - ДУШ + ЕК+г = Д,

(8)

Уо = -Рсь = -Рь Уп = К, Уп+1 = Рп+ъ г = 2,..., п — 1.

Отрезок (0, п+1) разобьем на 2(1—1) пересекающихся интервалов вида (0, к + 1) и (к, п + 1), к — т, 2т, ...,п-т (рис. 3).

О 1 ш ш+1 2т 2т+1 • • • п п+1

Рис. 3. Разбиение отрезка на пересекающиеся интервалы

Точки разбиения отрезка к, к + 1 выберем в качестве узлов распараллеливания. Зададим в них произвольные значения Ук°, В результате задача (8) разбивается на 2(Ь - 1) независимую подзадачу с краевыми условиями Р0, Р„, Р„+1.

Для фиксированного к на интервалах (0, к + 1) и (к, п + 1) имеем две независимые краевые задачи, после решения которых находятся У£_2,

и Ук+2> П+з-

Далее на отрезке (к — 2, к + 3) решаем задачу А^У-!3 = ук-2 = ук-21 П-1 — ук-ъ ук+2 ~ ук+2' ук+3 = ук+3> * = ^

(9)

Значения (9) в точках к, к + 1 берем в качестве новых краевых условий

П'.С.ит-Д.

Будем иметь У°, У,1, ■ ■ • -> У,*, У°+1, Ук\• ■ • -> УДГ Искомые решения У^, получим в явном виде. Записывая (9) в точках к, к + 1, имеем систему из двух уравнений с двумя неизвестными У/ и УД.1 для каждого к, которую представим в векторной форме

РУ1 =ЛУ° + В. (10)

Если определитель системы (10) |Д| ф 0, то матрица Р обратима и

у^б^ + Д с = р~1-Л, 1) = р-1-в.

15

Для произвольного У имеет место представление

5-1 3=0

Теорема 5. Если для исходной системы (8) выполняется условие:

\Ск\ > \Ак\ + \Вк\ + \Бк\ + \Ек\ + 5, 6 > О, (И)

2

тогда |Д| = \СкСк+1-Вк+гВк\ ф 0; ||6|| = тах ^ < 1 и искомое решение записывается в явном виде

. Т = Ит Уй - (Е - б)-1 ■ Ъ. (12)

Рассмотрим систему пятиточечных уравнений с постоянными коэффициентами 5, Р, Я, <5, Т во внутренних точках интервалов распараллеливания следующего вида

' ЗУ^г-РУ^+Д^-ОУш+ТЯ+г = Я, » = 2,..к-1, А:+2,..п-1,

- + СЛ - + №+2 - Р]ь,

М+\Ук-\ — Вк+\Ук + Ск+{Ук+1 — Пк+хУк+2 + Ек+{Ук+3 — Ек+1,

Уо = У\ = Уп = У„+1 =

(13)

Нас будет интересовать случай, когда в изолированных точках системы к и к + 1 нарушается условие (11), т.е. имеет место

|С)е| < |А);| + \Вк\ + |А;| + |£?*с|.

Теорема 6. Если коэффициенты системы (13) удовлетворяют условиям:

1. |Д| > |5| + |Р| + |д| + |Г| + 5, 6 > О, > |Г| и 5, Р, Я одного знака;

тогда выполняются условия обоснования метода

|Д| = |С*А+1 - Дн-гА! Ф о, ||£|| = тах < 1 и решение

1<г<2

3=1

системы (Ю) сходится к искомым У£, У£+1 и имеет вид (12).

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

{ СвУо-Во?! = ¿ = 0,

( -АЯы + С^-ВСУм = г = 1,2,... — 1, (14) [ -У1Л-1 + СЛ = Рм , г =

где У,- — искомые векторы размерности п, Рг — заданные векторы размерности п, А{, В{, С{ — квадратные матрицы порядка п.

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

Будем предполагать, что исходная область Р представляет собой прямоугольник. При построении параллельного алгоритма исходную область Р разобьем на Ь подобластей вертикальными линиями так, что М=ЬхМ. В качестве параметрических неизвестных выберем векторы У к, К = 0, М,..., Ы, связывающие неизвестные на сетке по вертикали.

Относительно У к строится редуцированная система уравнений. В подобластях, определяемых интервалами (К, К + М), рассматриваются следующие задачи:

' -а-ии + СД1 - вги)+1 = 0 , и\ = (10...0) , и1к+м = (00...0),

+ су] - В0ГМ = о, Щ = (оо...1), ТРК+М = (оо...о),

(13)

+ С{у] - = 0 , = (00...0) , Ухк+М = (10...0), < .................................

+ = 0, Р£ = (00...0), = (00...1),

_____ _ (16)

{ + - В№+1 = Р1, у/к = (00...0) , \Ук+м = (00...0),

(17)

где г = К +1,..., К + М - 1.

Теорема 7. Если ии... ,и{ — решения задач (15), — ре-

шения задач (16), IV( — решения задач (17), а У{ — решения исходной задачи (Ц) на (К,К+М), тогда

У; = (и]и■ .. .1П)УК + (У]У-. ..У^)УК+М + (18)

После подстановки соотношений (18) в точках К = О, М,..., N в исходную систему (14) получим систему уравнений относительно параметрических неизвестных — векторов У к- Эта система уравнений по своей структуре аналогична (14), имеет меньшую размерность и следующий вид:

' [Со - ВД]Уо - [ВД]УМ = ^о + , _ К = О,

-{Акик^]Ук^мЦСк^АкУк-х-Вкик+1}Ук-[ВкУк+1}Ук+м =

к -[Анин-1]УК-м + [Сц - = + ВЦУГЦ-!, К = И,

(19)

где Vк пУк — матрицы размерности п хп.

Задача (19) решается классическим алгоритмом матричной прогонки на одном процессоре. Задачи (15)—(17) решаются независимо на Ь интервалах распараллеливания на Ь процессорах. После вычисления параметров У к остальные искомые неизвестные находятся по формуле (18) также независимо на каждом из Ь интервалов на Ь процессорах.

Схема параллельного алгоритма матричной прогонки 1 имеет вид:

(15) - (16) - (17) ^ (19)- (18). Теорема 8. Если для исходной системы (14) выполняется условие ||С4||>||4|| + ||£?4||+«, 5>0, тогда для системы (19) имеет место

I\СК ~ АкУк-1 - Вкик+1Ц > \\Акик^\\ + \\ВкУк+1\\ + 5.

Теорема 9. Если для системы (14) выполняются достаточные условия устойчивости метода матричной прогонки по А.А. Самарскому

НС^ВЬП < 1, ЦС^ЛлгН < 1, Н^гЧН + НС^Д-Ц < 1, г = 1,...,ЛГ-1,

причем хотя бы одно из неравенств - строгое, то эти же условия достаточны и для устойчивости метода матричной прогонки при решении системы уравнений (19) относительно параметров У к-

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

ДУ1 = ~Ёи Уо=^о, (20)

ЛУг - + С,У* - ДУ.+1, * = 1,.., N - 1,

где У{ - искомые векторы размерности п; - заданные векторы размерности п; А{, В{, С{ - матрицы размерности пхп.

Исходную область разобьем на Ь - подобластей (рис. 4).

Рис. 4. Схема разбиения области для Ь — 3

Зададим на границах подобластей произвольные значения векторов У1М] I= 1,..., 1,-1. В результате задача (20) разбивается на 2(1- - 1) независимых подзадач с краевыми условиями Р.у, Ущ-> а именно:

I= 1°=Р(Ь =*=м~1;

(21)

[ЛУ- = Р,-, у\м = У°2М, У*„ - ¿V, г = 2М + 1,^ - 1;

Г/Й^"5 = У^"5 - То, уТ-м = У^-АГ, * = 1, ^ - М + 1; [ЛУ^""4 = Гг, У^ = П-л, ^Г = г — N — М + 1,.., Ж

Решая задачи (21), найдем

V1 V2 V4 V5 у3£"5

Г М-1! г М+1> 1 2м~ъ 1 2М+1) — > г ЛГ-ЛГ-И 7

Далее в подобластях, определяемых интервалами (М—1, М+1), (2М-1, 2М+1),..., (М-~М-1, ЛГ-М+1), решаем сеточные задачи

ДУ м = Рм, У м-1 ~ У м-ъ У м+1 ~ Ум+Ь

^у 2м — р2м, УгМ-1 = ^2М-1) у2м+1 ='^2М+1> (22)

. . . ш н_м = г ц-м, i н-м-1 = * ат-м-и i n-м+1 =

значения которых в точках М,2М,...,Ы — М возьмем в качестве новых

краевых условий Уш; / = 1,..., Ь — 1 для задач (21), и т. д. _0 _1 _2

Последовательность У1М, Угм, Уш> •■• сходится к искомым решениям Уг*м на границах Ь - подобластей для задачи (20).

Наиболее экономичным алгоритм является в случае разбиения исходной области на две подобласти для N -2 - М. Тогда задача (20) разбивается

— —0 —Ч) — на две подзадачи вида (21) с краевыми условиями -Ро> Ум и Ум->

В случае Ь = 2 по принципу суперпозиции решения в подобластях определяются следующим образом:

Yi = UiFti + ViFM + Wi, г = 1,..., M — 1; (23)

Yi = UiY*M + VFN + Wh i = M+l,..., N — 1; где матрицы Ui, V* и вектор Wj — решения задач (15)—(17), Y*M - искомое решение на границе подобластей. Для произвольных Yм имеет место

j=o

Теорема 10. Если для системы (20) выполняются достаточные условия устойчивости метода матричной прогонки по A.A. Самарскому

HC^Boll < 1, IlC^AvIl < 1, WCr'AiW+WCr^BiW < 1, ¿ =

причем хотя бы одно из неравенств - строгое, тогда ||<5|| < 1 и неизвестные на границе подобластей имеют вид

Y*M= lim TM = (E-Q)'lP, (24)

n—»00

где матрица Q и вектор Р вычисляются по формулам

Q = C^AmVM-I + С7}Вмим+ъ (25)

Р = CmAMPmFo + WM-i] + Cm1Bm[Vm+1Fn + WM+1] + C^FM.

§4 иллюстрирует применение алгоритмов распараллеливания прогонки при распараллеливании двумерных сеточных задач. Подход к распараллеливанию сеточной задачи Дирихле для уравнения Пуассона в прямоугольнике, предложенный в работе 10, применяется при решении двумерной краевой задачи для бигармонического уравнения. При помощи Р— трансформации векторов задача сводится к п системам скалярных пятиточечных уравнений, алгоритмы распараллеливания которых рассмотрены в §2. При разбиении исходного прямоугольника на подобласти Р— трансформацию векторов можно выполнять в каждой подобласти независимо и вычислять при помощи алгоритма быстрого преобразования Фурье (БПФ).

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

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

10Коновалов А.Н., Бугров А.Н., Блинов В.В. Алгоритмы распараллеливания сеточных задач // Актуальные проблемы вычислительной и прикладной математики. Новосибирск: Наука, 1979. С. 95-99.

11 Столяров Л.Н., Абрамов В.М. Организация параллельных вычислений, учитывающая особенности вычислительной системы // Комплексы программ математической физики. Новосибирск: ВЦ и ИТиПМ СО РАН, 1980. С. 250-262.

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

В §2 рассматриваются способы распараллеливания метода разделения переменных (МРП) решения сеточной задачи Дирихле для уравнения Пуассона в прямоугольной области и проводится анализ эффективности распараллеливания.

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

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

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

Получена теоретическая оценка эффективности параллельного МРП с учетом времени межпроцессорных обменов

Е__(3^+^ + 2)^ + ^_

где N — число узлов квадратной сетки; tc,ty,td — времена выполнения арифметических операций сложения, умножения и деления, соответственно; т — число процессоров, равное числу подобластей; Т0 = 16— время для выполнения обменных операций, Ъ — время, необходимое для пересылки элемента данных из одного процессора в другой.

Обозначим t = Тогда для МВС-1000 (в грубом приближении) можно полагать ty ^ ~ 10 ¿0 ~ 5001 и оценка (26) принимает вид

&__(Ш + Щг

т ~ (4ЛГ + 20 + 15ТО/ЛГ) 4 + 16т «0/ЛГ ' ^ '

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

Р2__(З + б/АГ)*_

т ~ (6 + 9/^ + 3 туЫ + 6 т2/^2) 4 + (4/ЛГ + 6/ЛР) и' К '

Построены графики изменения эффективности Е^ параллельного МРП и графики Е^ параллельного алгоритма матричной прогонки в зависимости от числа процессоров ш для МВС-1000. Оценки и графики подтверждаются численными экспериментами.

В табл. §2 приведены приведены времена счета на МВС-1000 и коэффициенты ускорения и эффективности решения модельной задачи Дирихле с помощью последовательного и параллельного МРП для 1000 х 1000 точек сетки и сравнение с параллельным алгоритмом Гаусса-Зейделя.

МРП существенно сокращает время счета (на несколько порядков) при высокой эффективности распараллеливания 0.94 < Е}п < 0.98.

В табл. §3 приведены времена счета на МВС-1000 и коэффициенты ускорения и эффективности решения СЛАУ с блочно-трехдиагональными матрицами размерности 30000 х 30000 (блоки размерности 25) с помощью последовательного и параллельного алгоритма 1 матричной прогонки. Для числа процессоров т < 15 имеем достаточно высокую эффективность распараллеливания 0.75 < Е^< 0.78.

В §4 рассматривается решение задач многокомпонентной диффузии с помощью параллельного алгоритма матричной прогонки.

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

дт г<дг{г 2^и«дг)>

где N — число компонентов сплава; г — пространственная координата; С^ — концентрация з~то компонента; — парциальные коэффициенты взаимной диффузии; q — показатель степени, зависящий от симметрии задачи: 0 — для плоской, 1 — для цилиндрической, 2 — для сферической.

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

£ [аЩ(к -1) + + цкс^к +1)] = 4, (30)

7=1

где а\к, Ь-к,с-к, й\к — коэффициенты, рассчитываемые в зависимости от модели, С](к) — концентрация 3-го компонента в к-и узле сетки.

На МВС-1000 решена тестовая линейная задача о диффузионном насыщении плоской металлической пластины (0,1) единичной толщины с ну-

левой начальной концентрацией Cf компонентов и граничными условиями 1-го рода (на левом конце пластины) и 2-го рода (на правом) тремя компонентами с различной диффузионной подвижностью.

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

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

Рассматривался сплав, состоящий из нескольких компонентов, в котором сосуществуют две фазы в твердом состоянии: основная фаза и частицы другой фазы, выделившиеся в результате некоторой предыдущей термической обработки. Для расчетов использовалась пошаговая процедура: на основании радиусов частиц и распределения концентраций в текущий момент t эти параметры пересчитывались для следующего шага по t. Система не является линейной, т.к. на каждом шаге коэффициенты диффузии Д-j зависят от концентраций в каждой ячейке.

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

Третья глава посвящена параллельным алгоритмам решения трехмерных обратных задач гравиметрии и магнитометрии.

Одной из важнейших моделей строения земной коры является модель горизонтальной слоистой среды. В §1 рассматривается линейная обратная задача гравиметрии о нахождении переменной плотности а — сг(х,у) в горизонтальном слое П = {(x,y,z) е R3 : {х,у) е D, Hi < z < ff2}, где Hi, И2 — константы, либо криволинейном слое П1 = {(x,y,z) € R3 : {х,у) е D, Н\(х,у) < z < Н2(х,у)} по гравитационным данным, измеренным на площади D — {(х,у) е R2 : а < х < Ъ, с < у < d} земной поверхности. Используется априорная информация об отсутствии аномалий плотности вне слоя с криволинейными границами Hi = Hi(x,y) и Я2 = Н2{х,у) такими, что Hi < Н2 V(x, у), и выполняется условие Щ(х,у) hi = const. При этом предполагается, что распределение

V—foo

плотности а = а(х, у) внутри слоя не зависит от z (ось z направлена вниз).

Решение задачи разбивается на два этапа. На первом этапе необходимо выделение из измеренного гравитационного поля аномального поля от

исследуемого слоя. Выделенное аномальное поле служит правой частью базового интегрального уравнения первого рода относительно искомой плотности. Методика выделения аномального поля предложена П.С. Мартышко и И.Л. Пруткиным в работе 12 и сводится к последовательному решению трех задач: решению задачи Дирихле для уравнения Лапласа на всей границе или части границы исследуемой области для исключения боковых источников поля, вычислению интегрального оператора для пересчета поля вверх и решению двумерного интегрального уравнения первого рода для пересчета поля вниз для исключения глубинных источников.

Второй этап связан с решением линейного двумерного интегрального уравнения Фредгольма первого рода для нахождения искомой плотности 13 ь 4

1

Аа

И{[[х-х'

)2 + {у-у')2 + Н2{х',у')]^

а с

1

¡}а&,1/)1и<11/ = Ь9{х,у), (31)

\(х — х')2 + (у — у')2 + у')]1!2.

где / — гравитационая постоянная, &д{х, у) — гравитационный эффект, порождаемый источниками в горизонтальном или криволинейном слое.

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

{А + аЕ)г = 6, (32)

где а — параметр регуляризации.

В случае криволинейного слоя исходная матрица СЛАУ несимметрична, поэтому СЛАУ предварительно преобразуется к виду (схема Тихонова)

(АТА + а'Е)г = АТЬ, (33)

где Ат — транспонированная матрица, а' — параметр регуляризации.

Для решения уравнений (32) и (33) используются регулярные итерационные методы градиентного типа: метод минимальных невязок, метод

и Мартышко П.С., Пруткин И.Л. Технология разделения источников гравитационного поля по глубине // Геофизический журнал. 2003. Т. 25. № 3. С. 159-168.

13Мартышко П.С., Кокшаров Д.Е. Об определении плотности в слоистой среде по гравитационным данным // Геофизический журнал. 2005. Т. 27. № 4. С. 678-684.

наискорейшего спуска, метод минимальной ошибки и метод простой итерации (МПИ) в виде 14

= _ —[(Л + aE)zk - 6], (34)

Лтпах

где Хтах — максимальное собственное значение матрицы A -f аЕ (симметричный случай), и прямой метод квадратного корня (МКК) для решения СЛАУ с симметричной положительно определенной матрицей. Условием

\\Azk - Ь|| /

останова итерационных процессов является следующее: —рц—11 < е.

Численная реализация и распараллеливание регулярных итерационных методов и МКК для решения линейной обратной задачи гравиметрии (31) выполнены на МВС-1000 с помощью библиотеки MPI на языке Фортран.

Распараллеливание итерационных методов градиентного типа основано на разбиении матрицы А горизонтальными полосами на m блоков, а вектора решения -г и вектора правой части Ь СЛАУ на m частей так, что п = m х L, где п — размерность системы уравнений, m — число процессоров. На каждой итерации каждый из m процессоров вычисляет свою часть вектора решения. В случае умножения матрицы А на вектор z каждый из m процессоров умножает свою часть строк матрицы А на вектор z. В случае матричного умножения АТА каждый из m процессоров умножает свою часть строк транспонированной матрицы Ат на всю матрицу А. Host-процессор отвечает за пересылки данных и также вычисляет свою часть вектора решения. Для метода (34) максимальное собственное значение Хтах матрицы А + аЕ находится с помощью степенного метода с использованием параллельного алгоритма умножения матрицы на вектор.

Распараллеливание метода квадратного корня основано на разбиении матрицы А вертикальными линиями на m блоков. Диагональные элементы треугольной матрицы S (А = S^S) вычисляются на одном процессоре и рассылаются каждому процессору. Затем каждый из m процессоров вычисляет свою часть недиагональных элементов матрицы S. Обратный ход метода квадратного корня (нахождение решения СЛАУ) по рекуррентным формулам также выполняется на одном процессоре.

При реализации методики выделения аномального поля на МВС-1000 на этапе решения задачи Дирихле используется описанный во второй главе параллельный метод разделения переменных в двух вариантах либо параллельный вариант метода Гаусса-Зейделя; на этапе пересчета поля вверх при вычислении интегрального оператора используется параллельный алгоритм умножения матрицы на вектор, на этапе пересчета поля вниз при

14Васин В.В., Еремин И.И. Операторы и итерационные процессы Фейеровского типа. Теория и приложения. Екатеринбург: УрО РАН, 2005. 210 с.

решении интегрального уравнения используются регулярные параллельные итерационные методы градиентного типа.

В §1 приводятся результаты численных расчетов решения задач о восстановлении плотности в слое на МВС-1000 для реальных данных, измеренных в некоторых областях района Среднего Урала. На рисунках представлены линии уровня и распределение аномального поля, выделенного из исходного по методике предварительной обработки данных, а также линии уровня и распределение восстановленной плотности в слое. В таблицах приведены время счета, коэффициенты ускорения и эффективности параллельных алгоритмов. Эффективность распараллеливания является высокой: 0.7 < Ет < 0.9. Результаты решения задач переданы в ИГФ УрО РАН для геофизической интерпретации.

При решении аадачи о восстановлении плотности в слое с помощью параллельных алгоритмов на МВС-1000 матрица СЛАУ большой размерности (порядка 40000) формируется и хранится в памяти каждого процессора по частям, что дает эффективность распараллеливания Ет> 1.

В §2 описывается разработанный совместно с Д.В. Гемайдиновым специализированный Web-cepBep, предназначенный для запуска программ, реализующих параллельные алгоритмы решения линейной обратной задачи гравиметрии на МВС-1000 через Web-интерфейс.

Комплекс параллельных алгоритмов для решения обратной задачи гравиметрии о нахождении переменной плотности в слое размещен на специализированном Web-cepeepe, установленном в ИММ УрО РАН.

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

1. Рассматривается трехмерная структурная обратная задача гравиметрии о восстановлении поверхности раздела между средами по известному скачку плотности и гравитационному полю, измеренному на некоторой площади земной поверхности. Предполагается, что нижнее полупространство состоит из двух или трех слоев постоянной плотности, разделенных искомыми поверхностями 5\ и 5г. В предположении, что гравитационная аномалия создана отклонением искомой поверхности S от горизонтальной плоскости z — Н (ось z направлена вниз), в декартовой системе координат функция z = z(x,y), описывающая искомую поверхность раздела, удовлетворяет нелинейному двумерному интегральному уравнению Фредгольма первого рода ь d

A[z) = fAa JJ {[(i _ x,)2 + {y_ *,)2 + ^ y,)]1/2 - (35)

где / — гравитационная постоянная, Аа — скачок плотности на границе раздела сред, G(x, у) — аномальное гравитационное поле, z = Н — асимптотическая плоскость для данной геологической границы.

2. Рассматривается трехмерная структурная обратная задача магнитометрии по численному восстановлению разделяющей поверхности сред на основе данных о магнитном поле, измеренном на некоторой площади земной поверхности, и скачке вектора намагниченности. Функция 2 = z(x,y), описывающая искомую поверхность раздела, удовлетворяет нелинейному

двумерному интегральному уравнению Фредгольма первого рода ъ d

В[А - ж')2 + + ~ (36) - [(;с_^2 + (уЯ_г/02 + Я2]3/2} = G1(?,y),

где A J — скачок вертикальной компоненты вектора намагниченности, Gl(x,y) — аномальное магнитное поле, обусловленное отклонением искомой поверхности от асимптотической плоскости z = —Я.

Предварительная обработка гравитационных либо магнитных данных, связанная с выделением аномального поля, выполняется по методике 12.

Уравнения гравиметрии и магнитометрии (35) и (36) являются существенно некорректными задачами.

После дискретизации уравнений (35) и (36), на сетке п = М х N, где заданы правые части G(x,y) и Gl(x, у), и аппроксимации интегральных операторов Л и В по квадратурным формулам имеем системы нелинейных уравнений

An[z] = Fn. (37)

Для решения систем уравнений вида (37) используется итеративно ре-гуляризованный метод Ньютона 15

zM = zk- [.A'n(zk) + ак1\-1(Ап&) + akzk - Fn). (38)

Здесь An{zk) и Fn — конечномерные аппроксимации интегральных операторов и правых частей в уравнениях (35)—(36), A'n(zk) — производная Фреше операторов А либо В в точке zk, I — единичный оператор, ак — последовательность положительных параметров регуляризации.

Нахождение очередного приближения zk+1 по найденному zk сводится к решению СЛАУ

Akzk+1 = Fk, (39)

где А£ = А'п(гк)+ак1 — плохо обусловленная несимметричная заполненная пхп матрица, Fk = Akzk — (An(zk) + akzk — Fn) — вектор размерности п.

15Bakushinsky A., Ooncharsky А. Ш-Posed Problems: Theory and Applications. London: Kluwer Akad. Publ., 1994. 256 p.

Обратимость матрицы А'п{гк) + ак1 контролируется вычислением ее спектра. При исследовании спектра матрицы тщательный анализ показал, что для всех гравитационных и магнитных данных на каждой итерации метода Ньютона матрица имеет п различных неотрицательных собственных значений. Это позволяет проводить регуляризацию сдвигом и использовать метод (38). В реальных расчетах решается регуляризованное уравнение

Ап[г] + аг = а > 0, (40)

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

Численные расчеты, выполненные для модельных и реальных данных, показали, что при решении задач (35), (36) методом Ньютона приближенные решения дают вполне хорошую точность по невязке.

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

В §3 проведены основные этапы доказательных вычислений, связанные с анализом сходимости метода Ньютона при решении обратной задачи гравиметрии. Идея доказательных вычислений принадлежит К.И. Бабенко 17 и заключается в том, что при подходящем начальном приближении проверяются численно все условия теоремы Ньютона-Канторовича с оценкой допускаемой погрешности, и при их выполнении делается вывод о сходимости метода. При проведении доказательных вычислений предполагается, что погрешность округления при вычислениях со стандартными типами данных на ЭВМ меньше необходимой, гарантирующей сходимость метода.

В первом варианте доказательных вычислений реализована следующая стратегия проверки условий теоремы Ньютона-Канторовича18 (теорема 1).

За решение 2* принималось либо вектор, описывающий модельную (синтетическую) поверхность раздела, либо, в случае реальных данных, вектор г, полученный в результате к шагов метода Ньютона (38) при условии, что вектор задает достаточно хорошее приближение по невязке для задачи (40): \\Апгк - в\\ < е.

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

16Васин В.В., Агеев А.Л. Некорректные задачи с априорной информацией. Екатеринбург: Наука, 1993. С. 216-218.

17Бабенко К.И., Петрович В.Ю. Доказательные вычисления в задаче о существовании решения удвоения // ДАН СССР. 1984. Т. 277. №2. С. 265-270.

Бахвалов Н.С. Численные методы. М.: Наука, 1973. С. 412.

Условия теоремы 1 проверялись при решении задачи с реальными данными и задачи с квазимодельным решением для области S : 50 х 60 км2, hx = 0.5 и hy = 2 км — шаги сетки, Аа = 0.5 г/см3 — скачок плотности на поверхности раздела, / = 6.67 • Ю-8 см3/г • см2 — гравитационная постоянная, Н = 5 км. Синтетическое гравитационное поле G(x,y) определялось путем решения прямой задачи гравиметрии (35) для некоторой исходной поверхности раздела с добавлением случайного шума 5%, заданной формулой z(x, у) = 5 + (4/тг) arctg(2z/5 - 10) + sin(7ry/30).

Утверждение 1. Пусть Zi = z* — точное решение уравнения F(z) = A[z] — G(x, у) =0, z2 — zk— приближенное решение уравнения F(z) = A[z]—G(x,y)+az = 0 методом Ньютона на к-ой итерации. Тогда при выборе zc € (0.1, Н + Н/2) и подходящем выборе параметра регуляризации а имеем значения констант a = max||sfc-**||, аг(к) = l/\/Amin((Л*)^), а2(к) =

c_1=max{(ai(A;)-a2(A;))""1}, Ь = min(a, с-1),

при которых условия теоремы Ньютона-Канторовича 18 :

1) Н^'Сг)-1!! < oi при z€üa = {z-. \\z-z*\\ <а};

2) \)F(z1)-F(z2)-F'(z2)(z1-z2)]\<a2)\z2-z1\)2 при zuz2eÜa; выполнены в итерационных точках при 0 < к < к и справедлива

оценка погрешности ||zk — z*|| < с-1 (с- ||z° - £*||)2t (*).

Замечание. При z° = Я справедлива оценка ||Я — z*|| = ||z° —z*|| < b. Во втором варианте доказательных вычислений на основе теоремы Ньютона-Канторовича Х9'20 (теорема 2) показано, что при некотором начальном приближении выполнены все условия теоремы 2 для уравнения с квазимодельным решением, что позволяет сделать вывод о сходимости метода Ньютона с соответствующей оценкой погрешности.

Утверждение 2. Условия теоремы Ньютона-Канторовича 20 ;

1) НПгоЩ < то, НПгоГ^ЫН^о;

2) \)F'(zi)-F'(z2)\\ <N2\\z1-z2\\ Vzuz2eB(z*,R); •Vi „ ^ 1.. l-y/l-2morjoN2 <

3) --< Я,

выполняются при выборе начального приближения z°, достаточно близкого к точному решению и для z*£B(zq,R) справедлива оценка погрешности ||z* — zq|| < (Этот^Л^)2") n — 0,1,... (**). Для задачи гравиметрии получена аналитическая оценка: N2 < /Да ■ (Ь - о)1^2 • (d - с)1/2 ■ 2fz3{x, у).

19Канторович Л.В., Акилов Г.П. Функциональный анализ. М.: Наука, 1977. С. 680.

'мБакушинский А.Б., Кокурин М.Ю. Итерационные методы решения нерегулярных уравнений. М.: ЛЕНАНД, 2006. С. 14.

Численная реализация и распараллеливание алгоритмов решения нелинейных обратных задач гравиметрии и магнитометрии о нахождении поверхности раздела между средами выполнены на МВС-1000 с помощью библиотеки MPI на языке Фортран.

На каждом шаге итеративно регуляризованного метода Ньютона для нахождения очередного приближения необходимо решение СЛАУ (39) с плохо обусловленной заполненной несимметричной матрицей.

Для решения СЛАУ используются регулярные параллельные варианты итерационных МПИ (34) и метода сопряженных градиентов (МСГ) 21 для СЛАУ с симметричной матрицей, а также регулярные параллельные варианты прямых методов Гаусса и Гаусса-Жордана.

В случае применения итерационных методов система уравнений (39) предварительно приводится к виду

Bkzk+l = {{Акп)тАкп + a'kI\zk+i = (Ak)TFk = b, (41)

где (Ак)т — транспонированная матрица, а'к — параметры регуляризации.

Распараллеливание метода сопряженных градиентов проводится по описанному выше принципу распараллеливания итерационных методов.

Распараллеливании методов типа Гаусса основано на том, что на каждом шаге каждый из m процессоров исключает неизвестные из своей части L уравнений. Host-процессор выбирает ведущий элемент среди элементов строки, модифицирует строку и рассылает ее остальным процессорам. При реализации процесса исключения Гаусса (матрица СЛАУ приводится к верхнетреугольной) все большее число процессоров постепенно начинает простаивать, т.к. с каждым шагом число уравнений СЛАУ уменьшается на единицу. Это уменьшает эффективность распараллеливания. При реализации метода Гаусса-Жордана (матрица СЛАУ приводится к диагональной) все процессоры выполняют вычисления со своей частью уравнений до конца и эффективность распараллеливания увеличивается.

В §3 приводятся результаты численных расчетов решения нелинейных задач гравиметрии и магнитометрии на МВС-1000 методом Ньютона для реальных гравитационных и магнитных полей, обработанных в различных областях (Средний Урал, Казахстан, Оренбург и Башкирия). Измерения и обработка гравитационных и магнитных полей выполнены сотрудниками ИГФ УрО РАН. На рисунках представлены восстановленные поверхности раздела. Проведен анализ эффективности и ускорения параллельных алгоритмов, которые уменьшают время решения задач. Результаты решения задач переданы в ИГФ УрО РАН для геофизической интерпретации.

21 Фаддеев В.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. М.: Гос. издат. физ. -мат. лит., 1963. 735 с.

Четвертая глава посвящена распараллеливанию алгоритмов решения трехмерной задачи упругости и упруго-пластической задачи.

В §1 рассматривается решение статической задачи упругости методом граничных интегральных уравнений. Требуется найти решение системы уравнений Ламе в конечной трехмерной области D, ограниченной кусочно-гладкой поверхностью S:

+ + = ¿ = 1,2,3; (42)

;=1 3 Я2 Я2 я2 А, ц — константы Ламе, Д ~ + + тгЧ .

C/Xj ¿'^З

Используется непрямой вариант метода 22, когда интегральное уравнение на границе области решается для некоторой вспомогательной функции, по которой определяется решение исходной задачи (компоненты вектора смещений и тензора напряжений) внутри и на границе области деформирования. Изначально метод граничных интегральных уравнений был реализован в виде комплекса программ МГИУ для персонального компьютера, разработанного сотрудниками Института горного дела СО РАН и предназначенного для решения трехмерных задач упругости с заданном на границе вектором усилий (В.И. Машуков).

В §1 описывается разработанный комплекс параллельных программ МГИУ-2 — модификация комплекса программ МГИУ с различными типами граничных условий. Для комплекса программ МГИУ-2 на границе области деформирования реализованы три вида граничных условий.

1) Вектор усилий F(x) = (Fi(x),F2(x),Fi(x)), действующий на элементарную площадку с нормалью п{х) — (щ, П2, т), проходящую через точку х = (х1,ж2, Хз). Если и(х) — решение задачи (42), то F(x) = T(n(x))u(x)\s, где Tij(n(x)) — оператор напряжения. Решение задачи (42) с заданным на границе F(x) ищется в виде потенциала простого слоя

и{х) = J Г(у — x)tp(y)dSv, s

где Г (у — х) — матрица фундаментальных решений (матрица Кельвина).

Уравнение для определения неизвестной плотности <р(х) имеет вид

-ф) + JТ(п(х))Г(у - x)<p(y)dSy = F{x). (43)

s

2) Вектор смещений и(х) = (щ(х), щ(х)). В этом случае исходная задача сводится к задаче с заданным вектором усилий на границе области.

пКупрадзе В.Д., Гегелиа Т.Г., Башыейгивили М.О., Бурчудадзе Т.В. Трехмерные задачи математической теории упругости и термоупругости. М.: Наука, 1976. 663 с.

Уравнение для определения вектора усилий имеет вид

-ВД + jT(n(x))T(y-x)F(y)dSv = Ф(х), (44)

где Ф(х) = jT{n{x)){T{n{y))Y(y - x))'n{y))dSy. s

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

Для численных расчетов проводится триангуляции граничной поверхности. Для случая тел вращения алгоритм автоматического построения триангуляции построен и реализован Т.И. Сережниковой.

В результате триангуляции граничной поверхности и дискретизации интегральных операторов задача упругости сводится к СЛАУ с заполненной матрицей. Для решения разрешающих систем уравнений используются параллельные итерационные методы градиентного типа: метод простой итерации с ускорением по Люстернику, метод наискорейшего спуска, метод минимальных ошибок и метод сопряженных градиентов.

Для комплекса программ МГИУ-2 при указанных выше граничных условиях разработаны и реализованы на МВС-1000 параллельные алгоритмы и программы для решения соответствующих граничных интегральных уравнений, вычисления компонент вектора смещений и тензора напряжений внутри и на границе области деформирования. Выполнены численные расчеты для модельных задач с анализом эффективности.

В 2001 г. комплекс параллельных программ МГИУ-2 передан в ИАПУ ДВО РАН для решения задач упругости на МВС-1000.

В §2 рассматривается использование и реализация параллельных алгоритмов при решении осесимметричной упруго-пластической задачи с малыми упругими и большими пластическими деформациями методом конечных элементов (совместная работа с И.П. Демешко и A.B. Коноваловым).

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

23Соболев С.К. Алгоритм Шварца в теории упругости // ДАН. 1936. Т. 4 (13). С. 235-238.

Коновалов A.B. Определяющие соотношения для упругопластической среды при больших пластических деформациях // Известия РАН. Механика твердого тела. 1997. № 5. С. 139-149.

С помощью конечно-элементной аппроксимации на каждом шаге нагрузки формируется СЛАУ с ленточной матрицей А большой размерности. Для решения СЛАУ использованы параллельные итерационные методы градиентного типа. Распараллеливание алгоритма решения задачи выполнено на всех этапах с анализом эффективности для МВС-1000.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

3. Для решения трехмерных нелинейных обратных задач гравиметрии и магнитометрии о нахождении поверхности раздела между средами на основе итеративно регуляризованного метода Ньютона выполнены основные этапы доказательных вычислений сходимости метода, разработаны параллельные вычислительные технологии и выполнены численные расчеты для реальных гравитационных и магнитных полей для различных областей (Средний Урал, Казахстан, Оренбург и Башкирия).

4. Разработан и реализован на МВС-1000 комплекс параллельных программ решения линейной обратной задачи гравиметрии и нелинейных обратных задач грави-магнитометрии на основе метода Ньютона с использованием регулярных параллельных прямых и итерационных алгоритмов.

5. Разработан и реализован на МВС-1000 комплекс параллельных программ МГИУ-2 решения трехмерной статической задачи упругости в ограниченных областях с различными типами граничных условий с использованием параллельных вычислительных технологий на всех этапах решения задачи и протестирован на серии модельных расчетов.

Публикации по теме диссертации

Статьи, опубликованные в научных журналах из списка ВАК

[1] Акимова E.H. Распараллеливание алгоритма матричной прогонки // Мат. моделирование. 1994. Т. 6. № 9. С. 61-67.

[2] Акимова E.H. Параллельный алгоритм решения систем уравнений с пятидиагональными матрицами и исследование его устойчивости // Вестник ННГУ. 2009.

№ 2. С. 135-140.

[3] Акимова E.H., Сережникова Т.Н. Распараллеливание алгоритма решения трехмерной задачи упругости методом граничных интегральных уравнений // Сиб. журн. вычисл. математики. 2000. Т. 3. № 2. С. 97-107.

[4] Акимова E.H., Горбачев И.И. Попов В.В. Решение задач многокомпонентной диффузии с помощью алгоритма матричной прогонки // Мат. моделирование. 2005. Т. 17. № 9. С. 85-92.

[5] Горбачев И.И., Попов В.В., Акимова E.H. Моделирование диффузионного взаимодействия карбонитридных выделений с аустенитной матрицей с учётом возможности изменения их состава // Физика металлов и металловедение. 2006. Т. 102. № 1. С. 22-32.

[6] Акимова E.H., Белоусов Д.В. Решение обратпой задачи гравиметрии с помощью параллельного алгоритма квадратного корня // Вестник УГТУ-УПИ. 2005. № 17 (69). С. 230-239.

[7] Акимова E.H., Гемайдинов Д.В. Параллельные алгоритмы решения задачи гравиметрии о восстановлении плотности в слое // Тр. Ин-та математики и механики УрО РАН. 2007.'Т. 13. № 3. С. 3-21.

Другие публикации

[8] Акимова E.H., Гемайдинов Д.В. Параллельные алгоритмы решения обратной задачи гравиметрии и организация удаленного взаимодействия между МВС-1000 и пользователем // Вычисл. методы и программирование. 2008. Т. 9. № 1. С. 133-144.

[9] Akimova E.N. Parallelization of algorithm for solving the three-dimensional problem of elasticity // J. Mechanical Engineering. 2001. Vol. 5. № 52. P. 299-308.

[10] Акимова E.H. Параллельные алгоритмы для решения трехмерной задачи упругости и разреженных линейных систем // Дальневост. мат. журн. 2001. Т. 2. .V' 2. С. 10-28.

[11] Akimova E.N. Parallelization of an algorithm for solving the gravity inverse problem // J. Computational and Applied Mechanics. 2003. Vol. 4. № 1. P. 5-12.

[12] Akimova E.N., Vasin V. V. Stable parallel algorithms for solving the inverse gravimetry and magnetometry problems // Intern. J. Engineering Modelling. 2004. Vol. 17. № 1-2. P. 13-19.

[13] Акимова E.H. Об устойчивости распараллеливания немонотонной прогонки: препринт ВЦ СО АН СССР. Новосибирск, 1989. № 818. 18 с.

[14] Акимпяп E.H. Об эффективности крупноблочного распараллеливания метода разделения переменных: препринт ВЦ СО АН СССР. Новосибирск, 1989. X' 833. 21 с.

[15] Акимова E.H. Исследование устойчивости алгоритма распараллеливания прогонки для решения систем пятиточечных уравнений // Высокопроизводительные вычисл. системы для комплексных центров мат. моделирования. Новосибирск: ВЦ СО АН СССР, 1991. С. 12-19.

[16] Акимова E.H. Параллельные прямые методы решения разреженных линейных систем // Алгоритмы и программные средства параллельных вычислений. Екатеринбург: ИММ УрО РАН, 1995. Вып. 1. С. 47-60.

[17] Акимова E.H. Распараллеливание алгоритма решения пространственной задачи упругости в случае задаяного на границе вектора усилий // Алгоритмы и программные средства параллельных вычислений. Екатеринбург: ИММ УрО РАН, 1998. Вып. 2. С. 10-21.

18] Akimova E.N. Parallel direct algorithms for solution of sparse linear systems // Proc. 4th Intern. Conf. "Parallel Computing Technologies" , Yaroslavl, September 8—12,1997. Berlin: Springer-Verlag, 1997. P. 389-390. (Lecture Notes in Computer Science; 1277).

19| Akirnova E.N. The parallel algorithm for solving the gravity inverse problem // Proc. 30th Intern. Summer School "Advanced Problems in Mechanics", St. Petersburg, June 27-July 6, 2002. СПб.: ИПМ PAH, 2002. P. 9-13.

20] Акимова E.H. Параллельные алгоритмы решения обратных задач гравиметрии и магнитометрии на МВС-1000 // Труды междунар. научной конференции "Параллельные вычислительные технологии", Нижний Новгород, 30 мар.-З апр. 2009 г. Челябинск: ЮУрГУ, 2009. С. 29-39.

21] Акимова E.H., Демешко И.П., Коновалов А.Н. Анализ быстродействия параллельных итерационных алгоритмов решения СЛАУ для упруго-пластических задач // Сб. статей 15-й Зим. школы по механике сплош. сред, Пермь, 26 февр.-З мар. 2007 г. Екатеринбург: УрО РАН, 2007. Ч. 1. С. 15-18.

22] Васин В.В., Акимова E.H. Параллельные алгоритмы решения трехмерной задачи упругости // Алгоритмы и программные средства параллельных вычислений. Екатеринбург: ИММ УрО РАН, 1999. Вып. 3. С. 34-47.

23] Васин В.В., Акимова E.H. Параллельный алгоритм решения трехмерной задачи упругости в случае смешанных граничных условий // Алгоритмы и программные средства параллельных вычислений. Екатеринбург: ИММ УрО РАН, 2000. Вып. 4. С. 63-75.

24] Акимова E.H., Васин В.В. Параллельный алгоритм решения обратной задачи гравиметрии на основе регуляризованного метода Ньютона // Алгоритмы и программные средства параллельных вычислений. Екатеринбург: ИММ УрО РАН, 2002. Вып. 6. С. 51-64.

25] Akimova E.N., Vasin V. V. Parallelization of algorithms for solving the inverse gravimetry and magnetometry problems // Proc. of 31st Intern. Summer School "Advanced Problems in Mechanics", St. Petersburg, June 22-July 2, 2003. СПб.: ИПМ РАН, 2003. P. 10-17.

26] Akimova E.N., Vasin V.V. Parallel iterative algorithms for solving the inverse gravity problems // Proc. 32nd Intern. Summer School "Advanced Problems in Mechanics", St. Petersburg, June 24-July 1, 2004. СПб.: ИПМ РАН, 2004. P. 1-8.

27] Акимова E.H., Васин B.B. Решение обратной задачи магнитометрии на многопроцессорном вычислительном комплексе МВС-1000 // Материалы 34-й сессии Междунар. семинара им. Д.Г. Успенского, Москва, 29 янв.-2 фев. 2007 г. М.: ИФЗ РАН, 2007. С. 8-11.

28] Акимова E.H., Васин В.В. Решение обратных геофизических задач на многопроцессорном вычислительном комплексе // Материалы междунар. конференции, по-свящ. 50-летию Института геофизики УрО РАН, Екатеринбург, 4-8 февр. 2008 г. Екатеринбург: ИГФ УрО РАН, 2008. С. 4-7.

29] Акимова E.H., Васин В.В. Параллельные алгоритмы решения обратных задач гравиметрии и магнитометрии на основе регуляризованного метода Ньютона [Электронный ресурс] // Материалы междунар. конференции "Математические методы в геофизике - 2008", Новосибирск, 13-15 окт. 2008 г. (CD-ROM). URL: http://www.sscc.ru/Conf/mmg2008/index.html (дата обращения: 08.07.2009).

Подписано в печать 20.08.2009 Формат 60x84 1/16. Объем 2 п.л. Тираж 120 экз. Заказ № 380 Редакционно-издательский отдел УГТУ-УПИ 620002, Екатеринбург, ул. Мира, 19.

Ризография НИЧ УГТУ-УПИ 620002, Екатеринбург, ул. Мира, 19.

Введение

1 Параллельные алгоритмы решения СЛАУ с трехдиаго-нальными, пятидиагональными и блочно-трехдиагональ-ными матрицами и исследование их устойчивости

1.1 Алгоритмы распараллеливания прогонки для решения систем уравнений с трехдиагональными матрицами и исследование их устойчивости

1.1.1 Алгоритм 1 распараллеливания трехточечной прогонки и его обобщение.

1.1.2 Исследование устойчивости алгоритма 1 распараллеливания трехточечной прогонки.

1.1.3 Алгоритм 2 распараллеливания трехточечной прогонки и его обобщение.

1.2 Алгоритмы распараллеливания прогонки для решения систем уравнений с пятидиагональными матрицами и исследование их устойчивости

1.2.1 Параллельный алгоритм 1 пятиточечной прогонки. Вывод формул алгоритма семиточечной прогонки

1.2.2 Исследование устойчивости параллельного алгоритма 1 пятиточечной прогонки.

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

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

1.3.1 Параллельный алгоритм 1 матричной прогонки и исследование его устойчивости.

1.3.2 Параллельный алгоритм 2 матричной прогонки и его обоснование.

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

1.4.1 Распараллеливание алгоритма решения сеточной задачи Дирихле для уравнения Пуассона.

1.4.2 Распараллеливание алгоритма решения сеточной задачи для бигармонического уравнения.

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

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

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

2.3 Анализ эффективности параллельного алгоритма матричной прогонки.

2.4 Решение задач многокомпонентной диффузии с помощью параллельного алгоритма матричной прогонки^.

3 Параллельные алгоритмы решения обратных задач гравиметрии и магнитометрии

3.1 Параллельные алгоритмы решения линейной обратной задачи гравиметрии о восстановлении плотности в слое

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

3.1.2 Распараллеливание прямых и итерационных методов решения задач о выделении источников гравитационного поля и восстановлении плотности в слое

3.1.3 Решение задач о восстановлении плотности в слое на МВС-1000 для областей Среднего Урала.

3.1.4 Об эффективности параллельных алгоритмов при решении задачи о восстановлении плотности в слое

3.2 Организация удаленного взаимодействия между МВСи пользователем при решении задачи гравиметрии.

3.2.1 Архитектура Web-сервера.

3.2.2 Web-приложение.

3.2.3 Пример использования Web-сервера.

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

3.3.1 Постановка структурных обратных задач гравиметрии и магнитометрии

3.3.2 Метод Ньютона для решения нелинейных задач

3.3.3 Основные этапы доказательных вычислений сходимости метода Ныотона при решении задачи гравиметрии

3.3.4 Распараллеливание итерационных и прямых методов типа Гаусса на каждом шаге метода Ньютона

3.3.5 Решение задач о нахождении поверхности раздела между средами на МВС-1000 для различных областей и анализ эффективности распараллеливания

4 Параллельные алгоритмы решения трехмерной задачи упругости и осесимметричной упруго-пластической задачи 207 4.1 Распараллеливание алгоритмов решения трехмерной задачи упругости методом граничных интегральных уравнений

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

4.1.2 Численные алгоритмы и параллельная реализация

4.1.3 Решение модельных задач упругости на МВС и анализ эффективности распараллеливания.

4.2 Распараллеливание алгоритмов решения осесимметричной упруго-пластической задачи и результаты численных экспериментов на МВС-1000 . . .'.

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

Важнейшими задачами исследования структуры земной коры являются обратные задачи гравиметрии и магнитометрии: задача гравиметрии о нахождении переменной плотности в слое и структурные задачи грави-магнитометрии о восстановлении геологической границы. Задачи описываются линейными и нелинейными интегральными уравнениями Фред-гольма первого рода и после дискретизации с использованием итерационных процессов сводятся с системам линейных алгебраических уравнений (СЛАУ) с плохо обусловленными заполненными матрицами большой размерности.

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

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

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

Таким образом, данные задачи описываются дифференциальными либо интегральными уравнениями и сводятся к решению СЛАУ с ленточными либо заполненными матрицами.

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

В работах [1]— [3] приводятся различные классификации многопроцессорных вычислительных систем. В качестве основных признаков классификации рассматриваются следующие: тип потока команд, тип потока данных, способ обработки данных, тип строения памяти, тип коммуникационной сети, степень однородности компонент системы, степень согласованности режимов работы устройств.

Самой ранней и наиболее известной является классификация архитектур вычислительных систем, предложенная в 1966 г. М. Флинном [4]. Данная классификация базируется на понятии потока. На основе числа потоков команд и потоков данных Флини выделяет четыре класса архитектур: ЯКБ (один поток команд — один поток данных), МЕЗБ (много потоков команд — один поток данных), ЯНуГО (один поток команд — много потоков данных), М1МБ (много потоков команд — много потоков данных).

Представителями класса Б^Б являются классические последовательные машины фон-неймановского типа. К классу МКБ можно отнести вычислительную систему, имеющую сложный процессор, например, векторно-конвейерного типа CRAY-1 [1]. Представителями класса SIMD являются матричная вычислительная система ILLIAC-IV фирмы "Барро-уз" [5] и отечественная векторно-многопроцессорная система ПС-2000 [6].

В системах типа MIMD процессоры универсальны и имеют собственную память. Современным представителем класса MIMD является многопроцессорный вычислительный комплекс кластерного типа МВС-1000 производства НИИ "Квант" , предназначенный для решения сложных научно-технических задач.

Приведем технические характеристики многопроцессорных вычислительных систем кластерного типа с распределенной памятью производства НИИ "Квант", установленных в Институте математики и механики УрО РАН (ИММ УрО РАН), на которых были реализованы описанные в данной диссертационной работе параллельные численные алгоритмы и решены прикладные задачи.

Вычислительная система МВС-1000/16 состоит из 14 процессоров Intel Pentium III-800, 256 Мбайт памяти, 10 Гбайт диска, двух 100 Мбит сетевых плат (Digital DS21143 Tulip и Intel PRO/lOO).

МВС—1000/32 состоит из 16 двухпроцессорных модулей Xeon 2,4 ГГц, 4 Гбайт оперативной памяти в каждом модуле, 40 Гбайт жесткого диска, сетевых интерфейсов Fast Ethernet и Gigabit Ethernet.

МВС-1000/64 состоит из 14 двухпроцессорных 2-х ядерных модулей AMD Opteron 64 bit (2.6 Ггц) с картой GbitEthernet.

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

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

Работы, посвященные параллельным вычислениям, идут по нескольким направлениям: исследование общих вопросов распараллеливания алгоритмов [9]— [10], построение алгоритмов для абстрактных параллельных вычислительных систем [11]— [12] и реализация алгоритмов на реальных многопроцессорных вычислительных системах.

Из работ, посвященных общим вопросам параллельных вычислений, выделим работы В.В. Воеводина [13]— [15]. Они посвящены совместному исследованию параллельных численных методов и параллельных вычислительных систем. В качестве математическимх объектов, используемых как посредники для описания алгоритмов и МВС, применяются ориентированные графы. Вводится граф вычислительной системы и ставятся задачи отображения графа алгоритма на граф системы. Описываются классы систем, для которых такое отображение является эффективным.

Среди работ, посвященных параллельным прямым методам решения систем линейных уравнений, отметим обзоры В.Н. Фаддеевой и Д.К. Фад-деева [16], монографии Е. Валяха [5], И.Н. Молчанова [17], Дж. Орте-га [18], сборник статей под редакцией Г. Родрига [1], коллективную монографию под редакцией Д. Ивенса [19], и др.

• В обзорах В.Н. Фаддеевой и Д.К. Фаддеева, посвященных исследованию параллельных алгоритмов1 для решения задач линейной алгебры на абстрактных вычислительных системах, вводятся понятия, анализирующие параллельные свойства алгоритма: параллельная форма алгоритма (последовательность упорядоченных групп операций, каждая из которых' зависит от результатов в предыдущих группах), ярус параллельной формы (на каждом ярусе собраны операции, не зависящие друг от друга по информации), высота параллельной формы (число групп), ширина параллельной формы (максимальное число операций в ярусе). Высота параллельного алгоритма — минимальная высота его параллельной формы.

В работах Л.Н. Столярова и В.М. Абрамова [20]— [21] рассматривается представление алгоритмов в виде информационных структур, которые удобно изображать в виде графа, вершинам которого соответствуют арифметические операции, а дуги указывают на зависимость результатов от аргументов операций.

Для исследования параллельных свойств и сравнения работы последовательного и параллельного алгоритма вводятся некоторые характеристики. Основные — это коэффициенты ускорения и эффективности:

Зтп — трг > Ет — -, (1) тт т где Т\ — время выполнения последовательного алгоритма на одном процессоре, Тт — время выполнения параллельного алгоритма на многопроцессорной вычислительной системе с числом процессоров т (т > 1).

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

Тт = Тс 4- Т0.

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

Е = щту (2) где С — гранулярность параллельного алгоритма.

1. К-ша1кхжз1а в работе [22] предложил использовать гранулярность для вычисления эффективности распараллеливания.

Гранулярность параллельного алгоритма — это отношение времени вычислений ко времени накладных расходов = £• (3)

1 о

Гранулярность параллельного алгоритма можно оценить следующим образом < тах(Тсотр) • тп ~ тт(Тсотт) ■ тп ' Здесь тах(Тсотр) — максимальное время вычислений для одного процессора, тт(Тсотот) — минимальное время накладных расходов.

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

Основной целью при построении параллельных алгоритмов является получение максимального ускорения'и эффективности:

Sm~m и Ет — 1.

Условиями высокой эффективности являются:

1) равномерная загрузка процессоров (отсутствие простоев);

2) низкая интенсивность взаимодействия процессоров (независимость);

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

В некоторых случаях удается получить Ет > 1. Данный факт связан с уменьшением времени обращения к данным за счет кэш-памяти.

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

В работах H.H. Миренкова [23]- [24] предлагается один из принципов создания параллельных алгоритмов — крупноблочно-иерархический подход к распараллеливанию. Схема параллельного алгоритма рассматривается как иерархическая структура, высший уровень которой — крупные блоки, выполняемые независимо, следующий уровень — подблоки крупных блоков, и т.д. Например, представление иерархического параллельного алгоритма П из трех уровней рассматривается как тройка параллельных алгоритмов

П=<ПьП2,Пз>, где каждый алгоритм Пг- (г = 1,2,3) отражает часть присущего задаче параллелизма, причем сложность отдельного действия уменьшается в Пг с ростом г. Каждый уровень иерархии отражает определенный параллелизм задачи.

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

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

Распараллеливание на уровнях Пх и П2 удобно для отображения на многопроцессорные вычислительные системы типа МВС-1000.

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

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

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

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

В работах P.M. Kogge и H.S. Stone [25]— [26] описан метод "рекурсивного сдваивания" на основе понятия сопровождающей функции. Для эффективной реализации алгоритмов, использующих сопровождающие функции, применяется метод логарифмического сдваивания.

В работе И.Б. Кузнецова [27] построены сопровождающие функции для алгоритмов скалярной и матричной прогонки.

Декомпозиции рекуррентных соотношений для решения одномерных и двумерных сеточных задач посвящены работы Ю.М. Нечепуренко [28] и A.C. Оленина [29]. Элементы обратной матрицы системы трехточечных уравнений представляются в факторизованном виде. Факторизация приводит к разложению обратной матрицы на сумму произведений диагональных и треугольных матриц. Параллельная модификация алгоритма основана на распараллеливании рекурсий.

Другой подход предложен в работе В.А. Валысовского, В.Е. Котова, А.Г. Марчука и H.H. Миренкова [30]. Он включает в себя однородное распределение массивов и других структур данных по ветвям параллельного алгоритма. В результате уменьшается время, затрачиваемое на взаимодействие ветвей. При таком распределении имеют место:

1) равенство объемов распределяемых частей массивов;

2) разделение массивов на части параллельными линиями;

3) дублирование массивов или частей одинаковым образом.

В дальнейшем при построении параллельных алгоритмовы мы будем использовать основные способы однородного распределения: горизонтальные полосы (ГП-распределение) и вертикальные полосы (ВП-распределение).

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

Различные варианты методов разделения областей исследовались многими авторами в нашей стране (Е.С. Николаев и A.A. Самарский [31], В.К.Агапов, Ю.А. Кузнецов, С.А. Финогенов [32], A.M. Мацокин [33], В.И. Лебедев и В.И. Агошков [34], и др.). Наиболее эффективными методы разделения областей оказываются в случаях, когда подобласти имеют достаточно простой вид (прямоугольники, параллелепипеды). Тогда в каждой такой регулярной подобласти исходная задача может быть решена одним из эффективных прямых методов. Например, методом разделения переменных с использованием алгоритма быстрого преобразования Фурье [35] или методом редукции.

Работы Ю.А. Кузнецова [36]— [37] посвящены исследованию блочно-релаксационных методов разделения области (методов Якобп, Гаусса-Зейделя и др.) как вычислительных процессов в подпространствах меньшей размерности, чем размерность исходных пространств. Смысл вычислительных процессов в подпространствах заключается в следующем. Сначала производится сдвиг решения исходной системы на некоторый вектор, чтобы правая часть принадлежала некоторому подпространству. Затем методом, который учитывает строение вектора правой части полученной системы, находится частичное решение этой системы. Оно позволяет свести вычисление полного решения к задаче решения систем с матрицами простого вида [37].

Одним из эффективных итерационных методов решения задачи Дирихле для уравнения Лапласа в областях сложной формы (область П делится на две подобласти Пх и 0,2, имеющими непустое пересечение) является альтернирующий метод Шварца, описанный в работе JT.B. Канторовича и В.И. Крылова [38].

В работе В.И. Лебедева и В.И. Агошкова [39] и работе A.M. Мацокина и C.B. Непомнящих [40] метод Шварца рассматривается как вариант метода разделения областей на случай, когда области Qi и П2 имеют лишь общую границу. Для ускорения сходимости методов разделения областей используются алгоритмы наискорейшего спуска, сопряженных градиентов, оптимальный линейный итерационный процесс и др.

В качестве методов разделения областей можно рассматривать метод суммарных представлений, описанный в работе Г.Н. Положия [41] и работе И.И. Ляшко и И.М. Великоиваненко [42]. В областях, составленных из прямоугольников, искомое решение записывается по формуле суммарных представлений в явном виде и на границе раздела областей выражается через известные граничные условия.

Один из вариантов при построении параллельных алгоритмов основан на том, что исходные данные задачи остаются неделимыми, но зато рассматривается известный последовательный алгоритм этой задачи и действия его распределяются по ветвям. В работах Е.В. Бондаренко [43] и В.К. Саульева [44] описываются алгоритмы такого типа.

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

В работах А.Н. Коновалова и Н.Н Яненко [46]— [48] вопросы распараллеливания вычислений рассматриваются с точки зрения изучения модульной структуры вычислительных алгоритмов для решения определенного класса задач (например, математической физики).

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

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

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

3. Метод установления позволяет с единой точки зрения трактовать эволюционные и неэволюционные задачи. Этот метод допускает и физическую интерпретацию: выход на стационарный режим, введение малой сжимаемости и т.п., после чего возможно применение методов типа 1,2.

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

5. Методы аналитического расщепления (типа предиктор-корректор). Их назначение может быть различным: обеспечение полной консервативности, повышение порядка точности и т.д. Методы этого типа также сводят исходную задачу к последовательному решению вспомогательных задач, каждая из которых может иметь самостоятельное значение.

Если вычислительный алгоритм решения исходной задачи из заданного класса строится на основе методов типа 1-5, то решение исходной задачи сводится к последовательному решению "простых" вспомогательных задач в стандартной области. Эти задачи в [49] названы базисными задачами, а последовательность решения таких задач, обеспечивающую решение исходной задачи, — представлением исходной задачи в данном базисе. В рамках некоторого фиксированного базиса может быть представлен довольно широкий класс задач математической физики. Пополнение класса исходных задач может быть произведено за счет незначительного расширения базиса.

Модуль — есть программная реализация базисной задачи [50]. Тогда вычислительный алгоритм и программа одновременно приобретают модульную структуру. В работе [49] понятие "простая задача" определяется с учетом условий, накладываемых на программную реализацию таких задач конкретной структурой ЭВМ, следующим образом.

Простая задача есть краевая задача с однородной физико-математической моделью, которая является корректной, допускает численную аппроксимацию на однородной разностной сетке (регулярной или нерегулярной) и целиком вкладывается в оперативную память ЭВМ.

Сведение конкретной задачи к последовательности "простых задач" является модульной декомпозицией задачи. Модульная декомпозиция алгоритма существенно облегчает его распараллеливание.

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

Распараллеливание решения базисных задач с помощью явных схем показано в работе [51]. Распараллеливание неявных схем расщепления и неявных методов бегущего счета показано в работе [47].

В современных вычислениях численная реализация многих базисных задач для решения класса задач математической физики связана с методом прогонки. Алгоритмы распараллеливания прогонки для решения краевой задачи Дирихле на отрезке для трехточечного разностного уравнения предложены и обоснованы в работах [52]— [53].

Крупноблочный подход к построению параллельных алгоритмов связан с прямыми методами решения разреженных систем линейных уравнений, матрица коэффициентов которых имеет блочный или ленточный вид. Представляют интерес параллельные алгоритмы, предполагающие блочное разбиение матрицы коэффициентов системы линейных алгебраических уравнений (СЛАУ) — блочный алгоритм Лори-Самеха [54] и блочный алгоритм Джонсона [56]. В результате преобразований исходной системы формируется редуцированная система уравнений, после решения которой находится часть искомых неизвестных. Остальные искомые неизвестные выражаются через найденные неизвестные.

В работе [57] идея декомпозиции области для решения системы уравнений с трехдиагональной матрицей обсуждается под именем "стратегии параллельных сечений". Узлы сетки разбиваются на группы и выделяется часть узлов, составляющая множество-разделитель 5". В результате перенумерации неизвестных последние номера присваиваются множеству $ и новая СЛАУ имеет "стреловидный вид". Сначала находятся неизвестные множества 5, затем - остальные неизвестные.

Отметим еще некоторые параллельные алгоритмы, описанные в литературе. Алгоритм циклической редукции для трехдиагональных систем общего вида и его параллельные варианты рассмотрены в работе [3].

Параллельный алгоритм для решения трехдиагональных систем, основанный на распараллеливании рекурсивных соотношений, предложен в работе [58].

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

В случае, когда матрица коэффициентов СЛАУ заполнена, при реализации прямых параллельных алгоритмов также существуют проблемы. Подробное рассмотрение параллельных алгоритмов для решения систем уравнений с плотными матрицами приведено в монографии Дж. Орте-га [18]. Основные методы, рассматриваемые автором в [18] при распараллеливании систем уравнений, это параллельный метод Гаусса (Ы1разложение для систем уравнений с заполненной квадратной матрицей) и параллельный алгоритм Холесского (ЬЬ' - разложение для систем с положительно определенной матрицей).

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

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

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

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

Научная новизна.

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

1. Построены прямые параллельные алгоритмы решения СЛАУ с пя-тидиагопальными матрицами и параллельные алгоритмы матричной прогонки для решения СЛАУ с блочно-трехдиагональными матрицами.

2. Доказаны теоремы об устойчивости параллельных алгоритмов решения СЛАУ с трехдиагональными, пятидиагональными и блочно-трехдиагональными матрицами в зависимости от соотношения коэффициентов исходных систем уравнений.

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

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

5. Разработан и реализован на МВС-1000 комплекс параллельных программ решения линейной обратной задачи гравиметрии и нелинейных обратных задач грави-магнитометрии на основе метода Ньютона с использованием регулярных параллельных прямых (типа Гаусса) и итерационных (градиентного типа) алгоритмов.

6. На базе комплекса программ В.И. Машукова разработан и реализован на МВС-1000 комплекс параллельных программ МГИУ-2 решения трехмерной статической задачи упругости в ограниченных областях с различными типами граничных условий. В случае смешанных граничных условий реализован итерационный альтернирующий метод Шварца.

Защищаемые положения.

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

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

3. Для решения трехмерных нелинейных обратных задач гравиметрии и магнитометрии о нахождении поверхности раздела между средами на основе итеративно регуляризованного метода Ньютона выполнены основные этапы доказательных вычислений сходимости метода, разработаны параллельные вычислительные технологии и выполнены численные расчеты для реальных гравитационных и магнитных полей для различных областей (Средний Урал, Казахстан, Оренбург и Башкирия).

4. Разработан и реализован на МВС-1000 комплекс параллельных программ решения линейной обратной задачи гравиметрии и нелинейных обратных задач грави-магнитометрии на основе метода Ньютона с использованием регулярных параллельных прямых и итерационных алгоритмов.

5. Разработан и реализован на МВС-1000 комплекс параллельных программ МГИУ-2 решения трехмерной статической задачи упругости в ограниченных областях с различными типами граничных условий с использованием параллельных вычислительных технологий на всех этапах решения задачи и протестирован на серии модельных расчетов.

Практическая значимость.

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

В 2001 г. комплекс параллельных программ МГИУ-2 решения трехмерной задачи упругости методом граничных интегральных уравнений передан в Институт автоматики и процессов управления (ИАПУ) ДВО РАН для решения задач упругости на многопроцессорном вычислительном комплексе МВС-1000.

Комплекс параллельных программ решения линейной задачи гравиметрии о восстановлении плотности в слое и решения нелинейных задач грави-магнитометрии о нахождении поверхности раздела между средами успешно используется в реальных расчетах для различных областей совместно с сотрудниками Института геофизики УрО РАН.

Разработан специализированный \¥еЬ-сервер, предназначенный для запуска программ, реализующих параллельные алгоритмы решения линейной обратной задачи гравиметрии на МВС-1000 через \¥еЬ-интерфейс.

Разработанные автором параллельные алгоритмы легли в основу создания спецкурса "Параллельные вычисления" для студентов специальности "Математическое обеспечение и администрирование информационных систем".

Апробация работы.

Основные положения диссертационной работы докладывались pi обсуждались на Всероссийских и Международных конференциях и семинарах: Международных конференциях "Parallel Computing Technologies -РаСТ" (Обнинск, 1993; Санкт-Петербург, 1995; Ярославль, 1997), Международных конференциях "Numerical Methods in Continuum Mechanics" (Липтовский Ян - Словакия, 2000; Жилина - Словакия, 2003), Восьмом Всероссийском съезде по теоретической и прикладной механике (Пермь, 2001), Международной конференции "Numerical Methods and Computational Mechanics" (Мишкольц - Венгрия, 2002), Международных летних школах "Advanced Problems in Mechanics - АРМ" (Санкт-Петербург, 2002, 2003, 2004), I, II и III Всероссийских конференциях, посвященных памяти академика А.Ф. Сидорова "Актуальные проблемы прикладной математики и механики" (Екатеринбург - Трубник, 2003; Абрау-Дюрсо, 2004; Абрау-Дюрсо, 2006), Всероссийской конференции "Декомпозиционные методы в математическом моделировании и информатике" (Москва, 2004), XIV Всероссийской конференции "Алгоритмический анализ неустойчивых задач" (Екатеринбург^Трубник, 2004), XV Всероссийской конференции "Теоретические основы и конструирование численных алгоритмов для решения задач математической физики с приложением к многопроцессорным системам посвященной памяти К.И. Бабенко (Абрау-Дюрсо, 2004), XI Всероссийской Школе-семинаре "Современные проблемы математического моделирования" (Абрау-Дюрсо, 2005), Международном семинаре им. Д.Г. Успенского "Вопросы теории и практики геологической интерпретации гравитационных, магнитных и электрических полей" (Екатеринбург, 2006), XXIV Генеральной ассамблее международного союза геодезии и геофизики "Earth: our changing planet" (Перуджа - Италия, 2007), Международной конференции, посвященной 50-летию Института геофизики УрО РАН "Геофизические исследования Урала и сопредельных регионов" (Екатеринбург, 2008), V Международной конференции "Алгоритмический анализ неустойчивых задач, посвященной 100-летию со дня рождения В.К. Иванова" (Екатеринбург -Трубник, 2008), Международной конференции "Математические методы в геофизике - 2008" (Новосибирск, 2008), Международных конференциях "Параллельные вычислительные технологии - ПаВТ" (Челябинск, 2007; Санкт-Петербург, 2008; Нижний Новгород, 2009).

Публикации.

По теме диссертации автором опубликовано 50 работ (из них 10 работ -на английском языке). Основные результаты опубликованы в 29 работах (список приведен в автореферате), в том числе в научных изданиях, рекомендованных ВАК, в рецензируемых российских и иностранных журналах, препринтах ВЦ СО АН СССР, в сборниках статей ИММ УрО РАН, а также в трудах всероссийских и международных научных конференций.

Исследования по теме диссертации выполнены в период с 1990 по 2008 годы в отделе некорректных задач анализа и приложений Института математики и механики УрО РАН.

Автор выражает искреннюю признательность своему учителю главному научному сотруднику ИВМиМГ СО РАН академику РАН Анатолию Николаевичу Коновалову.

Автор выражает благодарность за постановку ряда математических проблем, поддержку, полезные замечания и обсуждения заведущему Отделом некорректных задач анализа и приложений ИММ УрО РАН члену-корреспонденту РАН Владимиру Васильевичу Васину.

Структура и объем работы.

Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем диссертационной работы составляет 255 страниц. Библиография содержит 143 наименования.

Основные результаты диссертации состоят в следующем.

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

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

3. Для решения трехмерных нелинейных обратных задач гравиметрии и магнитометрии о нахождении поверхности раздела между средами на основе итеративно регуляризованного метода Ньютона выполнены основные этапы доказательных вычислений сходимости метода, разработаны параллельные вычислительные технологии и выполнены численные расчеты для реальных гравитационных и магнитных полей для различных областей (Средний Урал, Казахстан, Оренбург и Башкирия).

4. Разработан и реализован на МВС-1000 комплекс параллельных программ решения линейной обратной задачи гравиметрии и нелинейных обратных задач грави-магнитометрии на основе метода Ньютона с использованием регулярных параллельных прямых и итерационных алгоритмов.

5. Разработан и реализован на МВС-1000 комплекс параллельных программ МГИУ-2 решения трехмерной статической задачи упругости в ограниченных областях с различными типами граничных условий с использованием параллельных вычислительных технологий на всех этапах решения задачи и протестирован на серии модельных расчетов.

Заключение

1. Параллельные вычисления // Под ред. Г. Родрига. М.: Наука, 1986. 374 с.

2. Баер Ж.-Л., Барлоу Р., Вудворд М., и др. Системы параллельной обработки. М.: Мир, 1985. 416 с.

3. Хокни Р., Дэюессхоуп К. Параллельные ЭВМ. Архитектура, программирование и алгоритмы. М.: Радио и связь, 1986. 392 с.

4. Flynn М. Very high-speed computing system // Proc. IEEE. 1966. № 54. P. 1901-1909.

5. Валях E. Последовательно-параллельные вычисления. M.: Мир, 1985. 456 с.

6. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением. М.: Энергоатомиз-дат, 1983. 312 с.

7. Zabrodin А. V., Levin V.K., Korneev V. V. The Massively parallel processing system MBC-100. Proceedings of the Third International Conference (PaCT-95). Berlin: Springer-Verlag, 1995. P. 341-355. (Lecture Notes in Computer Science; 964).

8. Baranov A.V., Latsis A.O., Sazhin G.V., Khramtsov M.Yu. The MVS-1000 system user's guide. URL: http://parallel.ru/mvs/user.html (дата обращения: 09.09.2009).

9. Воеводин В. В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. 296 с.

10. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 599 с.

11. Ильин В.П., Фет Я.И. Параллельный процессор для решения задач математической физики. Препринт ВЦ СО АН СССР. Новосибирск, 1979. № 217. 36 с.

12. Ильин В.П., Руфицкий В.Н., Фет Я.И. Сеточный параллельный процессор. Препринт ВЦ СО АН СССР. Новосибирск, 1986. № 683. 21 с.

13. Воеводин В. В. Математические вопросы отображения алгоритмов на параллельные системы. Препринт ОВМ АН СССР. М.: Наука, 1985. № 94. 64 с.

14. Воеводин В.В. Параллельные структуры алгоритмов и программ. М.: ОВМ АН СССР, 1987. 148 с.

15. Воеводин В.В. Информационная структура алгоритмов. М.: МГУ, 1997. 139 с.

16. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре 1,2. // Кибернетика, 1977. №6. С. 28-40; 1982. №3. С. 18-31.

17. Молчанов И.Н. Введение в алгоритмы параллельных вычислений. Киев: Наукова Думка, 1990. 127 с.

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

19. Системы параллельной обработки // Под ред. Д. Ивенса. М.: Мир, 1985. 414 с.

20. Столяров Л.Н., Абрамов В.М. Организация параллельных вычислений, учитывающая особенности вычислительной системы // Комплексы программ математической физики. Новосибирск: ВЦ и ИТи-ПМ СО РАН, 1980. С. 250-262.

21. Абрамов В.М., Столяров Л.Н. Структурный анализ алгоритмов прогонки и редукции для параллельных вычислений // Численные методы механики сплошной среды. Новосибирск: ВЦ и ИТиПМ СО РАН, 1985. Т. 16, № 6. С. 3-18.

22. Kwiatkovuski J. Evaluation of parallel programs by measurement of its granularity // Proceedings of the conference "Parallel Processing and Applied Mathematics". Berlin: Springer-Verlag, 2001. P. 145-153. (Lecture Notes in Computer Science; 2328).

23. Миренков Н.Н. Иерархические параллельные алгоритмы // Вычислительные процессы и системы. М.: Наука, 1985. Вып. 2. С. 121 -128.

24. Миренков Н.Н. Параллельное программирование для многомодульных вычислительных систем. М.: Радио и связь, 1989. 320 с.

25. Кодде P.M. Parallel solution of recurrence problem // IBM J. Res. Develop. 1974. Vol. 18. №2. P. 138-148.

26. Kogge P.M., Stone H.S. A parallel algoritm for the efficient solution of a general class of recurrence equation // IEEE Trans, on Computers. 1973. Vol. 22. №8. P. 786-792.

27. Кузнецов И.Б. Параллельные формы алгоритма для решения рекурсивных задач. Препринт ВЦ СО АН СССР. Новосибирск. 1983. №101. 16 с.

28. Нечепуренко Ю.М. Новый параллельный алгоритм для трехднаго-нальной системы // Архитектура ЭВМ и численные методы. М.: ОВМ АН СССР, 1983. С. 29-45.

29. Оленин А. С. Параллельные вычисления в некоторых разностных задачах. Препринт ИТМиВТ АН СССР. М. 1983. №3. 24 с.

30. Валъковский В.А., Котов В.Е., Марчук А.Г., Миренков Н.Н. Элементы параллельного программирования. М.: Радио и связь, 1983. 239 с.

31. Николаев Е.С., Самарский A.A. Методы решения сеточных эллиптических уравнений в нерегулярных областях. Препринт ИПМ им.М.В.Келдыша. М.: Наука, 1979. № 63. 23 с.

32. Агапов В.К., Кузнецов Ю.А., Финогенов С.А. Реализация блочно-релаксационных методов в подпространствах // Архитектура ЭВМ и численные методы. M.: ОВМ АН СССР, 1983. С. 103-141.

33. Мацокин A.M. Методы фиктивных компонент и альтернирования по подобластям. Препринт ВЦ СО АН СССР. Новосибирск, 1985. № 612. 25 с.

34. Лебедев В.И., Агошков В.И. Вариационные алгоритмы метода разделения области. Препринт ОВМ АН СССР. М.: Наука, 1983. № 54. 24 с.

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

36. Кузнецов Ю.А. Вычислительные методы в подпространствах // Вычислительные процессы и системы. М.: Наука, 1985. Вып. 2. С. 265350.

37. Кузнецов Ю.А.; Труфанов О.Д. Методы разбиения области для волнового уравнения Гельмгольца. Препринт ОВМ АН СССР. М.: Наука, 1986. № 125. 39 с.

38. Канторович Л.В., Крылов В.И. Приближенные методы высшего анализа. M.-JL: Госиздат, физ.-мат. лит., 1962. 708 с.

39. Лебедев В.И., Агошков В.И. Обобщенный алгоритм Шварца с переменными параметрами. Препринт ОВМ АН СССР. М.: Наука, 1981. № 19. 40 с.

40. Мацокин A.M., Непомнящих C.B. Метод альтернирования Шварца в подпространстве. Препринт ВЦ СО АН СССР. Новосибирск, 1985. № 114. 16 с.

41. Положий Г.Н. Числеиное решение двумерных и трехмерных краевых задач математической физики и функции дискретного аргумента. Киев: Изд-во КГУ, 1962. 161 с.

42. Ляшко И.И., Великоиваненко И.М. Численно-аналитическое решение краевых задач теории фильтрации. Киев: Наукова думка, 1973. 264 о.

43. Бондаренко Е.В. Распараллеливание методов модификации матричных факторизаций // Вычислительные процессы и системы. М.: Наука, 1985. Вып. 2. С. 228-264.

44. Саулъев В.К. Об одном явном параллельном разностном методе решения нелинейных уравнений параболического типа. Препринт ОВМ АН СССР. М.: Наука, 1981. № И. 10 с.

45. Кузнецов И.Б., Кузнецов С.Б. Распараллеливание методов типа ПЕЗЗ? для решения эллиптических уравнений. Препринт ВЦ СО АН СССР. Новосибирск, 1986. № 633. 15 с.

46. Коновалов А.Н., Яненко H.H. Модульный принцип построения программ как основа создания пакета прикладных программ решения задач механики сплошной среды // Комплексы программ математической физики. Новосибирск: ИТиПМ СО АН СССР, 1972. С. 48-54.

47. Яненко H.H. Вопросы модульного анализа и параллельных вычислений в задачах математической физики // Комплексы программ математической физики. Новосибирск: ИТиПМ СО АН СССР, 1970. С. 3-12.

48. Япенко Н.Н., Карначук В.И., Коновалов А.Н. Проблемы математической технологии // Численные методы механики сплошной среды. Новосибирск: ВЦ и ИТиПМ СО АН СССР, 1977. Т. 8, № 3. С. 129-157.

49. Коновалов А.Н. Задачи фильтрации многофазной несжэимаемой жидкости. Новосибирск: Наука, 1988. 164 с.

50. Софронов И.Д. Оценка параметров вычислительной машины, предназначенной для решения задач механики сплошной среды // Численные методы механики сплошной среды. Новосибирск: ВЦ и ИТиПМ СО АН СССР, 1975. Т. 6, № 3. С. 98-147.

51. Яненко Н.Н., Коновалов А.Н., Бугров А.Н.; Шустов Г.В. Об организации параллельных вычислений и распараллеливании прогонки // Численные методы механики сплошной среды. Новосибирск: ВЦ и ИТиПМ СО АН СССР, 1978. Т. 9, № 7. С. 139-146.

52. Бугров А.Н., Коновалов А.Н. Об устойчивости алгоритма распараллеливания прогонки // Численные методы механики сплошной среды. Новосибирск: ВЦ и ИТиПМ СО АН СССР, 1979. Т. 10, № 6. С. 27-32.

53. Lawrie D., Sameh A. The Computation and Communication Complexity of a Parallel Banded System Solver // ACM Trans. Math. Softwere 10. 1984. P. 185-195.

54. Sameh A.H., Киек D.J. Parallel direct linear system solvers a survey // Mathematics and Computers in Simulation, 1977. Vol. 19. №4. P. 272277.

55. Johnsson L. Solving Narrow Banded Systems on Ensemble Architectures // ACM Trans. Math. Softwere 11. 1985. P. 271-288.

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

57. Stone H. Parallel Tridiagonal Equation Solvers // ACM Trans. Math. Softwere 1. 1975. P. 289-307.

58. Коновалов A.H., Бугров A.H., Елинов B.B. Алгоритмы распараллеливания сеточных задач // Актуальные проблемы вычислительной и прикладной математики. Новосибирск: Наука, 1979. С. 95-99.

59. Мартышко П. С., Пруткин И. Л. Технология разделения источников гравитационного поля по глубине // Геофизический журнал. 2003. Т. 25, № 3. С. 159-168.

60. Мартышко П.С., Кокшаров Д.Е. Об определении плотности в слоистой среде по гравитационным данным // Геофизический журнал. 2005. Т. 27. № 4. С. 678-684.

61. Васин В.В., Агеев А.Л. Некорректные задачи с априорной информацией. Екатеринбург: Наука, 1993. 262 с.

62. Bakushinsky A., Goncharsky A. Ill-posed problems: Theory and Applications. London: Kluwer Akad. Publishers. 1994. 256 p.

63. Бабенко К.И., Петрович В.Ю. Доказательные вычисления в задаче о существовании решения удвоения // ДАН СССР. 1984. Т. 277. №2. С. 265-270.

64. Бахвалов Н.С. Численные методы. М.: Наука, 1973. С. 412.

65. Канторович Л.В., Акилов Г.П. Функциональный анализ. М.: Наука, 1977. С. 680.

66. Бакушинский А.Б., Кокурин М.Ю. Итерационные методы решения нерегулярных уравнений. М.: ЛЕНАНД, 2006. С. 14.

67. Купрадзе В.Д., Гегелиа Т.Г., Башелейшвили М.О., Бурчуладзе Т.В. Трехмерные задачи математической теории упругости и термоупругости. М.: Наука, 1976. 663 с.

68. Машуков В.И., Лоскутова Л.И. Вычислительные алгоритмы и программные средства для решения трехмерных краевых задач теории упругости. Отчет ИГД СО РАН. Новосибирск, 1991. 137 с.

69. Соболев С.К. Алгоритм Шварца в теории упругости // ДАН. 1936. Т. 4 (13). С. 235-238.

70. Коновалов A.B. Определяющие соотношения для упругопластиче-ской среды при больших пластических деформациях // Известия РАН. Механика твердого тела. 1997. № 5. С. 139-149.

71. Акимова E.H. Алгоритмы распараллеливания сеточных задач. Диссертация . канд. физ.-мат. наук: 01.01.07. Новосибирск, 1990. 162 с.

72. Годунов С.К., Рябенький B.C. Разностные схемы. М.: Наука, 1977. 439 с.

73. Акимова E.H. Об устойчивости распараллеливания немонотонной прогонки. Препринт ВЦ СО АН СССР. Новосибирск, 1989. № 818. 18 с.

74. Акимова E.H., Пинкина H.A. Анализ устойчивости и-реализация алгоритма распараллеливания прогонки // Проекционно-сеточные методы в задачах численного анализа. Новосибирск: ВЦ СО АН СССР, 1989. С. 3-12.

75. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984. 318 с.

76. Ильин В.П., Кузнецов Ю.А. Трехдиагональные матрицы и их приложения. М.: Глав. ред. физ.-мат. литературы, 1985. 208 с.

77. Акимова E.H., Гемайдинов Д. В. Параллельные алгоритмы решения задачи гравиметрии о восстановлении плотности в слое // Труды института математики и механики УрО РАН. 2007. Т. 13. № 3. С. 3-21.

78. Акимова E.H. Параллельный алгоритм решения систем уравнений с пятидиагональными матрицами и исследование его устойчивости // Вестник ННГУ. 2009. № 2. С. 135-140.

79. Акимова E.H. Распараллеливание алгоритма матричной прогонки // Математическое моделирование. 1994. Т. 6, № 9. С. 61-67.

80. Акимова E.H., Горюнова С.А. Параллельный алгоритм решения СЛАУ с блочно-трехдиагональными матрицами // Проблемы теоретической и прикладной математики. Труды 37-й Региональной молодежной конференции. Екатеринбург: ИММ УрО РАН, 2006. С. 156— 160.

81. Акимова E.H. Структурный анализ некоторых параллельных алгоритмов // Тезисы 2-й конференции молодых ученых Сибири и Дальнего Востока. Новосибирск: НГУ, 1988. С. 13-15.

82. Акимова E.H. Об эффективности крупноблочного распараллеливания метода разделения переменных. Препринт ВЦ СО АН СССР. Новосибирск, 1989. № 833. 21 с.

83. Акимова E.H., Гемайдинов Д.В., Клименков A.B. Параллельные алгоритмы решения обратной задачи гравиметрии // Алгоритмы и программные средства параллельных вычислений. Екатеринбург: ИММ УрО РАН, 2006. Вып. 9. С. 3-16.

84. Акимова E.H. Параллельные прямые методы решения разреженных линейных систем // Алгоритмы и программные средства параллельных вычислений. Екатеринбург: ИММ УрО РАН, 1995. Вып. 1. С. 4760.

85. Акимова E.H., Горбачев H.H. Попов В. В. Решение задач многокомпонентной диффузии с помощью алгоритма матричной прогонки// Математическое моделирование. 2005. Т. 17, № 9. С. 85-92.

86. Бокштейн Б. С. Диффузия в металлах. Москва: Металлургия, 1978. 276 с.

87. Aaron Н.В., Kolter G.A. Second Phase Dissolution // Met. Yrans. 1971. Vol. 2. № 2. P. 393-408.

88. Murray W.D., Landis F. Numerical and machine solution of transient heat conduction problems involving melting or freezing // Trans. ASME. Ser. C. J. Heat Transfer. 1959. Vol. 2. № 2. P. 106-112.

89. Попов В.В., Горбачев И.И. Моделирование эволюции выделений в многокомпонентных сплавах // Физика металлов и металловедение. 2003. Т. 95. № 5. С. 16-25.

90. Попов В.В. Численное моделирование диффузионного взаимодействия выделений с матрицей в многокомпонентных системах // Изв. РАН. Металлы. 1997. № 2. С. 129-138.

91. Попов В. В. Моделирование превращений карбонитридов при термической обработке сталей. Екатеринбург: УрО РАН, 2003. 378 с.

92. Meyer L., BuMer Н.Е., Heisterkamp F. Metallkundliche Untersuchungen zur Wirkungsweise von Titan in unlegierten Baustahlen // Arch. Eisenhuttehw, 1972. Bd. 43. № 11. S. 823-832.

93. Martyshko P.S., Koksharov D.E. On the construction of the density sections using gravity data // Extended Abstracts of 66th EAGE Conference and Exhibition. Paris, 7-12 June 2004. P. 43.

94. Лаврентьев M.M. О некоторых некорректных задачах математической физики. Новосибирск: СО АН СССР, 1962.

95. Страхов В.Н., Иванов С.Н. Метод аналитического продолжения трехмерных потенциальных полей // Теория и практика геологической интерпретации гравитационных и магнитных аномалий. Алма-Ата, 1984. Т 2. С.68-70.

96. Пруткин И.Л. О предварительной обработке измерений, заданных на площади // Методы интерпретации и моделирования геофизических полей. Свердловск: УрО АН СССР, 1988. С. 11-15.

97. Васин В.В., Еремин И. И. Операторы и итерационные процессы Фейеровского типа. Теория и приложения. Екатеринбург: УрО РАН, 2005. 210 с.

98. Фаддеева В.Н., Фаддеев Д.К. Вычислительные методы линейной алгебры. М.: Гос. издат. физ.- мат. литературы, 1963. 734 с.

99. Акимова Е.Н. Параллельный алгоритм решения обратной задачи гравиметрии // Тезисы докладов Всероссийской конференции, посвященной 70-летию со дня рождения акад. А.Ф. Сидорова. Екатеринбург, 3-7 февраля 2003. С. 5-6.

100. Akimova E.N., У asín У. У Parallel iterative algorithms for solving th.e inverse gravity problems // Proceedings of the XXXII International Summer School "Advanced Problems in Mechanics" (APM'2004). St. Petersburg, Russia, June 24-Julyl, 2004. P. 1-8.

101. Акимова E.H., Белоусов Д. В. Решение обратной задачи гравиметрии с помощью параллельного алгоритма квадратного корня // Вестник УГТУ-УПИ. 2005. № 17 (69). С. 230-239.

102. Akimova E.N. The parallel algorithms for inverse gravimetry and magnetometry problems solving / / Abstracts of XXIV IUGG General Assembly. Perugia, Italy, 2-13 July 2007. URL: http://www.iugg2007perugia.it/webbook (дата обращения: 08.08.2009).

103. Парлет Б. Симметричная пролема собственных значений. Численные методы. Москва: Мир, 1983. 384 с.

104. Акимова E.H., Гемайдинов Д.В. Параллельные алгоритмы решения обратной задачи гравиметрии и организация удаленного взаимодействия между МВС-1000 и пользователем // Вычислительные методы и программирование. 2008. Т. 9. № 1. С. 133-144.

105. Нумеров В.В. Интерпретация гравитационных наблюдений в случае одной контактной поверхности // ДАН СССР. 1930. № 21. С. 569-574.

106. Малкин Н.Р. О решении обратной магнитометрической задачи для случая одной контактной поверхности (случай пластообразно залегающих масс) // ДАН СССР. Сер. А. 1931. № 9. С. 232-235.

107. Новоселицкий В.М. О построении плотностной границы по аномалиям силы тяжести // Прикладная геофизика. 1966. В. 47. С. 120-129.

108. Бакушинский A.B. Регуляризующий алгоритм на основе метода Ньютона-Канторовича для решения вариационных неравенств // Журнал вычислительной математики и математической физики, Т. 16. № 6. 1976. С. 1397-1404.

109. Стренг Г. Линейная алгебра и ее применения. М.: Мир, 1980. 456 с.

110. Акимова E.H. О сходимости метода Ньютона при решении обратной задачи гравиметрии // Тезисы докладов международной конференции "Алгоритмический анализ неустойчивых задач". Екатеринбург: УрГУ, 2008. С. 112-113.

111. Акимова E.H., Васин В.В. Параллельный алгоритм решения обратной задачи гравиметрии на основе регуляризованного метода Ньютона // Алгоритмы и программные средства параллельных вычислений. Екатеринбург: ИММ УрО РАН, 2002. Вып. 6. С. 51-64.

112. Akimoua E.N. Parallelization of an algorithm for solving the gravity inverse problem // Journal of Computational and Applied Mechanics. 2003. Vol. 4. №. 1. P. 5-12.

113. Akimova E.N., Vasin V.V. Stable parallel algorithms for solving the inverse gravimetry and magnetometry problems // International Journal Engineering Modelling. 2004. Vol. 17. Ж 1-2. P. 13-19.

114. Akimova E.N. The parallel algorithm for solving the gravity inverse problem // Proceeding of XXX Summer School "Advanced Problems in Mechanics" (APM'2002). St. Petersburg, Russia, June 27-July 6, 2002. P. 9-13.

115. Акимова Е.Н., Васин В. В. Решение обратных геофизических задач на многопроцессорном вычислительном комплексе // Материалы международной конференции, посвященной 50-летию Института геофизики УрО РАН. Екатеринбург: ИГФ УрО РАН, 2008. С. 4-7.

116. Акимова Е.Н., Скорик Г.Г. Регулярные методы решения обратной задачи гравиметрии // Сибирские электронные математические известия. Новосибирск: ИМ СО РАН, 2008. 9 с.

117. Акимова Е.Н. Распараллеливание алгоритма решения пространственной задачи упругости в случае заданного на границе вектора усилий // Алгоритмы и программные средства параллельных вычислений. Екатеринбург: ИММ УрО РАН, 1998. Вып. 2. С. 10-21.

118. Васин В.В., Акимова Е.Н. Параллельные алгоритмы решения трехмерной задачи упругости // Алгоритмы и программные средства параллельных вычислений. Екатеринбург: ИММ УрО РАН, 1999. Вып. 3. С. 34-47.

119. Akimova E.N. Parallelization of algorithm for solving the three-dimensional problem of elasticity // Journal of mechanical engineering. Bratislava, 2001. Vol. 5. Ж 52. P. 299-308.

120. Васин В.В., Акимова Е.Н. Параллельный алгоритм решения трехмерной задачи упругости в случае смешанных граничных условий // Алгоритмы и программные средства параллельных вычислений. Екатеринбург: ИММ УрО РАН, 2000. Вып. 4. С. 63-75.

121. Акимова E.H. Параллельные алгоритмы для решения трехмерной задачи упругости и разреженных линейных систем // Дальневосточный математический журнал. Владивосток: Дальнаука, 2001. Т. 2. № 2. С. 10-28.

122. Цвик Л.Б. Обобщение алгоритма Шварца на случай областей, сопряженных без налегания // ДАН. 1975. Т. 224 (2). С. 309-312.

123. Акимова E.H., Сереэюникова Т.Н. Распараллеливание алгоритма решения трехмерной задачи упругости методом граничных интегральных уравнений // Сиб. журн. вычисл. математики. 2000. Т. 3. № 2. С. 97-107.

124. Колтунов М.А., Васильев Ю.Н., Черных В.А. Упругость и прочность цилиндрических тел. М.: Высшая школа, 1975. 526 с.

125. Васин В.В., Сережникова Т.Н., Акимова E.H. Комплекс программ решения пространственных задач упругости методом граничных интегральных уравнений (МГИУ-2). Отчет ИММ УрО РАН. Екатеринбург, 1996. 107 с.

126. Акимова E.H. Параллельные алгоритмы решения обратных задач гравиметрии и магнитометрии на МВС-1000 // Труды междунар. научной конференции "Параллельные вычислительные технологии (ПаВТ'2009)". Челябинск: ЮУрГУ, 2009. С. 29-39.

127. Акимова E.H. Параллельные алгоритмы решения обратных задач гравиметрии и магнитометрии на МВС-1000 // Вестник ННГУ. 2009. № 4. С. 181-189.