On Monte Carlo method in distributed memory systems
Abstract
Работа посвящена решению систем линейных алгебраических уравнений (СЛАУ) на компьютерах с распределенной памятью. Предполагается наличие M вычислительных узлов, каждый из которых имеет ограниченную быструю память, а обмен данными между узлами занимает значительное время.При условии, что элементы матрицы и вектора правой части невозможно разместить в полном объеме в памяти одного узла, возникает проблема эффективного использования оборудования в промежутках между обменами, т. е. возможности использования каждым из узлов доступных ему данных для уменьшения общей невязки. При общих предположениях относительно матрицы системы ответ на этот вопрос отрицателен, что подтверждает пример в приложении работы. Мы рассматриваем случай, когда система имеет достаточно большой порядок и целесообразно применять метод Монте-Карло. При этом матрица разделяется между вычислительными узлами на непересекающиеся блоки строк при одинаковом разбиении на блоки индексов строк и столбцов. Также рассматривается модификация метода простой итерации, основанная на этом разбиении, состоящая из двух вложенных итерационных процессов, так что только внешние итерации сопряжены с обменом сообщениями между узлами.Данный итерационный процесс естественным образом приводит к аналогичному процессу с использованием метода Монте-Карло, не требующему хранения полной копии матрицы системы на каждом вычислительном узле.В работе построены и исследованы оценки решения СЛАУ для рассматриваемого случая. При некоторых дополнительных условиях на матрицу системы доказаны достаточные условия сходимости. Библиогр. 8 назв.
Downloads
References
Downloads
Published
How to Cite
Issue
Section
License
Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.