Параллельные алгоритмы решения задач грави-магнитометрии и упругости на многопроцессорных системах с распределенной памятью тема диссертации и автореферата по ВАК РФ 05.13.18, доктор физико-математических наук Акимова, Елена Николаевна

• Акимова, Елена Николаевна
• доктор физико-математических наук
• 2009

Оглавление диссертации доктор физико-математических наук Акимова, Елена Николаевна

Введение

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 решения трехмерной статической задачи упругости в ограниченных областях с различными типами граничных условий с использованием параллельных вычислительных технологий на всех этапах решения задачи и протестирован на серии модельных расчетов.

Заключение

Список литературы диссертационного исследования доктор физико-математических наук Акимова, Елена Николаевна, 2009 год

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.