О параллелизме стохастических и квазистохастических алгоритмов в задачах моделирования

Вопросы эффективности решения широкого круга задач моделирования тесно связаны с возможностями использования параллельных компьютерных структур. Известно, что методы Монте-Карло благодаря присущему им естественному параллелизму обладают рядом преимуществ в этом отношении. В некоторых случаях они допускают практически неограниченный параллелизм при полной загрузке оборудования.
Существуют определенные ограничения, налагаемые на класс задач, которые могут быть решены путем моделирования траекторий случайных процессов. Это естественные ограничения, связанные с возможностью представления решения в виде интеграла по траекториям. Другой тип ограничений связан с известным невысоким порядком убывания погрешности стохастических методов – для достижения точности порядка $\varepsilon$ требуется проследить $\sim1/\varepsilon^2$ траекторий.
В предполагаемой заметке показано, как преодолеваются эти ограничения при решении задач большого объема. Результаты в значительной степени опираются на исследования автора и его коллег, осуществленные в последние годы. В этой части работа по необходимости имеет характер обзора. Однако проблемы синхронности и параллелизма ранее в таком объеме не излагались.
Далее мы рассматриваем проблему решения систем линейных алгебраических уравнений – одну из основных в вычислительной математике, хотя, можно указать уже отдельные результаты, выходящие за рамки этой проблемы.