О методе Монте-Карло в системах с распределенной памятью

Аннотация

Работа посвящена решению систем линейных алгебраических уравнений (СЛАУ) на компьютерах с распределенной памятью. Предполагается наличие M вычислительных узлов, каждый из которых имеет ограниченную быструю память, а обмен данными между узлами занимает значительное время.При условии, что элементы матрицы и вектора правой части невозможно разместить в полном объеме в памяти одного узла, возникает проблема эффективного использования оборудования в промежутках между обменами, т. е. возможности использования каждым из узлов доступных ему данных для уменьшения общей невязки. При общих предположениях относительно матрицы системы ответ на этот вопрос отрицателен, что подтверждает пример в приложении работы. Мы рассматриваем случай, когда система имеет достаточно большой порядок и целесообразно применять метод Монте-Карло. При этом матрица разделяется между вычислительными узлами на непересекающиеся блоки строк при одинаковом разбиении на блоки индексов строк и столбцов. Также рассматривается модификация метода простой итерации, основанная на этом разбиении, состоящая из двух вложенных итерационных процессов, так что только внешние итерации сопряжены с обменом сообщениями между узлами.Данный итерационный процесс естественным образом приводит к аналогичному процессу с использованием метода Монте-Карло, не требующему хранения полной копии матрицы системы на каждом вычислительном узле.В работе построены и исследованы оценки решения СЛАУ для рассматриваемого случая. При некоторых дополнительных условиях на матрицу системы доказаны достаточные условия сходимости. Библиогр. 8 назв.