Как можно распараллелить многосеточный метод для решения линейной системы уравнений?

11

Насколько я понимаю, многосеточный метод решает линейную систему, решая более грубую версию той же проблемы (устраняя низкочастотную ошибку), затем проецируя обратно в точную сетку, чтобы сгладить высокочастотные ошибки. Для больших систем я вижу, как итерационный метод может быть реализован параллельно на каждом уровне сетки. Этот подход хорошо масштабируется параллельно? Есть ли какой-либо другой источник параллелизма в алгоритме, который можно использовать параллельно?

Пол
источник

Ответы:

14

Параллельная геометрическая многосетка проста для реализации на структурированных сетках. Алгебраическая и неструктурированная многосетка более техническая, см. Этот ответ для ссылок на реализации.

VlogcNNc2d3ddlog2logcN, Мне еще предстоит увидеть демонстрацию на реальном оборудовании, в которой повышенный параллелизм оправдывает худшие константы и снижает надежность аддитивных методов.

O(N/P)

На практике грубые сетки быстро достигают строгого предела масштабируемости (сверх которого добавление большего количества процессов увеличивает время выполнения), поэтому они должны размещаться на все меньших коммуникаторах MPI. Это добавляет небольшую сложность к реализации. Для проблем, в которых грубые уровни имеют слишком большую структуру, чтобы продолжать грубое изменение, решение грубого уровня может стать узким местом.

Для тестирования различных параллельных многосеточных методов я рекомендую использовать такую ​​библиотеку, как PETSc, которая позволяет запускать множество различных алгоритмов с очень небольшим количеством пользовательского кода.

Джед браун
источник
Ссылка Адамс (2001) больше не работает. Я полагаю, что статья, которую вы имели в виду, это: ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1592790&tag=1 . «Алгоритм Гаусса-Зейделя с распределенной памятью для многосеточных сглаживателей» Дайте мне знать, если я ошибаюсь.
nukeguy