On partial synchronization of iterative methods

Authors

  • Aleksey V. Dmitriev
  • Sergey M. Ermakov

Abstract

Темпы развития многопроцессорной вычислительной техники способствуют исследованию параллельных алгоритмов, среди которых немаловажную роль играют метод Монте-Карло и асинхронные итерации. Выгодной особенностью таких алгоритмов является отсутствие необходимости наличия глобального времени в многопроцессорной системе (отсутствие синхронизации) и эффективность загрузки имеющихся вычислительных ресурсов (отсутствие простоя процессоров). В работе развивается и обобщается на нелинейный случай предложенный ранее авторами метод частичной синхронизации итераций при решении систем уравнений вида x = F (x), где x - неизвестный вектор-столбец длины n, а F - оператор из Rn в Rn. Рассматриваются такие операторы F, для которых не выполнено достаточное условие сходимости асинхронных итераций, но при этом сходятся простые итерации. В этом случае можно указать пример оператора и свойства вычислительной системы, при которых асинхронные итерации будут расходиться. При этом эффективным решением может стать частичная синхронизация. Предложен алгоритм, обеспечивающий сходимость асинхронных итераций и метода Монте-Карло для указанного класса операторов. Оценивается скорость сходимости метода. Результаты могут быть полезны при решении больших задач на многопроцессорных вычислительных комплексах. Библиогр. 4 назв.

Downloads

Download data is not yet available.

References

1. Дмитриев А.В., Ермаков С.М. Метод Монте-Карло и асинхронные итерации // Вестник С-Петерб. ун-та. Сер. 1. Математика. Механика. Астрономия. 2014. Т. 1 (59). Вып. 4. C. 517-528.

2. Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. М.: Мир, 1975.

3. Bertsekas D.P., Tsitsiklis J.N. Parallel and Distributed Computation: Numerical Methods. Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 1989. 0-13-648700-9. ISBN: 0-13-648700-9

4. Chazan D., Miranker W. Chaotic relaxation // Linear Algebra and its Applications. 1969. Vol. 2, N 2. P. 199-222.

Published

2020-08-20

How to Cite

Dmitriev, A. V., & Ermakov, . S. M. (2020). On partial synchronization of iterative methods. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 3(3), 393–401. Retrieved from https://math-mech-astr-journal.spbu.ru/article/view/8684

Issue

Section

Mathematics