On Monte Carlo method in distributed memory systems
Sergey M. Ermakov, Anatolii V. Trosinenko, JSC “Technologies for aviation” · Vestnik of Saint Petersburg University Mathematics Mechanics Astronomy · 2016
УДК 519.245Вестник СПбГУ.Сер. 1. Т. 3 (61).2016.Вып. 4 О МЕТОДЕ МОНТЕ-КАРЛО В СИСТЕМАХ С РАСПРЕДЕЛЕННОЙ ПАМЯТЬЮ * С. М. Ермаков 1 , А. В. Тросиненко 2 1 Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7-9 2 АО «Технологии для авиации», Российская Федерация, 199178, Санкт-Петербург, Малый пр.В. О., 54, корп.5, лит.П Работа посвящена решению систем линейных алгебраических уравнений (СЛАУ) на компьютерах с распределенной памятью.Предполагается наличие M вычислительных узлов, каждый из которых имеет ограниченную быструю память, а обмен данными между узлами занимает значительное время.При условии, что элементы матрицы и вектора правой части невозможно разместить в полном объеме в памяти одного узла, возникает проблема эффективного использования оборудования в промежутках между обменами, т. е. возможности использования каждым из узлов доступных ему данных для уменьшения общей невязки.При общих предположениях относительно матрицы системы ответ на этот вопрос отрицателен, что подтверждает пример в приложении работы.Мы рассматриваем случай, когда система имеет достаточно большой порядок и целесообразно применять метод Монте-Карло.При этом матрица разделяется между вычислительными узлами на непересекающиеся блоки строк при одинаковом разбиении на блоки индексов строк и столбцов.Также рассматривается модификация метода простой итерации, основанная на этом разбиении, состоящая из двух вложенных итерационных процессов, так что только внешние итерации сопряжены с обменом сообщениями между узлами.Данный итерационный процесс естественным образом приводит к аналогичному процессу с использованием метода Монте-Карло, не требующему хранения полной копии матрицы системы на каждом вычислительном узле.В работе построены и исследованы оценки решения СЛАУ для рассматриваемого случая.При некоторых дополнительных условиях на матрицу системы доказаны достаточные условия сходимости.Библиогр.8 назв.