Н. Новгород: Изд-во Нижегородского госуниверситета им. Н.И.
Лобачевского, 2011. 124 c.
В пособии рассматриваются типовые численные алгоритмы из различных разделов вычислительной математики: методы решения систем линейных алгебраических уравнений (с плотными и разреженными матрицами), решение дифференциальных уравнений в частных производных, методы Монте-Карло. Для каждого рассматриваемого алгоритма приводится его математическое описание, излагается последовательная версия, рассматриваются способы возможного распараллеливания в системах с общей памятью. Проводится сравнение разработанных алгоритмов с известными высокопроизводительными реализациями (на примере Intel MKL)
Для студентов и магистрантов, обучающихся на факультетах физико-математического профиля. В настоящее время основной тенденцией развития вычислительной техники является параллельность: любой современный компьютер содержит несколько вычислительных ядер на центральном процессоре, и несколько десятков ядер – на графическом. Развитие техники определяет и развитие численных алгоритмов: все большее внимание уделяется параллельным численным методам, любой алгоритм сейчас рассматривается сквозь призму его возможного распараллеливания.
Целью данного пособия является изложение некоторых известных численных алгоритмов и рассмотрение круга вопросов, связанных с их распараллеливанием. Пособие построено следующим образом.
Первая часть посвящена рассмотрению прямых методов решения систем линейных алгебраических уравнений с матрицами как общего, так и специального вида: метод исключения Гаусса, разложение Холецкого, метод прогонки. Изложены классические варианты алгоритмов, показана их недостаточная эффективность при использовании современных вычислительных архитектур. Последовательно проводится идея блочной обработки данных.
Во второй части рассмотрены итерационные методы решения систем линейных уравнений: методы простой итерации и верхней релаксации, метод сопряженных градиентов. Рассмотрены способы их распараллеливания, приведены теоретические и экспериментальные оценки ускорения, достигаемого за счет введения паралеллизма.
Третья часть посвящена задачам разреженной алгебры. Дан краткий обзор структур хранения разреженных матриц, рассмотрены типовые проблемы, возникающие при реализации основных операций над разреженными матрицами. В качестве примера вычислительного алгоритма рассмотрено разложение Холецкого, показана проблема роста коэффициента заполнения матрицы при разложении, изложены алгоритмы переупорядочивания матрицы, снижающие заполнение результирующей матрицы.
Четвертая часть затрагивает вопросы параллельного решения дифференциальных уравнений в частных производных. Рассмотрены типовые уравнения в частных производных, для них построены разностные схемы, приведены последовательные и параллельные алгоритмы их решения.
Заключительная часть посвящена численным методам Монте-Карло. Здесь читатели могут познакомиться с проблемами, возникающими при использовании случайных чисел при решении задач методами Монте-Карло. Рассмотрены различные способы генерации случайных чисел, как последовательные, так и параллельные; обсуждаются вопросы безызбыточного распараллеливания метода.
В каждой главе приводятся результаты вычислительных экспериментов. Содержание
Введение.
Прямые методы решения СЛАУ.
Метод прогонки.
Метод встречной прогонки и его распараллеливание. Параллельный вариант метода прогонки. Результаты вычислительных экспериментов.
Метод исключения Гаусса.
Последовательный алгоритм. Параллельный алгоритм. Связь метода Гаусса и LU- разложения. Результаты вычислительных экспериментов. Блочное LU- разложение. Результаты вычислительных экспериментов.
Метод Холецкого.
Последовательный алгоритм. Организация параллельных вычислений. Результаты вычислительных экспериментов. Блочный алгоритм. Результаты вычислительных экспериментов.
Итерационные методы решения СЛАУ.
Метод простой итерации.
Последовательный алгоритм. Параллельный алгоритм.
Метод верхней релаксации.
Последовательный алгоритм. Организация параллельных вычислений. Результаты вычислительных экспериментов.
Метод сопряженных градиентов.
Последовательный алгоритм. Организация параллельных вычислений. Результаты вычислительных экспериментов.
Решение разреженных СЛАУ.
Хранение разреженной матрицы.
Операции над разреженными матрицами.
Умножение матрицы на вектор. Параллельный алгоритм.
Метод Холецкого для разреженных матриц.
Метод минимальной степени. Результаты экспериментов. Метод вложенных сечений.
Решение дифференциальных уравнений в частных производных.
Решение волнового уравнения.
Явная разностная схема. Организация параллельных вычислений. Результаты вычислительных экспериментов.
Решение задачи теплопроводности.
Явная разностная схема. Неявные разностные схемы. Организация параллельных вычислений. Результаты экспериментов.
Решение задачи Дирихле для уравнения Пуассона.
Построение разностной схемы. Применение метода верхней релаксации. Организация параллельных вычислений. Результаты вычислительных экспериментов.
Параллельные методы Монте-Карло.
Вычисление определенного интеграла.
Способы уменьшения дисперсии.
Генераторы псевдослучайных чисел.
Линейный конгруэнтный генератор. Генератор Фибоначчи с запаздываниями. Генератор MERSENNE TWISTER Генератор Соболя.
Подходы к распараллеливанию методов Монте-Карло.
Метод «Мастер-Рабочий». Метод с перешагиванием (LEAPFROG). Разделение последовательности. Параметризация.
Результаты вычислительных экспериментов.
Литература.
Использованные источники информации.
Дополнительная литература.
Информационные ресурсы сети Интернет.
В пособии рассматриваются типовые численные алгоритмы из различных разделов вычислительной математики: методы решения систем линейных алгебраических уравнений (с плотными и разреженными матрицами), решение дифференциальных уравнений в частных производных, методы Монте-Карло. Для каждого рассматриваемого алгоритма приводится его математическое описание, излагается последовательная версия, рассматриваются способы возможного распараллеливания в системах с общей памятью. Проводится сравнение разработанных алгоритмов с известными высокопроизводительными реализациями (на примере Intel MKL)
Для студентов и магистрантов, обучающихся на факультетах физико-математического профиля. В настоящее время основной тенденцией развития вычислительной техники является параллельность: любой современный компьютер содержит несколько вычислительных ядер на центральном процессоре, и несколько десятков ядер – на графическом. Развитие техники определяет и развитие численных алгоритмов: все большее внимание уделяется параллельным численным методам, любой алгоритм сейчас рассматривается сквозь призму его возможного распараллеливания.
Целью данного пособия является изложение некоторых известных численных алгоритмов и рассмотрение круга вопросов, связанных с их распараллеливанием. Пособие построено следующим образом.
Первая часть посвящена рассмотрению прямых методов решения систем линейных алгебраических уравнений с матрицами как общего, так и специального вида: метод исключения Гаусса, разложение Холецкого, метод прогонки. Изложены классические варианты алгоритмов, показана их недостаточная эффективность при использовании современных вычислительных архитектур. Последовательно проводится идея блочной обработки данных.
Во второй части рассмотрены итерационные методы решения систем линейных уравнений: методы простой итерации и верхней релаксации, метод сопряженных градиентов. Рассмотрены способы их распараллеливания, приведены теоретические и экспериментальные оценки ускорения, достигаемого за счет введения паралеллизма.
Третья часть посвящена задачам разреженной алгебры. Дан краткий обзор структур хранения разреженных матриц, рассмотрены типовые проблемы, возникающие при реализации основных операций над разреженными матрицами. В качестве примера вычислительного алгоритма рассмотрено разложение Холецкого, показана проблема роста коэффициента заполнения матрицы при разложении, изложены алгоритмы переупорядочивания матрицы, снижающие заполнение результирующей матрицы.
Четвертая часть затрагивает вопросы параллельного решения дифференциальных уравнений в частных производных. Рассмотрены типовые уравнения в частных производных, для них построены разностные схемы, приведены последовательные и параллельные алгоритмы их решения.
Заключительная часть посвящена численным методам Монте-Карло. Здесь читатели могут познакомиться с проблемами, возникающими при использовании случайных чисел при решении задач методами Монте-Карло. Рассмотрены различные способы генерации случайных чисел, как последовательные, так и параллельные; обсуждаются вопросы безызбыточного распараллеливания метода.
В каждой главе приводятся результаты вычислительных экспериментов. Содержание
Введение.
Прямые методы решения СЛАУ.
Метод прогонки.
Метод встречной прогонки и его распараллеливание. Параллельный вариант метода прогонки. Результаты вычислительных экспериментов.
Метод исключения Гаусса.
Последовательный алгоритм. Параллельный алгоритм. Связь метода Гаусса и LU- разложения. Результаты вычислительных экспериментов. Блочное LU- разложение. Результаты вычислительных экспериментов.
Метод Холецкого.
Последовательный алгоритм. Организация параллельных вычислений. Результаты вычислительных экспериментов. Блочный алгоритм. Результаты вычислительных экспериментов.
Итерационные методы решения СЛАУ.
Метод простой итерации.
Последовательный алгоритм. Параллельный алгоритм.
Метод верхней релаксации.
Последовательный алгоритм. Организация параллельных вычислений. Результаты вычислительных экспериментов.
Метод сопряженных градиентов.
Последовательный алгоритм. Организация параллельных вычислений. Результаты вычислительных экспериментов.
Решение разреженных СЛАУ.
Хранение разреженной матрицы.
Операции над разреженными матрицами.
Умножение матрицы на вектор. Параллельный алгоритм.
Метод Холецкого для разреженных матриц.
Метод минимальной степени. Результаты экспериментов. Метод вложенных сечений.
Решение дифференциальных уравнений в частных производных.
Решение волнового уравнения.
Явная разностная схема. Организация параллельных вычислений. Результаты вычислительных экспериментов.
Решение задачи теплопроводности.
Явная разностная схема. Неявные разностные схемы. Организация параллельных вычислений. Результаты экспериментов.
Решение задачи Дирихле для уравнения Пуассона.
Построение разностной схемы. Применение метода верхней релаксации. Организация параллельных вычислений. Результаты вычислительных экспериментов.
Параллельные методы Монте-Карло.
Вычисление определенного интеграла.
Способы уменьшения дисперсии.
Генераторы псевдослучайных чисел.
Линейный конгруэнтный генератор. Генератор Фибоначчи с запаздываниями. Генератор MERSENNE TWISTER Генератор Соболя.
Подходы к распараллеливанию методов Монте-Карло.
Метод «Мастер-Рабочий». Метод с перешагиванием (LEAPFROG). Разделение последовательности. Параметризация.
Результаты вычислительных экспериментов.
Литература.
Использованные источники информации.
Дополнительная литература.
Информационные ресурсы сети Интернет.