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

Белоносов, Михаил Андреевич

Автореферат диссертации по теме "Организация параллельных вычислений для численного моделирования сейсмических волн на основе интегрального преобразования Лагерра и метода декомпозиции области"

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

БЕЛОНОСОВ Михаил Андреевич

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

25.00.10 - геофизика, геофизические методы поисков полезных ископаемых

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

1 7 ЯНВ 2013

НОВОСИБИРСК - 2012

005047922

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте нефтегазовой геологии и геофизики им. A.A. Трофимука Сибирского отделения Российской академии наук (ИНГГ СО РАН)

Научный руководитель:

доктор физико-математических наук, профессор Чеверда Владимир Альбертович

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

Поздняков Владимир Александрович, доктор технических наук, профессор, зав. кафедрой геофизики Федерального государственного автономного образовательного учреждения высшего профессионального образования «Сибирский Федеральный университет», г. Красноярск;

Костин Виктор Иванович, кандидат физико-математических наук, доцент, ФЛ ЗАО «ИНТЕЛ А/О» в г. Новосибирске, руководитель отдела по разработке программного обеспечения

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

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

Защита состоится 1 февраля 2013 г. в 10 час. на заседании диссертационного совета Д 003.068.03, созданного на базе Федерального государственного бюджетного учреждения науки Института нефтегазовой геологии и геофизики им. A.A. Трофимука Сибирского отделения Российской академии наук, в конференц- зале.

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

630090, г. Новосибирск, проспект Академика Коптюга, 3;

факс: (383) 333-25-13;

e-mail: NevedrovaNN @ ipgg.sbras.ru.

С диссертацией можно ознакомиться в библиотеке ИНГГ СО РАН Автореферат разослан 27 декабря 2012 г.

Ученый секретарь диссертационного совета, к.г.-м.н., доцент ' H.H. Неведрова

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

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

Актуальность. Развитие программно-алгоритмических средств численных методов моделирования сейсмических полей в упругих средах является чрезвычайно важным направлением, обеспечивающим дальнейшее совершенствование сейсмических методов изучения внутреннего строения Земли. В настоящее время ни одна площадная система геофизических наблюдений в районах со сложным сейсмологическим строением не реализуется без проведения предварительного полномасштабного моделирования для оценки информативности получаемых данных. Наибольшее распространение в данном направлении получили явные конечно-разностные схемы. На их основе созданы эффективные алгоритмы и разработано промышленное программное обеспечение, в том числе и ориентированное на использование вычислительных систем с параллельной архитектурой. Основным недостатком этих схем является их условная устойчивость, накладывающая весьма жёсткие ограничения на величину шага по времени в зависимости от шага по пространству. В то же время присущая им численная дисперсия не позволяет использовать крупные шаги по пространству. Всё это приводит порой к нереальным требованиям на вычислительные ресурсы, особенно при построении волновых сейсмических изображений. А при реализации миграции в обратном времени (Baysal Е., Kosloff D.D., Sherwood J.W.C. Geophysics. 1983. N. 48. P. 1514-1524) необходимо производить полное моделирование волнового поля для каждого нового источника.

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

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

Одним из возможных направлений дальнейшего развития здесь является декомпозиция области с последующей организацией альтернирования по Шварцу (Мацокин A.M., Непомнящих C.B. Изв. высш. уч. заведений. Математика. 1985. Т. 29. № 10. С. 61-66). Существенное уменьшение размерности задачи для каждой из подобластей не только ускоряет сходимость итерационного процесса, но и открывает путь к использованию прямых методов решения соответствующей системы линейных алгебраических уравнений. Однако применение этого подхода для матриц, возникающих в результате применения преобразования Фурье по времени, затруднительно в силу их знаконеопределённости: для таких матриц итерации по Шварцу, вообще говоря, могут и не сходиться.

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

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

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

Этапы исследования:

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

2. Постановка задачи и определение основного направления исследования.

3. Разработка алгоритмов.

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

5. Численные эксперименты по изучению основных свойств алгоритма: скорости сходимости аддитивного метода Шварца, масштабируемости, расчёту волновых полей и т.д. Теория и методы исследования

Теоретической основой решения поставленной научной задачи являются:

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

- метод Шварца, основанный на декомпозиции области;

- теория параллельных вычислений, разработка программного интерфейса обмена сообщениями в стандарте MPI-2, с использованием новых возможностей параллельных коллективных обменов и ввода/вывода в среде MPI-2 I/O.

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

Тестирование разработанного алгоритма проводилось на серии сейсмогеологических моделей, включая реалистичную двумерную модель Gullfaks одного из районов Северного моря (Fossen Н., Hesthammer J. Geological Society. London. Special Publications. 1998. V. 127. P. 231-261).

Защищаемые научные результаты:

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

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

Научная новизна. Личный вклад.

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

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

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

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

Новый способ организации параллельных вычислений для численного моделирования сейсмических волн с использованием преобразования Лагерра, декомпозиции области и метода Шварца, и реализация разработанных на его основе алгоритмов в виде научно-исследовательской версии программного обеспечения,

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

Детально исследованы свойства этих алгоритмов. В частности:

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

- численно исследована слабая и сильная масштабируемости алгоритма и показано, что они составляют примерно 60-^70%;

- рассчитаны волновые поля для различных двумерных моделей, среди которых реалистичная сейсмогеологическая модель одного из районов Северного моря — Си1^акя.

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

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

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

Результаты диссертационной работы известны научной общественности. Они докладывались и получили одобрение специалистов на 9 конференциях:

XLVII Международной научной студенческой конференции "Студент и научно-технический прогресс" (Новосибирск, 2009), VI Международной выставке и научном конгрессе "ГЕО-Сибирь-2010" (Новосибирск, 2010), Молодёжной международной научной школе-конференции "Теория и численные методы решения обратных и некорректных задач" (Новосибирск, 2010), Международном симпозиуме "Seismic waves in laterally inhomogeneous media VII" (Чешская Республика, Тепла, 2010), 20 Международной конференции по методам декомпозиции области "DD20" (США, Сан-Диего, 2011), XIV Всероссийской молодёжной конференции-школе с международным участием "Современные проблемы математического моделирования" (Новороссийск, 2011), Международной конференции по параллельному программированию "PARA12" (Финляндия, Хельсинки, 2012), Международной молодёжной конференции-школе "Современные проблемы прикладной математики и информатики" (Дубна, 2012), Международной суперкомпьютерной конференции "Научный сервис в сети интернет: поиск новых решений" (Новороссийск, 2012);

на научных семинарах Института нефтегазовой геологии и геофизики им. А.А. Трофимука Сибирского отделения РАН и Института вычислительной математики и математической геофизики Сибирского отделения РАН.

Результаты исследования по теме диссертации изложены в 10 научных публикациях, в том числе одна в ведущем научном рецензируемом журнале по перечню ВАК (Вычислительные методы и программирование) и 9 - в материалах российских и международных конференций и симпозиумов.

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

Диссертация состоит из введения, 4 глав, заключения и списка литературы из 77 наименований. Общий объём диссертации составляет 86 страниц, включая 30 рисунков и 2 таблицы.

Благодарности.

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

Автор выражает благодарность В.И. Самойловой за методические рекомендации и поддержку при подготовке диссертации.

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

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

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

Вторая глава содержит постановку прямой динамической задачи сейсмики для двумерной системы уравнений динамической теории упругости второго порядка и разработку параллельного алгоритма её решения, основанного на отделении времени с использованием интегрального преобразования Лагерра и последующей организации итерационного процесса по подобластям после декомпозиции области посредством аддитивного метода Шварца [2, 7]. После отделения времени интегральным преобразованием Лагерра выполняется её конечно-разностная аппроксимация.

В разделе 2.1 вводится интегральное преобразование Лагерра

/т = Г т ■ т-ь^т^ (1)

■'о

с формулой обращения

со

/СО = £ /т ■ (2)

т=О

где а - целое положительное, Н - вещественное положительное. В этих формулах ¿т - функции Лагерра, которые определяются выражением

где ¿^(ЛС) - обобщенные полиномы Лагерра. Исследованы свойства преобразования Лагерра в зависимости от значений параметров а и /г.

(3)

В разделе 2.2 рассматривается двумерная система уравнений динамической теории упругости второго порядка с нулевыми начальными данными для источника типа центр объёмного расширения д д PiuJtt = ШЩ)* + *(u2)z] + ^ [Ц(и2)х + H(Mi)z] +

+8'x(x-x0,z-z0)f(t), д д p(«2)tt = gj [м(и2)х + m("i)z] + ^ [ACщ)х + (я + 2i0(u2)z] +

+6'z(x - x0lz - z0)f(t), где p - плотность среды, Я, ц - её коэффициенты Ламе, (х0, z0) -координаты источника, a /(t) задаёт форму излучаемого им импульса.

Далее к системе уравнений (3) применяется интегральное преобразование Лагерра (1), в результате чего она трансформируется к виду:

^[(Я + 2/х)«)* + Я(и?)2] + А[//(ип);с + ^(ип)2] - p^-uj = F",

^ [ц№)х + //(и?),] + ^ [Л(и?)х + (Я + 2М)(и?) J - p^j-u? = F",

где Fi(x,z,u°, и F^ipc.z.u®, ....u"-1) - рекуррентно

вычисляемые правые части.

В системе (4) пространственный оператор в левой части отрицательно определён, что позволяет организовать сходящийся итерационный процесс на основе аддитивного метода Шварца. Кроме того, этот оператор не зависит от параметра разделения п. Благодаря этому при численном решении матрица конечно-разностной аппроксимации вычисляется один раз, более того, и её LU-разложение может быть вычислено только один раз.

В разделе 2.3 для того, чтобы избежать искусственных отражений от границы области, вводится её окаймление идеально подходящим поглощающим слоем - PML (аббревиатура от английского Perfectly Matched Layer).

В разделе 2.4 описываются этапы решения задачи после отделения времени:

1) Для каждого п решается система уравнений (4) и строятся функции и" и и";

2) Вычисляется обратное преобразование Лагерра (2) и находится искомое решение во временной области.

Особое внимание уделяется формулировке критерия выбора необходимого числа функций Лагерра п:

(4)

Функция источника f(t) размещается в конечной точке Т временного интервала; к ней применяются прямое и обратное преобразование Лагерра (1) и (2) при п= 1,..., /V, и результат сравнивается с f(t); изменением числа N обеспечивается необходимый уровень точности.

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

1 ..

к. • i • i

• 1 • i

J+1

J-1

1-3/2

1-1/2

1+1/2

Рис. I. Шаблон конечно-разностной схемы, используемой для аппроксимации системы (4). □ и о соответствуют точкам, в которых вычисляются и" и и"; вспомогательные переменные а вычисляются в точках, обозначенных треугольниками.

Такая аппроксимация для каждого значения параметра п даёт систему линейных алгебраических уравнений (СЛАУ) с девятьюдиагональной квадратной матрицей. Для решения соответствующих систем линейных алгебраических уравнений используется решатель Pardiso из Intel® Math Kernel Library (Intel® MKL).

Поскольку основной объем оперативной памяти тратится на хранение LU-разложения, особое внимание в разделе уделяется численным экспериментам по определению её необходимого объёма для различных размеров расчётной области. Так, для области 1600 X 1600 точек необходимо иметь в распоряжении более 6 Гб оперативной памяти.

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

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

Основным достоинством метода Шварца является возможность организации вычислений в каждой отдельной элементарной подобласти, возникающей в результате пространственной декомпозиции исходной целевой области при организации обменов между соседями (рис.2). Так, для нахождения решения в области £), вводится её разбиение на перекрывающиеся подобласти О, и 02 (рис. 2а). На первой итерации метода Шварца решение находится в этих подобластях с произвольными граничными условиями Дирихле на границах и 52. На последующих итерациях на каждой из этих границ ставится условие Дирихле с функцией, равной значению уже найденного решения задачи на предыдущей итерации из соседней подобласти. Сходимость итерационного процесса гарантируется знакоопределённостью оператора и наличием перекрытия. В общем случае декомпозиция проделывается как показано на рис.26.

Б,

Б

а) б)

Рис. 2. Декомпозиция области с перекрытием на две подобласти (слева); декомпозиция расчётной области с перекрытием на 9 подобластей (справа): в зелёных областях пересекаются 2 подобласти, в красных - 4 подобласти.

В качестве критерия остановки для метода Шварца используется достижение заранее заданного порогового значения величиной, характеризующей относительную изменчивость решения на двух последовательных итерациях:

р _ ЛК-иЗПг К-иГЧЦ гг~ \ 1К"1Г ' [Н-% г

где Г есть объединение всех границ, вводимых декомпозицией области. В приводимых далее численных экспериментах было выбрано Етг < Ю-5.

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

гибридной параллельной архитектурой [6, 7]. Численные эксперименты показали, что для достаточно большой ширины перекрытия скорость сходимости метода Шварца растёт приблизительно как п в одномерном случае и приблизительно как Vn в двумерном случае, где л число подобластей. Также показывается высокая эффективность и масштабируемость параллельного алгоритма. Представлены результаты численных экспериментов для различных неоднородных сред, в том числе для реалистичной сейсмогеологической модели.

Раздел 3.1 посвящен описанию этапов организации параллельных вычислений при реализации предложенного алгоритма:

1) декомпозиция расчетной области на элементарные подобласти такой размерности, которая позволяет хранить LU-декомпозицию в общей оперативной памяти (shared memory);

2) использование PARDISO MKL для эффективной организации параллельных вычислений при решении соответствующей системы линейных алгебраических уравнений на данном узле с использованием ОрепМР (SMP-архитектура);

3) организация обменов между подобластями при выполнении альтернирований по Шварцу с использованием библиотеки MPI (МРР-архитектура).

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

Раздел 3.3 посвящён численному исследованию скорости сходимости аддитивного метода Шварца для двумерной однородной среды. Показывается, что при разбиении на M = К2 подобластей, когда источник находится в средней подобласти, число итераций аддитивного метода Шварца растёт как К + 2 .

В разделе 3.4 исследуются слабая и сильная масштабируемости разработанного параллельного алгоритма (рис.3).

Т(п)/Т(9) 1

с!Т(н) 1.5

1.0

9 25 49 81

Количество вычислительных узлов

а)

2345678 9 Количество вычислительных узлов/9

б)

Рис. 3. Масштабируемость параллельного алгоритма: а) слабая, б) сильная.

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

1) Вертикально-неоднородная слоистая среда (рис.4, слева). Волновое поле (рис. 4, справа) рассчитывалось до Зс, при этом при выполнении преобразования Лагерра брались Н = 300, а = 3 и п = 450, что давало относительную ошибку Ю-5. Метод Шварца сходится затри итерации.

2) Неоднородная среда с углами (рис.5, слева). Моментальный снимок рассчитанного волнового поля представлен на рис.5 справа. Метод Шварца сходится за 4 итерации.

0

1000

200

1000

V =3600 м/с

р

V =5000 м/с

р

§

и

х, м

1000

X, м

1000

Рис. 4. Горизонтально-слоистая неоднородная среда (слева); моментальный снимок рассчитанного волнового поля (справа) для модели слева.

Рис. 5. Неоднородная среда из двух слоев с углами (слева); моментальный снимок рассчитанного волнового поля (справа) для модели слева.

В разделе 3.6 рассматривается численный эксперимент по изучению алгоритма на примере реалистичной двумерной сейсмогеологической модели одного из районов Северного моря - на модели СиМакБ (рис.6, слева). Источник находится в верхнем слое (в воде). Расчётная область разбивается на 3x3 подобласти. Метод Шварца сходится за 10 итераций. Моментальный снимок волнового поля представлен на правом изображении рис. 6.

X, м м

Рис. 6. Распределение скорости продольных волн для реалистичной двумерной сейсмогеологической модели района Северного моря СшШакв (слева); моментальный снимок рассчитанного волнового поля (справа) для модели ОиШакв.

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

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

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

ИЗМЕЛЬЧЕНИЕ СЕТКИ

Рис. 7. Декомпозиция расчётной области на девять подобластей. В жёлтой подобласти производится измельчение сетки.

На рис.8 приведён результат численного эксперимента, реализующего упомянутый выше алгоритм локального измельчения. Для декомпозиции области, представленной на рис.7 во внутреннем квадрате используется сетка с шагом в три раза меньшим, чем во всех остальных подобластях. Моментальный снимок волнового поля представлен на рис.8. Амплитуда артефакта, возникающего при прохождении волны через область с локальным измельчением, составляет 0,5% от амплитуды падающей волны.

1800

900 х. ы 1800

Рис. 8. Моментальный снимок волнового поля при локальном измельчении сетки в 3 раза (в синем квадрате).

Раздел 4.3 посвящен организации численного моделирования одновременно для нескольких источников. Такая возможность основывается на независимости оператора, стоящего в левой части (4), от параметра разделения п и от функции источника, поэтому LU-разложение выполняется один раз и сразу для всех источников. С его использованием впоследствии и решается система уравнений для одной матрицы и нескольких правых частей. Используемый решатель Pardiso из Intel® MKL распараллелен и оптимизирован под многоядерные системы с общей памятью (ОрепМР), что обеспечивает эффективную загрузку всех вычислительных ядер. Кроме того, организация пересылок при реализации метода Шварца в виде одного пакета сразу для всех источников также существенно повышает эффективность вычислений.

Чтобы убедиться в значимости описанных преимуществ, был проделан численный эксперимент. Для двумерной неоднородной среды, представленной на рис.6, была выполнена, как и в предыдущем случае, декомпозиция на девять перекрывающихся подобластей, обеспечившая максимальную загрузку процессорных элементов. После этого для различного числа источников выполнялось численное моделирование волновых полей с одновременным вычислением нормализованного времени T(tn) = —, где tn - время расчёта задачи для п источников. Результат представлен на рис.9. Из рисунка видно, что происходит ускорение почти в два раза для 72 различных источников по сравнению с последовательным решением серии независимых задач для одного источника.

Количество источников

1.1

0.6

0.9

0.8

0.7

0.5

0 10 20 30 40 50 60 70

Рис. 9. Нормализованное время вычисления для одновременного моделирования для нескольких источников.

ЗАКЛЮЧЕНИЕ

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Белоносов, М.А. Применение интегрального преобразования Лагерра и метода декомпозиции области для численного решения волнового уравнения / М.А. Белоносов // ХЬУП Междунар. науч. студ. конф. "Студент и научно-технический прогресс" (Новосибирск, 2009 г.). - Новосибирск, 2009. - С. 56.

2. Белоносов, М.А. Организация параллельных вычислений на основе процесса альтернирования по Шварцу применительно к численному моделированию сейсмических волн [Электронный ресурс] / М.А. Белоносов // Молодёж. междунар. науч. школа-конференция "Теория и численные методы решения обратных и некорректных задач" (Новосибирск, 21-29 сент. 2010 г.). - Режим доступа свободный: http://math.nsc.ai/conference/onzlO/thesis/abstracts.pdf

3. Белоносов, М.А. Применение интегрального преобразования Лагерра и метода декомпозиции области для численного моделирования сейсмических волновых полей. Ч. 1. Недропользование. Горное дело. Новые направления и технология поиска, разведки и разработки месторождений полезных ископаемых. / М.А. Белоносов // VI Междунар. выставка и науч. конгресс «ГЕО-СИБИРЬ-2010» (Новосибирск, 19-29 апр. 2010 г.). -Новосибирск, 2010. - Т. 2. - С. 122-126.

4. Belonosov, М.А. Parallel implementation of numerical simulation of elastic waves on the base of Laguerre transform followed by domain decomposition [Electronic source] / M.A. Belonosov, G.V. Reshetova et al. // WORKSHOP MEETING SEISMIC WAVES IN LATERALLY INHOMOGENEOUS MEDIA VII (Czech Republic, Tepla, June 21-26, 2010 year): Proceedings. - Режим доступа свободный: littr>://sw3d.c?./swlim/.

5. Belonosov, M.A. Simulation of Elastic Waves by Schwartz Alternations After Application of Laguerre Transform in Time [Electronic source] / M.A. Belonosov C. Kostov et al. // 20-th International Conference on Domain Decomposition Methods (United States, San Diego, February 7-11, 2011 year): Proceedings. - P. 255. - Режим доступа свободный: http://ccom.ucsd.edu/~dd20/downloads/dd20-abstracts.pdf.

6. Белоносов, М.А. Численное моделирование сейсмических волн на основе интегрального преобразования Лагерра и метода альтернирования по Шварцу / М.А. Белоносов, Г.В. Решетова, В.А. Чеверда // XIV Всероссийская молодёж. конференция-школа с междунар. участием "Современные проблемы математического моделирования" (Новороссийск, 12-17 сент.

2011 г.).-Новороссийск, 2011.-С. 63-67.

7. Белоносов, М.А. Организация параллельных вычислений для моделирования сейсмических волн с использованием аддитивного метода Шварца / М.А. Белоносов, Г.В. Решетова, В.А. Чеверда и др. // Вычислительные методы и программирование. - 2012. - Т. 13. - С. 525-535. (рек. перечнем ВАК)

8. Belonosov, М.А. Parallel numerical simulation of seismic wave propagation with Intel® Math Kernel Library [Electronic source] / M.A. Belonosov, S.A. Solovev, V.A. Tcheverda et al. // Workshop on the State-of-the-Art in Scientific and Parallel Computing PARA 12 (Finland, Helsinki, June 10-13,

2012 year): Proceedings. - Режим доступа свободный: http://www.csc.fi/english/pages/para2012/ргортат/рага 12 abstracts/para 12 belon osov.

9. Белоносов, M.A. Параллельный алгоритм для численного моделирования сейсмических волн с использованием интегрального преобразования Лагерра / М.А. Белоносов, С.А. Соловьёв, В.А. Чеверда и др. // Междунар. молодёж. конференция-школа "Современные проблемы

прикладной математики и информатики" (Дубна, 22-27 авг. 2012 г.). - Дубна: ОИЯИ, 2012.-С. 53-57.

10. Белоносов, М.А. Моделирование сейсмических волн на многопроцессорных вычислительных системах с распределённой памятью, основанное на интегральном преобразовании JIareppa и аддитивном методе Шварца [Электронный ресурс] / М.А. Белоносов, С.А. Соловьёв, В.А., Чеверда и др. // Тр. Междунар. суперкомпьютерной конф. "Научный сервис в сети интернет: поиск новых решений" (Новороссийск, 17-22 сент. 2012). -М.: Изд-во МГУ, 2012. - С. 222-226 (CD-ROM).

Технический редактор Е.В.Бекренёва Подписано в печать 20.12.2012 Формат 60x84/16. Бумага офсет №1. Гарнитура Тайме _Печ.л. 0,9. Тираж 120. Зак. № 83_

ИНГГ СО РАН, 630090, Новосибирск, просп. Акад. Коптюга, 3

Содержание диссертации, кандидата физико-математических наук, Белоносов, Михаил Андреевич

ВВЕДЕНИЕ.

Глава 1. ИЗУЧЕННОСТЬ РЕШЕНИЯ ЗАДАЧИ.

Глава 2. АЛГОРИТМ МОДЕЛИРОВАНИЯ

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

2.1 Преобразование Лагерра и его свойства.

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

2.3 Ограничение расчётной области.

2.4 Постановка задачи после отделения времени.

2.5 Численная аппроксимация решаемой системы и ЬИ- разложение.

2.6 Декомпозиция расчётной области и аддитивный метод Шварца.

Глава 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

И ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ.

3.1 Организация параллельных вычислений.

3.2 Исследование скорости сходимости метода Шварца в одномерном случае.

3.3 Исследование скорости сходимости метода Шварца в двумерном случае.

3.4 Слабая и сильная масштабируемость параллельного алгоритма.

3.5 Численные эксперименты для простых неоднородных сред.

3.6 Численные эксперименты для реалистичной модели среды.

Глава 4. ЛОКАЛЬНОЕ ИЗМЕЛЬЧЕНИЕ СЕТОК

И ОДНОВРЕМЕННОЕ МОДЕЛИРОВАНИЕ

ДЛЯ НЕСКОЛЬКИХ ИСТОЧНИКОВ.

4.1 Одномерное локальное измельчение сеток.

4.2 Двумерное локальное измельчение сеток.

4.3 Одновременное моделирование для нескольких источников.

Введение Диссертация по наукам о земле, на тему "Организация параллельных вычислений для численного моделирования сейсмических волн на основе интегрального преобразования Лагерра и метода декомпозиции области"

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

Актуальность. Развитие программно-алгоритмических средств численных методов моделирования сейсмических полей в упругих средах является чрезвычайно важным направлением, обеспечивающим дальнейшее совершенствование сейсмических методов изучения внутреннего строения Земли. В настоящее время ни одна площадная система геофизических наблюдений в районах со сложным сейсмологическим строением не реализуется без проведения предварительного полномасштабного моделирования для оценки информативности получаемых данных. Наибольшее распространение в данном направлении получили явные конечно-разностные схемы. На их основе созданы эффективные алгоритмы и разработано промышленное программное обеспечение, в том числе и ориентированное на использование вычислительных систем с параллельной архитектурой. Основным недостатком этих схем является их условная устойчивость, накладывающая весьма жёсткие ограничения на величину шага по времени в зависимости от шага по пространству. В то же время присущая им численная дисперсия не позволяет использовать крупные шаги по пространству. Всё это приводит порой к нереальным требованиям на вычислительные ресурсы, особенно при построении волновых сейсмических изображений. А при реализации миграции в обратном времени [22] необходимо производить полное моделирование волнового поля для каждого нового источника.

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

Одним из возможных направлений дальнейшего развития здесь является декомпозиция области с последующей организацией альтернирования по Шварцу [13]. Существенное уменьшение размерности задачи для каждой из подобластей не только ускоряет сходимость итерационного процесса, но и открывает путь к использованию прямых методов решения соответствующей системы линейных алгебраических уравнений. Однако применение этого подхода для матриц, возникающих в результате применения преобразования Фурье по времени, затруднительно в силу их знаконеопределённости: для таких матриц итерации по Шварцу, вообще говоря, могут и не сходиться.

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

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

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

Этапы исследования:

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

2. Постановка задачи и определение основного направления исследования.

3. Разработка алгоритмов.

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

5. Численные эксперименты по изучению основных свойств алгоритма: скорости сходимости аддитивного метода Шварца, масштабируемости, расчёту волновых полей и т.д.

Теория и методы исследования

Теоретической основой решения поставленной научной задачи являются:

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

- метод Шварца, основанный на декомпозиции области;

- теория параллельных вычислений, разработка программного интерфейса обмена сообщениями в стандарте MPI-2, с использованием новых возможностей параллельных коллективных обменов и ввода/вывода в среде MPI-2 I/O.

При разработке программного обеспечения для решения системы линейных алгебраических уравнений использовалась библиотека Intel®Math Kernel Library.

Тестирование разработанного алгоритма проводилось на серии сейсмогеологических моделей, включая реалистичную двумерную модель Gullfaks одного из районов Северного моря [35].

Защищаемые научные результаты:

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

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

Научная новизна. Личный вклад.

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

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

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

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

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

Детально исследованы свойства этих алгоритмов. В частности:

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

- численно исследована слабая и сильная масштабируемости алгоритма и показано, что они составляют примерно 60-^-70%;

- рассчитаны волновые поля для различных двумерных моделей, среди которых реалистичная сейсмогеологическая модель одного из районов Северного моря - Ои^акз.

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

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

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

Результаты диссертационной работы известны научной общественности. Они докладывались и получили одобрение специалистов на 9 конференциях:

XLVII Международной научной студенческой конференции "Студент и научно-технический прогресс" (Новосибирск, 2009), VI Международной выставке и научном конгрессе "ГЕО-Сибирь-2010" (Новосибирск, 2010), Молодёжной международной научной школе-конференции "Теория и численные методы решения обратных и некорректных задач" (Новосибирск, 2010), Международном симпозиуме "Seismic waves in laterally inhomogeneous media VII" (Чешская Республика, Тепла, 2010), 20 Международной конференции по методам декомпозиции области "DD20" (США, Сан-Диего, 2011), XIV Всероссийской молодёжной конференции-школе с международным участием "Современные проблемы математического моделирования" (Новороссийск, 2011), Международной конференции по параллельному программированию "PARA 12" (Финляндия, Хельсинки, 2012), Международной молодёжной конференции-школе "Современные проблемы прикладной математики и информатики" (Дубна, 2012), Международной суперкомпьютерной конференции "Научный сервис в сети интернет: поиск новых решений" (Новороссийск, 2012); на научных семинарах Института нефтегазовой геологии и геофизики им. A.A. Трофимука Сибирского отделения РАН и Института вычислительной математики и математической геофизики Сибирского отделения РАН.

Результаты исследования по теме диссертации изложены в 10 научных публикациях, в том числе одна в ведущем научном рецензируемом журнале по перечню ВАК (Вычислительные методы и программирование) и 9 - в материалах российских и международных конференций и симпозиумов.

Благодарности.

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

Автор выражает благодарность В.И. Самойловой за методические рекомендации и поддержку при подготовке диссертации.

Заключение Диссертация по теме "Геофизика, геофизические методы поисков полезных ископаемых", Белоносов, Михаил Андреевич

Заключение

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

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

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

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

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

Библиография Диссертация по наукам о земле, кандидата физико-математических наук, Белоносов, Михаил Андреевич, Новосибирск

1. Алексеев, A.C. Численное моделирование распространения сейсмических волн в радиально-неоднородной модели Земли / A.C. Алексеев, Б.Г. Михайленко // Докл. АН СССР. 1977. - Т. 235. - № 1. -С. 46-49.

2. Василевский, Ю.В. Краткий курс по многосеточным методам и методам декомпозиции области / Ю.В. Василевский, М.А. Ольшанский -М.: Изд-во МГУ, 2007. 100 с.

3. Гилбо, Ж. Численное моделирование сейсмических волновых полей в двумерно-неоднородных упругих разномасштабных средах (карстовые включения) / Ж. Гилбо, Е. Ланда, Г.В. Решетова и др. // Технологии сейсморазведки. 2008. - № 3. - С. 19-28.

4. Годунов, С.К. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах / С.К. Годунов, А.Г. Антонов, О.П. Кирилюк Годунов и др. 2-е изд., перераб. и доп. Новосибирск: Наука, 1992. - 360 с.

5. Коновалов, А.Н. Введение в вычислительные методы линейной алгебры / А.Н. Коновалов Новосибирск: Наука, 1993. - С. 17-31.

6. Конюх, Г.В. Применение интегрального преобразования Лагерра при решении динамических задач сейсмики / Г.В. Конюх, Б.Г. Михайленко // Тр. ИВМиМГ СО РАН. Сер. Мат. моделирование в геофизике. 1998. -№5.-С. 106-123.

7. Костин, В.И. Конечно-разностный метод численного моделирования распространения сейсмических волн в трехмерно-неоднородных разномасштабных средах / В.И. Костин, В.В. Лисица, Г.В.

8. Решетова и др. // Вычислительные методы и программирование. 2011. — Т. 12.-№2.-С. 85-93.

9. Левченко, В.Д. Асинхронные алгоритмы как способ достижения 100% эффективности вычислений / В.Д. Левченко // Информационные технологии и вычислительные системы. 2005. - № 1. - С. 68-75.

10. Мацокин, A.M. Метод альтернирования Шварца в подпространствах / A.M. Мацокин, С. В. Непомнящих Изв. высш. уч. заведений. Математика, 1985. - Т. 29. - № 10. - С. 61-66.

11. Непомнящих, C.B. Метод альтернирования Шварца для вырожденной задачи Неймана / C.B. Непомнящих Вычислительные алгоритмы в задачах мат. физики. - Новосибирск, 1985. - С. 99-112.

12. Решетова, Г.В. Использование преобразования Лагерра для построения идеально подходящих поглощающих слоев без расщепления / Г.В. Решетова, В.А. Чеверда // Математическое моделирование. 2006. — Т. 18. -№ 10.-С. 91-101.

13. Свешников, В.М. О расчете интенсивных пучков заряженных частиц методом итераций по подобластям без налегания / В.М. Свешников // Прикладная физика. 2006. - № 3. - С. 49-57.

14. Суетин, П.К. Классические ортогональные многочлены / П.К. Суетин М.: Наука, 1974. - С. 203-243.

15. Фатьянов, А.Г. Метод расчёта нестационарных волновых полей в неупругих слоисто-неоднородных средах / А.Г. Фатьянов, Б.Г. Михайленко // Докл. АН СССР. 1988. - Т. 301. - № 4. - С. 1024-1027.

16. Alford, R.M. Accuracy of finite-difference modeling of the acoustic wave equation / R.M. Alford, K.R. Kelly, D.M. Boore // Geophysics. 1974. -V. 39.-P. 834-842.

17. Bayliss, A. A fourth order accurate finite-difference scheme for the computation of elastic waves / A. Bayliss, K.E. Jordan, B.J. Lemesurier et al. // Bull. Seis. Soc. Am. 1986. - V. 76. - P. 1115-1132.

18. Baysal, E. Reverse time migration / E. Baysal, D.D. Kosloff, J.W.C. Sherwood//Geophysics. 1983.-N. 48.-P. 1514-1524.

19. Berenger, J.P. A perfect matched layer for the absorption of electromagnetic waves / J.P. Berenger // Journal of Comp. Physics. 1994. — N. 114.-P. 185-200.

20. Boore, D.M. Finite-difference methods for seismic wave propagation in heterogeneous materials / D.M. Boore // Methods in Computation Physics. -1972.-V. 11.-P. 1-37.

21. Calhoun, D.A. Logically Rectangular Grids and Finite Volume Methods for PDEs in Circular and Spherical Domains / D.A. Calhoun, C. Helzel // SIAM Review 50(4). 2008. - P. 723-752.

22. Carcione, J.M. A Chebyshev collocation method for the elastodynamic equation in generalized coordinates / J.M. Carcione, J.P. Wang // Comput. Fluid Dynamics. 1993. - V. 2. - P. 269-290.

23. Chan, T. Domain decomposition / T. Chan, T.P. Mathew // Acta Numerica. 1994. - V. 3. - P. 61-143.

24. Clement, F. Solution of the 3D Helmholtz equation by conjugate gradients / F. Clement, M. Kern, C. Rubin // In Copper mountain conference on iterative methods (USA, Denver, April 1-5, 1990 year). 1990.

25. Colella, P. Performance and scaling of locally-structured grid methods for partial differential equations / P. Colella, J. Bell, N. Keen, T. Ligocki, M. Lijewski, B. van Straalen // Journal of Physics: Conference Series. 78 012013. -2007.

26. Collino, F. Domain Decomposition Method for Harmonic Wave Propagation / F. Collino, S. Ghanemi, P. Joly // INRIA, Rapport de recherché. -1998.-N. 3473.-P. 4-24.

27. Collino, F. Application of the PML absorbing layer model to the linear elastodynamic problem in anisotropic heterogeneous media / F. Collino, C. Tsogka//Geophysics.-2001. -V. 66. -N. 1,P. 294-307.

28. Collino, F. A Conservative Space-time Mesh Refinement Method for the 1-DWave Equation. Part 1: Construction / F. Collino, T. Fouquet, P. Joly // Numer. Math. -2003. V. 95.-P. 197-221.

29. Diaz, J. Energy Conserving Explicit Local Time Stepping for Second-Order Wave Equations / J. Diaz, M.J. Grote // SIAM Journal on Scientific Computing.-2009.-N. l.-P. 1985-2014.

30. Dryja, M. Domain decomposition algorithms with small overlap / M. Dryja, O.B. Widlund // SIAM, J. Sci. Comp. 15(3). 1994. - P. 604-620.

31. Haskell, N.A. The dispersion of surface waves in multi-layered media / N.A. Haskell // Bull. Seism. Soc. Am. 1953. - V. 43. - P. 17-43.

32. Holdberg, O. Computational aspects of the choice of operator and sampling interval for numerical differentiation in large-scale simulation of wave phenomena / O. Holdberg // Geophys. Prosp. 1987. - V. 35. - P. 629-655.

33. Jo, C.H. An optimal 9-point, finite-difference, frequency-space, 2D scalar wave extrapolator / C.H. Jo, C.S. Shin, J.H. Suh // Geophysics. 1996. -V. 61.-P. 529-537.

34. Joly, P. Analyse numerique d'une methode de raffinement de maillage espace-temps pour l'équation des ondes / P. Joly, F. Collino, T. Fouquet // INR1A, Rapport de recherché. 1998. - N. 3474. - P. 3-56.

35. Joly, P. An Error Analysis of Conservative Space-Time Mesh Refinement Methods for the One-Dimensional Wave Equation / P. Joly, J. Rodriguez // SIAM Journal on Numerical Analysis 43(2). 2005. - P. 825-859.

36. Karypis, G. A fast and high quality multilevel scheme for partitioning irregular graphs / G. Karypis, V. Kumar // SIAM J. on Scientific Computing. -1998.-V. 20.-N. 1.-P. 359-392.

37. Kelly, K.R. Synthetic seismograms: a finite-difference approach / K.R. Kelly, R. W. Ward, R. M. Alford et al. // Geophysics. 1976. - V. 41. -P. 2-27.

38. Konyukh, G.V. Integral Laguerre transform as applied to forward seismic modeling / G.V. Konyukh, B.G. Mikhailenko, A.A. Mikhailov // Bull, of the Novosibirsk Computing Center, series Mathematical Modeling in Geophysics. 1999.-V. 5.-P. 71-91.

39. Konyukh, G.V. Application of the integral Laguerre transforms for forward seismic modeling / G.V. Konyukh, B.G. Mikhailenko, A.A. Mikhailov // Journal of Computational Acoustics. 2001. - V. 9. - N. 4. - P. 1523-1541.

40. Korneev, V.I. Modelling of seismic waves propagation for 2D media (direct and inverse problems) / V.I. Korneev, V.I. Kostin, V.V. Kovalevsky et al. // Lecture Notes in Computer Sciences. 1997. - V. 1277. - P. 350-357.

41. Kosloff, D. Elastic wave calculations by the Fourier method / D. Kosloff, M. Reshef, D. Loewenthal // Bull. Seis. Soc. Am. 1984. - V. 74. - P. 875-891.

42. Kosloff, D. Solution of equations of dynamic elasity by a Chebyshev spectral method / D. Kosloff, A. Filho, D. Kessler // Geophysics. 1990. -V. 55.-P. 734-748.

43. Kwak, D.Y. Domain decomposition for model heterogeneous anisotropic problems / D.Y. Kwak, S.V. Nepomnyaschikh, H.C. Pyo // Numer. Lin. Alg. Appl. 2003. - N. 10.-P. 129-157.

44. Lysmer, B. A finite-element method for seismology / B. Lysmer, N. Drake // In Bolt B.A. Eds., Methods in computational physics, Seismology: Surface waves and Earth oscillations. 1972. - V. 11. - P. 181-216.

45. Marfiirt, K.J. Accuracy of finite-difference and finite-element modeling of the scalar and elastic wave equations / K.J. Marfiirt // Geophysics. -1984.-V. 49.-P. 533-549.

46. McCully, J. The Laguerre transform / J. McCully // SIAM Review. -1960.-V. 2.-N. 3.-P. 185-191.

47. McMechan, G.A. Determination of source parameters by wavefield extrapolation / G.A. McMechan // Geophys. J. Roy. Astr. Soc. 1982. - V. 71. -P. 613-628.

48. McMechan, G.A. Migration by extrapolation of time-dependent boundary values / G.A. McMechan // Geophysical Prospecting. 1983. - V. 31. -P. 413-420.

49. Mikhailenko, B.G. Numerical viscoelastic modeling by the spectral Laguerre method / B.G. Mikhailenko, A.A. Mikhailov, G.V. Reshetova // Geophysical Prospecting. 2003. - V. 51. - P. 37-48.

50. Miller, K. Numerical analogs to the Schwarz alternating procedure / K. Miller//Numer. Math. 1965.-N. 7-P. 91-103.

51. Muller, G. The reflectivity method; a tutorial / G. Muller // Geophysics. 1985. - V. 58. - P. 153-174.

52. Nepomnyashchikh, S.V. Domain decomposition methods / S.V. Nepomnyashchikh // Radon Series Comput. Appl. Math. 2007. - N. 1. -P. 81-159.

53. Pissarenko, D. 3D finite-difference synthetic acoustic log in cylindrical coordinates: parallel implementation / D. Pissarenko, G. Reshetova, V. Tcheverda // J. of Computational and Applied Mathematics. 2010. - V. 234. -N. 6.-P. 1766-1772.

54. Plessix, R.E. A Helmholtz iterative solver for 3D seismic-imaging problems / R.E. Plessix // Geophysics. 2007. - V. 72. - N. 5. - SMI 85-SM194.

55. Robertsson, J. Viscoelastic finite-difference modeling / J. Robertsson, J. Blanch, W. Symes // Geophysics. 1999. - V. 64. - P. 1444-1456.

56. Schenk, O. Efficient sparse LU factorization with left-right looking strategy on shared memory multiprocessors / O. Schenk, K. Gartner, W. Fichtner // BIT. 2000. - V. 240. - N. 1. - P. 158-176.

57. Schenk, O. Sparse factorization with two-level scheduling in PARDISO / O. Schenk, K. Gartner // Proc. of the 10th SIAM Conf. on Parallel Processing for Scientific Computing. Portsmouth. 2001.

58. Schenk, O. Two-level scheduling in PARDISO: improved scalability on shared memory multiprocessing systems / O. Schenk, K. Gartner // Parallel Computing. -2002. -N. 28. P. 187-197.

59. Stekl, I. Accurate viscoelastic modeling by frequency-domain finite-difference using rotated operators / I. Stekl, R.G. Pratt // Geophysics. 1998. -V. 63.-P. 1779-1794.

60. Tal-Ezer, H. An accurate scheme for seismic forward modeling / H. Tal-Ezer, D. Kosloff, Z. Koren // Geophys. Prosp. 1987. - V. 35. - P. 479-490.

61. Thomson, W.T. Transmission of elastic waves through a stratified solid / W.T. Thomson // J. Appl. Phys. 1950. - V. 21. - P. 89-93.

62. Virieux, J. P-SV wave propagation in heterogeneous media: Velocity -stress finite-difference method / J. Virieux // Geophysics 51(4). 1986. - P. 889-901.

63. Whitmore, D. Iterative depth migration by backward time propagation / D. Whitmore // 53rd Annual International Meeting, SEG, Expanded Abstracts. 1983.-P. 382-385.

64. Zahradnik, J. Heterogeneous formulations of elastodynamic equations and finite-difference schemes / J. Zahradnik, E. Priolo // Geophysical Journal International 120(3). 1995. - P. 663-676.