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

• Терехов, Андрей Валерьевич
• кандидат физико-математических наук
• 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С-модели для изучения турбулентности, возбуждаемой мощным электронным пучком в плазме. Показано хорошее согласие результатов численных экспериментов с теорией как для одночастичного механизма возбуждения плазменных колебаний, так и для коллективной раскачки двухпотоковой неустойчивости.

Список литературы диссертационного исследования кандидат физико-математических наук Терехов, Андрей Валерьевич, 2010 год

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.