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

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

004614ИУ >

Терехов Андрей Валерьевич

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

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

программ

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

" 2 ДЕН 2010

Новосибирск - 2010

004614897

Работа выполнена в Учреждении Российской академии наук Институте вычислительной математики и математической геофизики Сибирского

отделения РАН.

Защита состоится « 21 » декабря 2010 г. в 16 часов на заседании диссертационного совета Д003.061.02 при Учреждении Российской академии наук Институте вычислительной математики и математической геофизики Сибирского отделения РАН, по адресу: 630090, г.Новосибирск, проспект Академика Лаврентьева, 6.

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

Автореферат разослан « 9 » ноября 2010 г. Ученый секретарь диссертационного совета,

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

профессор

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

профессор

Воеводин Анатолий Федорович кандидат физико-математических наук, старший научный сотрудник Бибердорф Элит Артльдовна Ведущая организация: Учреждение Российской академии наук

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

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

Сорокин С. Б.

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

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

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

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

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

3

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

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

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

Для достижения указанной цели были сформулированы н решены следующие задачи:

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

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

• Исследование эффективности алгоритма параллельной прогонки в различных приложениях

а) решение задачи Дирихле для уравнения Пуассона методом разделения переменных и методом переменных направлений;

4

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

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

Научная новизна заключается в том, что

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

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

• предложена параллельная реализация численно-аналитического метода для решения уравнения акустики и динамической задачи теории упругости;

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

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

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

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

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

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

На защиту выносятся следующие основные результаты и положения:

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

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

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

6

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

Апробация работы. По мере выполнения работы были сделаны доклады на следующих конференциях и семинарах: Международная конференция Parallel Computing Technologies, РаСТ 2007 г.; конкурс молодых учёных Института Ядерной Физики им. Будкера СО РАН, Новосибирск. 2008 г. и 2010 г.; конференция молодых учёных ИВМнМГ СО РАН Новосибирск, 2004 г. и 2010 г.; семинары математическое и архитектурное обеспечение параллельных вычислепий(3 доклада), ИВМиМГ СО РАН; Научный семинар отдела математических задач геофизики, ИВМиМГ СО РАН(2 доклада); Плазменный семнпар ИЯФ им. Г.И. Будкера СО РАН; 8-ая международная конференция но открытым системам для удержания плазмы (OS-2010, 5-9 июля, Новосибирск, Россия); семинар "Проблемы математического н численного моделирования" Института вычислительного моделирования СО РАН.

Публикации. Материалы диссертации опубликованы в 7 печатных работах, из них 6 статей в рецензируемых журналах, включенных в список ВАК, 1 статья в сборниках трудов конференций.

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

Диссертационная работа выполнялась в соответствии с планами Института вычислительной математики и математической геофизики, поддерживалась интеграционным проектом СО РАН No. 26, программами Рособразо-

т (

вания "Развитие научного потенциала ВШ" (проекты РНП 2.1.1/3983, РНП 2.2.1.1/3653), грантами РФФИ 09-02-00594, Фондом содействия отечественной науке.

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

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

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

Вторая глава посвящена разработке нового параллельного алгоритма (алгоритм дихотомии) для решения серии СЛАУ с одной н той же трехдиаго-нальной матрицей и различными правыми частями: ЛХ„ = Г„, п = 1,2,.... Здесь А-трехдиатональная матрица порядка т, обладающая свойством диагонального преобладания.

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

пе алгоритма дихотомии вычисляется решение для каждой правой части. Для этого на каждом уровне процесса дихотомии трехдиагональная система уравнений, полученная на предыдущем шаге, путем вычисления first, last-компонент из вектора решения (рис. 1), разделяется натри независимых подсистемы меньших размерностей. Далее процесс разделения применяется к двум из трех независимых подсистем (рис. 2). В итоге, через flog2(p)l шагов, где рчисло процессоров, исходная система уравнений будет разделена на р независимых подсистем, каждая из которых может быть решена посредством любого варианта метода прогонки.

Х=(о

«и — Ц ~г им Т

• 1.....I® О ■•• о • © о - О • i • О - О •! ..... !• О - О О )

last(UM) first(Uj) last(UJ first(UM)

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

Расчет first.last - элементов из вектора решения производится в соответствии с доказанной в разделе 2.2.3 основной теоремой параллельной прогонки. Справедливость этой теоремы следует из принципа суперпозиции, согласно которому общее решение линейной неоднородной задачи есть сумма общего решения однородной задачи и частного решения неоднородной зада-

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

вычислительной погрешности процесса дихотомии. В разделе 2.2.5 показа-

9

Шаг 2

процессоры 1:(И)

-i-

процессор I

процессоры fi+lj:p

: М

(и-|,1ф.....ииК

Г Т

N N PW

t IN* '

X г*;-, L

ц / <Ui+1,Uij.2,...,Up)

f'V'

4

N

Рис. 2. Разделение трехдиагональной СЛАУ на независимые подсистемы.

но, что по числу арифметических операций и количеству коммуникационных взаимодействий алгоритм дихотомии практически эквивалентен методу циклической редукции. В силу того, что расчет first, tasi-компонент сводится к вычислению суммы ряда, все межпроцессорные обмены могут быть осуществлены через последовательность вызовов коллективной операции All-to-One-Reduce(+). Учет таких свойств как ассоциативность и коммутативность операции сложения позволяет уменьшить время коммуникационных взаимодействий за счет их оптимизации, тогда как организация обменов через многократный вызов неблокирующей функции All-to-One-Reduce(+) позволяет сократить время синхронизации процессорных элементов. Таким образом, структура алгоритма дихотомии предоставляет широкие возможности для минимизации как времени передачи данных, так и времени синхронизации процессоров. В разделах 2.3-2.4 на примере параллельной реализации метода переменных направлений и метода разделения переменных для обращения оператора Лапласа исследована зависимость величины коэффициента ускорения от числа процессоров (рис. 3).

Цит. Ргосе.,

а) Метод переменных направлений. б) Метод разделения переменных.

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

В третьей главе в разделе 3.1 предложена и исследована параллельная реализация алгоритма дихотомии на основе интерфейса передачи сообще-ний(МР1). В разделе 3.2 рассмотрена модификация алгоритма дихотомии для решения СЛАУ с трехдиагональными теплицевыми матрицами. Наличие подготовительного этапа с затратами 0{т) арифметических действий не позволяет эффективно использовать алгоритм дихотомии для решения только одной системы уравнений. Однако для теплицевых матриц можно предложить экономичную подготовительную процедуру с числом арифметических действий порядка 0(m/p + log2p), гдер -число процессоров. Таким образом, предложенная модификация подготовительного этапа алгоритма дихотомии позволяет эффективно решать не только серию, но и одну СЛАУ с теплице-вой трехдиагональной матрицей.

В разделе 3.3 приведены результаты численных экспериментов по реализации алгоритма дихотомии для решения СЛАУ с трехдиагональными теплицевыми матрицами.

В четвертой главе исследуется вопрос применимости алгоритма дихо-

томии в рамках численно-аналитического метода для решения задач сейсмической разведки. Для этого рассматривается проблема моделирования акустических и упругих волн от точечного источника в неоднородной среде в г, г-геометрии. В качестве метода решения выбран численно-аналитический алгоритм на основе применения интегрального преобразования Лагерра по времени. Выбор преобразования Лагерра обусловлен тем, что алгоритм дихотомии разработан для решения СЛАУ с одной и той же трехдиагональ-ной матрицей и различными правыми частями. Известно, что преобразование Лагерра, в отличие от Фурье, позволяет после аппроксимации пространственных производных получить серию СЛАУ с одной н той же матрицей и различными правыми частями Аип = /„ + ^21=1 а«.»»и»> 11 = 2,... .

Разностные уравнения для моделирования акустических волновых полей предлагается решать методом сопряженных градиентов, а для упругих методом СМГ1Е8(А'). В качестве иредобуславливающего оператора выбран оператор Лапласа, для обращения которого используется метод разделения переменных, включающий алгоритм дихотомии и процедуру быстрого Фурье-преобразования.

В разделе 4.3 в рамках сравнения численных и аналитических решений показано, что моделирование волновых процессов для длительных моментов времени требует использования сеток с высокой разрешающей способность. Продемонстрировано, что предлагаемый параллельный алгоритм позволяет проводить не только модельные расчеты, но и решать реальные прикладные геофизические задачи. При этом может быть эффективно использован как суперкомпьютер с относительно небольшим числом процессоров 04 4- 256, так и многопроцессорные системы, объединяющие тысячи вычислительных элементов 1024 -г 8192.

В пятой главе рассмотрена реализация алгоритма дихотомии в рамках метода "частиц в ячейках" (ТАВ-код) для решения задачи о релаксации

электронного пучка в плазме в двумерной постановке.

Известно, что при вычислении сеточных плотностей заряда и тока в рамках метода "частиц в ячейках" необходимо удовлетворять разностному аналогу уравнения непрерывности/' + ' +(1пг/^'"+1/2 = 0. в противном случае появляются фиктивные заряды, в том числе и магнитные: (НуВ ф 0. с1К'Е ф Аир. Существуют несколько подходов к решению этой проблемы. Первый подход состоит в согласованном вычислении вкладов частиц в сеточные функции тока и плотности заряда. В другом подходе вычисления плотности тока и заряда по распределению частиц проводятся по несогласованным формулам, а затем для коррекции вводится поправка к электромагнитному нолю: Е = Ё — А(р = (НуЁ - 4тгр. Реализация процедуры решения уравнения Пуассона на многопроцессорной вычислительной системе представляет нетривиальную задачу, поэтому второй подход практически не используется при реализации метода "частиц в ячейках" на суперкомпьютере. Однако в работе показано, что использование алгоритма дихотомии в контексте процедуры обращения оператора Лапласа позволяет достичь ускорения близкого к линейному. Таким образом, в ТАВ-коде эффективно реализованы оба способа согласованного вычисления плотности тока и заряда: первый метод следует использовать при расчетах, когда число частиц в ячейке порядка 10 - 40, тогда как второй метод следует применять в случае, если число частиц значительно превышает число ячеек.

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

В заключении дан обзор основных результатов, полученных в днссер-

тацнонной работе.

Основные результаты

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

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

3. На основе алгоритма дихотомии предложена высокопроизводительная параллельная реализация метода разделения переменных и метода переменных направлений для обращения оператора Лапласа.

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

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

Основные результаты диссертации изложены в следующих публикациях:

1. Terekhov Andrew. Parallel dichotomy algorithm for solving tridiagonal system of linear equations with multiple right-hand sides. // Parallel Comput. 2010. Vol. 36. N. 8. pp. 423-438.

2. Терехов A.B., Тимофеев И.В., Лотов K.B. Двумерная численная модель плазмы для изучения процессов пучково-плазменного взаимодействия. // Вестник НГУ.Серия: Физика. 2010. Т. 5. №. 2. С. 85-97.

3. Лотов К.В, Терехов А.В., Тимофеев И.В. О насыщении двухпотоковой неустойчивости электронного пучка в плазме. //Физика Плазмы, 2009, Т. 9. №. 6. С. 567-574

4. Timofeev I.V., Lotov K.V., Terekhov A.V. Direct computation of the growth rate for the instability of a warm relativistic electron beam in a cold magnetized plasma // Phys. Plasmas. 2009. Vol. 16, pp. 063101-063101-5.

5. Вшивков B.A.,Терехов A.B. О самодействии в методе частиц в ячейках // Вычислительные методы и программирование. 2008. Т. 9. С. 48-57.

6. A.V. Terekhov, A. Mesgouez, and G. Lefeuve-Mesgouez. Transient mechanical wave propagation in semi-infinite porous media using a finite element approach with Domain Decomposition Technology. // In Proc. of the 9-th Int. conference on Parallel Computing Technologies (PaCT-2007), Pereslavl-Zalessky, Russia, September 3-7,2007, LNCS Vol. 4671, Springer Berlin/Heidelberg, pp. 174-183.

7. Timofeev I.V. and Terekhov A.V. Simulations of turbulent plasma heating by powerful electron beams //Phys. Plasmas 2010, Vol. 17, pp.083111, doi:10.1063/1.3474952.

Отпечатано в типографии Новосибирского Государственного технического университета 630092, г.Новосибирск, пр. К. Маркса, 20, Тел./факс (383) 346-08-57 Формат 60 х 84/16. Объем 1,0 п.л. Тираж 100 экз. Заказ 285. Подписано в печать 08.11.2010 г.

Введение

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

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

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

2.2. Алгоритм дихотомии

2.2.1. Базовый алгоритм

2.2.2. Вычисление произвольной компоненты из вектора решения.

2.2.3. Основная теорема параллельной прогонки.

2.2.4. Дихотомия системы линейных алгебраических уравнений

2.2.5. Вычислительные и коммуникационные затраты

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

2.3.1. Метод разделения переменных

2.3.2. Метод переменных направлений.

2.4. Результаты численных экспериментов.

Глава 3. Реализация алгоритма дихотомии на мультикомпьютере.

3.1. Основные формулы.

3.1.1. Вычисление first, last компонент.

3.1.2. MPI - реализация алгоритма дихотомии.

3.1.3. Оптимизация межпроцессорных взаимодействий

3.2. Процесс дихотомии для теп лицевых трехди атональных матриц

3.2.1. Оптимизация подготовительных вычислений

3.2.2. Экономичная подготовительная процедура алгоритма дихотомии для решения уравнения Пуассона

3.3. Результаты численных экспериментов.

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

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

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

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

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

Для достижения указанной цели были сформулированы и решены следующие задачи:

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

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

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

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

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

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

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

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

На защиту выносятся следующие основные результаты и положения:

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

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

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

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

Апробация работы. По мере выполнения работы были сделаны доклады на следующих конференциях и семинарах: Международная конференция Parallel Computing Technologies, РаСТ 2007 г.; конкурс молодых учёных Института Ядерной Физики им. Будкера СО РАН, Новосибирск, 2008 г. и 2010 г.; конференция молодых учёных ИВМиМГ СО РАН Новосибирск, 2004 г. и 2010 г.; семинары математическое и архи-1 тектурное обеспечение параллельных вычислений(3 доклада), ИВМиМГ СО РАН; Научный семинар отдела математических задач геофизики, ИВМиМГ СО РАН(2 доклада); Плазменный семинар ИЯФ им. Г.И. Будкера СО РАН; 8-ая международная конференция по открытым системам для удержания плазмы (OS-2010, 5-9 июля, Новосибирск, Россия); семинар "Проблемы математического и численного моделирования" Института вычислительного моделирования СО РАН.

Публикации. Материалы диссертации опубликованы в 7 печатных работах, из них 6 статей в рецензируемых журналах, включенных в список ВАК, 1 статья в сборниках трудов конференций.

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

Диссертационная работа выполнялась в соответствии с планами Инстатута вычислительной математики и математической геофизики, поддерживалась интеграционным проектом СО РАН N0. 26, программами Рособразования "Развитие научного потенциала ВШ" (проекты РНП 2.1.1/3983, РНП 2.2.1.1/3653), грантами РФФИ 09-02-00594, Фондом содействия отечественной науке.

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

Выводы по главе 5

Разработан новый параллельный Р1С-код для моделирования процессов пучково-плазменного взаимодействия. Как показали численные эксперименты на суперкомпьютере Межведомственного Суперкопьютер-ного Центра РАН 11 МВС-ЮОк использование в численной модели Алгоритма Дихотомии позволяет значительно ускорить трудоемкую процедуру решения уравнения Пуассона, используемую в Р1С—методе, и создает условия для повышения скорости и точности Р1С-расчетов за счет возможности использования больших вычислительных ресурсов.

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

Заключение

В диссертационной работе получены следующие результаты.

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

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

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

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

1. Самарский A.A. Теория разностных схемы. М.: Наука, 1977. С. 656.

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

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

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

5. Ильин В.П. Методы конечных разностей и конечных объемов для эллиптических уравнений. Новосибирск: Изд. ИВМиМГ, 2001. С. 318.

6. Яненко H.H. Метод дробных шагов решения задач математической физики. Из-во "Наука" , Сибирское отделение, 1967. С. 197.

7. Марчук Г.И. Методы вычислительной математики. М.:Наука, 1977. С. 456.

8. Марчук Г.И., Лебедев В.И. Численные методы в теории переноса нейтронов. М.: Атомиздат, 1971. С. 496.

9. Федоренко Р.П. Введение в вычислительную физику. М.: изд-во Моск. физ.-техн. ин-та, 1994. С. 528.

10. Стечкин С.Б., Субботин Ю.Н. Сплайны в вычислительной математике. М.:Наука, 1976. С. 248.

11. Hannan E.J. Time series analysis. Methuen, London, 1960. P. 152.

12. Марчук Г.И. Методы расщепления. М.:Наука, 1988. С. 263.

13. Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.:Наука, 1985. С. 208.

14. Коновалов А.Н. Введение в вычислительные методы линейной алгебры. Новосибирск, Наука, 1993. С. 159.

15. Годунов С.К. О численном решении краевых задач для систем линейных обыкновенных дифференциальных уравнений // Успехи мат. наук. 1961. Т. 3. С. 171-174.

16. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. БХВ-Петербург, 2004. С. 608.

17. Корнеев В.Д., Малышкин В.Э. Параллельное программирование мультикомпьютеров. Учебники НГТУ. НГТУ, 2006. С. 301.

18. Головашкин Д.Л. Параллельные алгоритмы решения сеточных уравнений трехдиагонального вида, основанные на методе встречных прогонок // Матем. моделирование. 2005. Т. 17. С. 118-128.

19. Логанова Л.В. Параллельный алгоритм метода циклических встречных прогонок для двумерной области // Вестник Самарского государственного аэрокосмического университета имени академика С.П. Королева. 2008. № 2. С. 164-174.

20. Ильин В.П., Свешников В.М., Литвиненко С.А. Параллельная реализация трехмерного аналога метода Пнсмана-Речфорда // Автометрия. 2003. Т. 39. С. 97-108.

21. Вшивков В.А., Тарнавский Г.А., Неупокоев Е.В. Параллелизацияалгоритмов прогонки: многоцелевые вычислительные эксперименты // Автометрия. 2002. Т. 38. С. 74-86.

22. Тарнавский Г.А., Шпак С.И. Схема распараллеливания операции решения систем алгебраических уравнений методом многомерной скалярной прогонки // Вычислительные методы и программирование. 2000. Т. 1. С. 19-27.

23. Povitsky Alex. Parallel ADI solver based on processor scheduling // Appl. Math. Comput. 2002. Vol. 133, по. 1. Pp. 43-81.

24. Qin Jiangning, Nguyen Duc T. A tridiagonal solver for massively parallel computéis // Adv. Eng. Softw. 1998. Vol. 29, no. 3-6. Pp. 395-397.

25. Яненко H.H., Коновалов A.H., Бугров A.H., Шустов Г.В. Об организации параллельных вычислений и "распараллеливании "прогонки // Численные методы механики сплошной среды. 1978. Т. 9, № 7. С. 139-146.

26. Воеводин А.Ф., Мурзин Ф.А., Пономарев М.Ю. Оптимизирующая трансляция и конструкция программ // Под ред. . Касьянов. Институт систем информатики им. А.П. Ершова, 1997. С. 123-133.

27. Mattor Nathan, Williams Timothy J., Hewett Dennis W. Algorithm for solving tridiagonal matrix problems in parallel // Parallel Comput. 1995. Vol. 21, no. 11. Pp. 1769-1782.

28. Бугров А.Н, Коновалов А.Н. Об устойчивости алгоритма распараллеливания прогонки // Численные методы механики сплошной среды. 1979. Т. 10. С. 139-146.

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

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

31. López Juan, Zapata Emilio L. Unified Architecture for Divide and Conquer Based Tridiagonal System Solvers // IEEE Trans. Comput. 1994. Vol. 43, no. 12. Pp. 1413-1425.

32. Витковский В.Э., Федорук М.П. Вычислительная производительность параллельного алгоритма прогонки на кластерных суперкомпьютерах с распределенной памятью // Вычислительные методы и программирование. 2008. Т. 9. С. 305-310.

33. Agüí Juan С., Jiménez Javier. A binary tree implementation of a parallel distributed tridiagonal solver // Parallel Comput. 1995. Vol. 21, no. 2. Pp. 233-241.

34. Wang H. H. A Parallel Method for Tridiagonal Equations // ACM Trans. Math. Softw. 1981. Vol. 7, no. 2. Pp. 170-183.

35. Hockney R.W., Jesshope C.R. Parallel Computers Two: Architecture, Programming and Algorithms. Bristol, UK: IOP Publishing Ltd., 1988. P. 642.

36. Lin H. X. A unifying graph model for designing parallel algorithms for tridiagonal systems // Parallel Comput. 2001. Vol. 27, no. 7. Pp. 925-939.

37. Heller D. Some aspects of the cyclic reduction algorithm for block tridiagonal linear systems // SIAM J. Numer. Anal. 1978. Vol. 13, no. 4. P. 484-496.

38. Lambiotte Jr. J.J., Voigt R.G. The solution of tridiagonal linear systems on the CDC STAR100 computer // ACM Trans. Math. Software. 1975. Vol. 1. Pp. 308-329.

39. Wu Jung-Gen, Yan Wen-Ming, Chung Kuo-Liang. A Parallel Solver for Circulant Toeplitz Tridiagonal Systems on Hypercubes // J. Sci. Comput. 1997. Vol. 12, no. 4. Pp. 409-431.

40. Sun Xian-He, Zhang Hong, Ni Lionel M. Efficient Tridiagonal Solvers on Multicomputers // IEEE Trans. Comput. 1992. Vol. 41, no. 3. Pp. 286-296.

41. Sun Xian-He, Zhang Wu. A Parallel Two-Level Hybrid Method for Tridiagonal Systems and Its Application to Fast Poisson Solvers // IEEE Trans. Parallel Distrib. Syst. 2004. Vol. 15, no. 2. Pp. 97-106.

42. Sun Xian-He. A scalable parallel algorithm for periodic symmetric Toeplitz tridiagonal systems. Commack, NY, USA: Nova Science Publishers, Inc., 2001. Pp. 149-156.

43. Тыртышников E.E. Теплицевы матрицы, некоторые их аналоги и приложения. М., 1989. С. 164.

44. Garey L.E., Shaw R.E. A parallel algorithm for solving Toeplitz linear systems // Appl. Math. Comput. 1999. Vol. 100, no. 2-3. Pp. 241-247.

45. Гаитмахер Ф.Р. Теория матриц. Изд.5. М.:Наука, 2010.

46. Паасоиеи В.И. Параллельный алгоритм для компактных схем // Вычислительные технологии. 2005. Т. 10, № 5. С. 81-89.

47. Гельфонд А.О. Исчисление конечных и разностей. М. Гос. Изд. Физико-математической литературы, 1959. С. 400.

48. Ильин В.П. Прямой анализ устойчивости метода прогонки // Актуальные проблемы вычислительной математики и математического моделирования. 1985. С. 189-201.

49. Gibbs W.R. A parallel/recursive algorithm //J. Comput. Phys. 2004. Vol. 201, no. 2. Pp. 573-585.

50. Amdahl G. Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities // AFIPS Conference Proceedings. Vol. 30. 1967. Pp. 483-485.

51. Rabenseifner R. A new optimized mpi reduce algorithm, High-Performance Computing-Center, University of Stuttgart. http://www.hlrs.de/mpi/myreduce.html. URL: http: //www.hlrs. de/mpi/myreduce.html.

52. Hockney R.W. A Fast Direct Solution of Poisson's Equation Using Fourier Analysis // J. ACM. 1965. Vol. 12, no. 1. Pp. 95-113.

53. Washspress E. L. Optimal Alternating-Direction-Implicate Iteration Parameters //J. Soc. Indust. Appl. Math. 1962. Vol. 10. Pp. 339-350.

54. Ильин В.П. Параллельные неявные методы переменных направлений // Журнал вычислительной математики и математической физики. 1997. Т. 37, № 8. С. 899-907.

55. Wakatani Akiyoshi. A parallel and scalable algorithm for ADI method with pre-propagation and message vectorization // Parallel Comput. 2004. Vol. 30, no. 12. Pp. 1345-1359.

56. Vajtersic M. Algorithms for Elliptic Problems, Efficient Sequential and Parallel Solvers. Springer, 1993. P. 292.

57. Grooss J. Parallel elliptic PDE solver. Informatics and Mathematical Modelling. Technical University of Denmark, DTU„ 2001.

58. Shonkwiler Ronald W., Lefton Lew. An Introduction to Parallel and Vector Scientific Computation (Cambridge Texts in Applied Mathematics). New York, NY, USA: Cambridge University Press, 2006. P. 288.

59. Terekhov Andrew. Parallel dichotomy algorithm for solving tridiag-onal system of linear equations with multiple right-hand sides. // Parallel Comput. 2010. Vol. 36, no. 8. Pp. 423-438. doi:10.1016/j.parco.2010.02.005.

60. Parhami Behrooz. Introduction to Parallel Processing: Algorithms and Architectures. Norwell, MA, USA: Kluwer Academic Publishers, 1999. P. 564.

61. Sourcebook of parallel computing, Ed. by J. Dongarra, I. Foster, G. Fox et al. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2003.

62. Heroux Michael A., Raghavan Padma, Simon Horst D. Parallel Processing for Scientific Computing (Software, Environments and Tools).

63. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2006. P. 397.

64. Ольшанский M.A. Лекции и упражнения по многосеточным методам. М.: Физматлит, 2005. С. 176.

65. Douglas Craig С., Haase Gundolf, Langer Ulrich. A Tutorial on Elliptic PDE Solvers and Their Parallelization. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2003. P. 135.

66. Хокни P., Иствуд Дж. Числениое моделирование методом частиц в ячейках. Москва "Мир 1987. С. 640.

67. Canuto С., Hussaini M.Y., Quarteroni A., Zang Т.A. Spectral Methods. Fundamentals in Single Domains. Scientific Computation. Springer Berlin Heidelberg, 2006. P. 563.

68. Carl de Boor. A Practical Guide to Splines. Springer-Verlag, 1978. Vol. 27 of Applied Mathematical Sciences. P. 372.

69. McNally Jeffrey M., Garey L. E., Shaw R. E. A communication-less parallel algorithm for tridiagonal Toeplitz systems //J. Comput. Appl. Math. 2008. Vol. 212, no. 2. Pp. 260-271.

70. Суетин П.К. Классические ортогональные многочлены. Главная редакция физико-математической литературы изд-ва Наука, 1979. С. 416.

71. Bhat Prashanth В., Raghavendra C.S., Prasanna Viktor К. Efficient collective communication in distributed heterogeneous systems //J. Parallel Distrib. Comput. 2003. Vol. 63, no. 3. Pp. 251-263.

72. Faraj Ahmad, Yuan Xin. Automatic generation and tuning of MPI collective communication routines // ICS '05: Proceedings of the 19th annual international conference on Supercomputing. New York, NY, USA: ACM, 2005. Pp. 393-402.

73. Vadhiyar Sathish S., Fagg Graham E., Dongarra Jack. Automatically tuned collective communications // Supercomputing '00: Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM). Washington, DC, USA: IEEE Computer Society, 2000. P. 3.

74. Sistare Steve, vandeVaart Rolf, Loh Eugene. Optimization of MPI collectives on clusters of large-scale SMP's // Supercomputing '99: Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM). New York, NY, USA: ACM, 1999. P. 23.

75. Демидов С.П. Теория упругости. M.: Высшая школа, 1979. С. 389.

76. Кауфманн А.А., Левшнн АЛ. Введение в теорию геофизических методов. М.:Недра, 2006. С. 663.

77. Уайт Дж. Возбуждение и распространение сейсмических волн. М.:Недра, 1986. С. 261.

78. Mikhailenko В. G. Spectral Laguerre method for the approximate solution of time dependent problems // Applied Mathematics Letters. 1999. Vol. 12. Pp. 105-110.

79. Flyer Natasha, Swarztrauber Paul N. The Convergence of Spectral and Finite Difference Methods for Initial-Boundary Value Problems // SI AM J. Sci. Comput. 2002. Vol. 23, no. 5. Pp. 1731-1751.

80. Марчук Г.И., Агошков В.И. Введение в проекционно-сеточные методы. М.:Наука, 1981. С. 416.

81. Ihlenburg F. Finite element analysis of acoustic scattering. Springer, 1998. P. 224.

82. Kwan Yuen-Yick, Shen Jie. An efficient direct parallel spectral-element solver for separable elliptic problems //J. Comput. Phys. 2007. Vol. 225, no. 2. Pp. 1721-1735.

83. Paprzycki M., Petrova S. I., Sanchez J. Implementing parallel elliptic solver on a Beowulf cluster // Electron. J. Differ. Equ. 1999. Pp. 75-85.

84. Tufo H. M., Fischer P. F. Fast Parallel Direct Solvers for Coarse Grid Problems // J. of Parallel and Distributed Computing. 2001. Vol. 61, no. 2. Pp. 151-177.

85. Johnsson S. Lennart. Solving tridiagonal systems on ensemble architectures // SIAM J. Sei. Stat. Comput. 1987. Vol. 8, no. 3. Pp. 354-392.

86. Bernhardt P. A., Brackbilla J. U. Solution of Elliptic Equations Using Fast Poisson Solvers // Journal of Computational Physics. 1984. Vol. 53. Pp. 382-394.

87. Conçus P., Golub H.G. Use of Fast direct methods for the Efficient Numerical Solution of Non-Separable Elliptic Equations // SIAM J. Numer. Anal. 1973. Vol. 10. Pp. 1103-1120.

88. Braverman E., Epstein В., Boris et al. A fast spectral subtractional solver for elliptic equations //J. Sei. Comput. 2004. Vol. 21. Pp. 91-128.

89. Chang S. Solution of elliptic PDEs by fast Poisson solvers using a local relaxation factor // J. Comput. Phys. 1986. Vol. 67, no. 1. Pp. 91-123.127

90. Федоренко Р.П. Методы решения разностных эллиптических уравнений // Успехи мат. наук. 1973. Т. 28, № 5. С. 121-182.

91. Peaceman D. W., Rachford Н. Н. The numerical solution of parabolic , and elliptic differential equations // SIAM J. 1955. Vol. 3. Pp. 28-41.

92. Ильин В.П., Карпов В.В., Масленников A.M. Численные методы решения задач строительной механики. Справочное пособие. Минск: Высш. шк, 1990. С. 349.

93. Boresi Arthur P., Chong Ken P., Saigal Sunil. Approximate Solution Methods in Engineering Mechanics, 2nd Edition. John Wiley & Son, 2003. P. 280.

94. Encyclopedia of Computational Mechanics, Vol. 2 Solids and Structures, Ed. by S. Erwin, R. de Borst, H. Thomas J. R. Wiley, 2004.

95. Ильин В.П. Методы неполной факторизации для решения алгебраических систем. М.:Физмалит, 1995. С. 288.

96. Калиткин Н.Н. Численные методы. М.:Наука, 1978. С. 508.

97. Schumann U. Fast Fourier transforms for direct solution of Poisson's equation with staggered boundary conditions //J. Comput. Phys. 1988. Vol. 75. Pp. 123-137.

98. FFTW 3.2.2, (http://fftw.org/).

99. Dupros F., et al. High-performance finite-element simulations of seismic wave propagation in threedimensional nonlinear inelastic geological media // Parallel Comput. 2010,doi:10.1016/j.parco.2009.12.011.

100. Dongarra Jack J., Duff Lain S., Sorensen Danny C., Vorst Henk A. Vander. Numerical Linear Algebra for High Performance Computers. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 1998. P. 342.

101. Kim Seongjai, Lim Hyeona. High-order schemes for acoustic waveform simulation // Appl. Numer. Math. 2007. Vol. 57, no. 4. Pp. 402-414.

102. Михайленко Б.Г. Моделирование распрастранения сейсмических волн в неоднородных средах // Сиб. журн. вычисл. матем. 2003. Т. 6. С. 415-429.

103. Коновалов А.Н. Численные методы в динамических задачах теории упругости // Сибирский математический журнал. 1997. Т. 38. С. 551-568.

104. Михайленко Б.Г. Численное решение задачи Лэмба для неоднородного полупространства // Математические проблемы геофизики, Новосибирск , ВЦ СО АН СССР. 1973. Т. 4. С. 273-297.

105. Lombard Bruno, Piraux Joël. Numerical treatment of two-dimensional interfaces for acoustic and elastic waves //J. Comput. Phys. 2004. Vol. 195, no. 1. Pp. 90-116.

106. Ito Kazufumi, Qiao Zhonghua, Toivanen Jari. A domain decomposition solver for acoustic scattering by elastic objects in layered media //J. Comput. Phys. 2008. Vol. 227, no. 19. Pp. 8685-8698.

107. Lirkov Ivan. MPI solver for 3D elasticity problems // Math. Comput. Simul. 2003. Vol. 61, no. 3-6. Pp. 509-516.

108. Thomson W.T. Transmission of classic waves through a stratified solid material // J. Appl. Phys. 1950. Vol. 21, no. 1. Pp. 89-93.

109. Haskell N.A. The dispersion of surface waves on multilayered media // Bull. Seismol. Soc. Amer. 1953. Vol. 43, no. 1. Pp. 17-34.

110. Knopoff L.A. Matrix method for elastic wave problems // Bull. Seismol. Soc. Amer. 1964. Vol. 54. Pp. 431-438.

111. Kennett B.L.N. Theoretical reflection seismograms for elastic media // Geophysical Prospecting. 1979. Vol. 27, no. 2. Pp. 301-321.

112. Dunkin I.W. Computation of model solutions in layered elastic media at high frequencies // Bull. Seismol. Soc. Amer. 1965. Vol. 55, no. 2. Pp. 355-358.

113. Fatyanov A.G. Semi-analitical method of the solution of direct dynamic problems in layered mediums // Dokl. Akad. Nauk SSSR. 1990. Vol. 310.

114. Fatyanov A.G. Mathematical Simulation of Wave Fields in Media with Arbitrary Curvilinear Boundaries // Applied Mathematics Letters. 2005. Vol. 8, no. 11. Pp. 1216-1223.

115. Martin Gary S., Wiley Robert, Marfurt Kurt J. Marmousi2: An elastic upgrade for Marmousi // The Leading Edge. 2006. Vol. 25, no. 2. Pp. 156-166.

116. Михайловский А.Б. Теория плазменных неустойчивостей. М.: Атом-издат, 1977. Т. 1. С. 312.

117. Брейзман Б.Н. Коллективное взаимодействие релятивистских электронных пучков с плазмой., Под ред. . Кадомцев. Вопросы теории плазмы № 15. М.: Энргоатомиздат, 1986.

118. Timofeev I.V., Lotov K.V. Relaxation of a relativistic electron beam in plasma in the trapping regime // Phys. Plasmas. 2006. Vol. 13, no. 062312.

119. Gremillet L., Benisti D., Lefebvre L., Bret A. Linear and nonlinear development of oblique beam-plasma instabilities in the relativistic kinetic regime // Phys. Plasmas. 2007. Vol. 14.

120. Umeda T. Generation of low-frequency electrostatic and electromagnetic waves as nonlinear consequences of beam-plasma interactions // Phys. Plasmas. 2008. Vol. 15, no. 064502.

121. Timofeev I.V., Lotov K.V., Terekhov A.V. Direct computation of the growth rate for the instability of a warm relativistic electron beam in a cold magnetized plasma // Phys. Plasmas. 2009. Vol. 16, no. 063101.

122. Tabak M., Hammer J., Glinsky M.E. Ignition and high gain with ultra-powerful lasers // Phys. Plasmas. 1994. Vol. 1, no. 1626.

123. Malkin V.M., Fish N.J. Collective Deceleration of Relativistic Electrons

124. Precisely in the Core of an Inertial-Fusion Target // Phys. Rev. Lett. 2002. Vol. 89, no. 125004.

125. Бэдсел Ч., Ленгдон А. Физика плазмы и численное моделирование. М.: Энергоатомиздат, 1989. С. 456.

126. Григорьев Ю.Н., Вшивков В.А., Федорук М.П. Численное моделирование методами частиц-в-ячейках. Новосибирск: СО РАН, 2004.

127. Березин Ю.А., Вшивков В.А. Метод частиц в динамике разреженной плазмы. Новосибирск: Наука. Сиб. отделение, 1980.

128. Терехов А.В, Лотов К.В., Тимофеев И.В. Двумерная численная модель для изучения процессов пучково-плазменного взаимодействия // Вестик Новосибирского государственного университета. Серия:Физика. 2010. Т. 5. С. 85-97.

129. Tirnofeev I. V., Terekhov А. V. Simulations of turbulent plasma heating by powerful electron beams // Physics of plasmas. 2010. Vol. 17. P. 083111.

130. Kraeva M.A., Malyshkin V.E. Assembly Technology for Parallel Realization of Numerical Models on MIMD-Multicomputers // In the Int. Journal on Future Generation Computer Systems. 2001. Vol. 17, no. 6. Pp. 755-765.

131. Malyshkin V. Assembling of Parallel Programs for Large Scale Numerical Modeling. Handbook of Research on Scalable Computing Technologies. IGI Global, 2010. Pp. 295-311.

132. Вшивков В.А., Вшивков К.В., Дудникова Г.И. Алгоритмы решения задачи взаимодействия лазерного импульса с плазмой // Вычислительные технологии. 2001. Т. 6, № 2. С. 47-63.

133. Koidan V.S., Arzhannikov A.V., Astrelin V.T., et al. Progress on the multimirror trap GOL-3 // Trans. Fusion Sci. and Techn. 2005. Vol. 47, no. 35.

134. Burdakov A., Arzhannikov A., Astrelin V. et al. Plasma heating and confinement in GOL-3 multi mirror trap // Trans. Fusion Sci. and Techn. 2007. Vol. 51, no. 106.

135. Аржанников А.В., Астрелин В.Т., Бурдаков и др., А.В. Исследование механизма быстрого нагрева ионов в многопробочной ловушке ГОЛ-3 // Физика Плазмы. 2005. Т. 31, № 506.

136. Вшивков В.А., Терехов А.В. О самодействии в методе частиц в ячейках // Вычислительные методы и программирование. 2008. Т. 9. С. 48-57.

137. Esirkepov T.Zh. Exact charge conservation for Particle-in-Cell simulation with an arbitary form-factor // Computer Physics Communications. 2001. Vol. 135. Pp. 144-153.

138. Taflove A., Hagness S.C. Computational Electrodynamics: The Finite-Difference Time-Domain Method. Norwood, MA: Artech House, 2005. P. 1038.

139. Boris J.P. Relativistic plasma simulation optimization of a hybrid code coordinates. Vol. 6. Washington: Procedings 4th International Conference on the Numerical Simulation of Plasmas, 1970.— September. Pp. 3-67.

140. Лотов К.В., Терехов А.В, Тимофеев И.В. О насыщении двухпотоко-вой неустойчивости электронного пучка в плазме // Физика. 2009. Т. 35, № 6. С. 567-574.

141. Лившиц Е.М., Питаевский Л.П. Физическая кинетика.- 2е изд. М.: ФИЗМАТЛИТ, 2002. С. 175.