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

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

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

$V$$\log_{c} N$$N$$c$$2^d$$3^d$$d$$\log_2 \log_c N$, Мне еще предстоит увидеть демонстрацию на реальном оборудовании, в которой повышенный параллелизм оправдывает худшие константы и снижает надежность аддитивных методов.

$\mathcal O (N/P)$

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

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