Amg1r5

AMG1r5 — исторически первая успешная программа предназначенная для решения больших разреженных линейных систем уравнений алгебраическим многосеточным методом (AMG).

С начала 1990-х годов наблюдается растущий спрос на более эффективные методы решения крупных разреженных, неструктурированных линейных систем уравнений. Для практически актуальных размеров проблем классические одноуровневые методы уже достигли своих пределов, и необходимо было разработать новые иерархические алгоритмы, чтобы обеспечить эффективное решение ещё больших проблем.

AMG — один из очень эффективных итерационных методов для решения линейных систем уравнений, например, возникающих при численном решении различных типов эллиптических уравнений в частных производных на неструктурированных сетках. Метод может быть использован как решатель по принципу чёрного ящика, для различных вычислительных задач, в том числе и не содержащих геометрическую информацию, а содержащих лишь матрицу коэффициентов линейной системы самой различной природы происхождения (теплопередача, аэро-гидродинамика, нефтяные месторождения, компьютерная томография и др.). AMG часто используется и как собственный решатель линейных систем и как предобуславливатель к итерационным методам (Conjugate Gradients, BiCGStab или FGMRES).

AMG1r5.f — это самодостаточный файл на языке FORTRAN с набором функций (около 4600 строк кода) одна из которых является вызываемой извне и в которую передаётся матрица линейной системы уравнений в CRS формате хранения. Авторами AMG1r5 являются Джон Руге университет Колорадо и Клаус Штубен из Fraunhofer Institute for Algorithms and Scientific Computing SCAI. Код amg1r5 написан в 1986 году. Это исторически первый программный код, доказывающий, что линейная масштабируемость (от числа неизвестных в системе линейных уравнений) может быть достигнута без привлечения геометрической информации о задаче. Код amg1r5 обладает лучшей скоростью сходимости (справляется с большими числами обусловленности) по сравнению с современными многосеточными методами сглаженной агрегации (SA-amg). В отличие от методов сглаженной агрегации код AMG1r5 требует для работы большого количества оперативной памяти (до 13 размеров исходной матрицы для amg1r5 и менее 2 размеров исходной матрицы для SA-amg методов).

AMG1r5 свободно доступный исследовательский учебный код без какого-либо обслуживания или поддержки. Он хорошо документирован и является классическим и исторически первым. Основная критика кода amg1r5 связана с его высокой операторной сложностью. Тем не менее amg1r5 содержит такие положительные компоненты как:

1. C/F релаксация, Gauss-Seidel релаксация.

2. RS/ RS2 огрубление.

3. Amg1r5 интерполяция (Amg1r6 вариант алгоритма).

4. Понижение операторной сложности путём задания параметра ecg2=0.9 вместо 0.25.

С минимальными модификациями код amg1r5 может использоваться как предобуславливатель к алгоритмам BiCGStab и FGMRes. Расспараллеливание с помощью OpenMP фазы решения позволяет ускорить алгоритм amg1r5 до трёх раз на системах с общей памятью, согласно закону Амдала. А также функция relx_ может быть дополнена сглаживателем ILUk, k=0,1,…, например, из библиотеки Ю.Саада SPARSKIT2. Данные модификации позволяют коду amg1r5 решать ещё более плохообусловленные задачи ещё большего размера.

Литература

1. Волков К. Н., Дерюгин Ю. Н., Емельянов В. Н. и др. Глава 3. Алгебраические многосеточные методы. // Методы ускорения газодинамических расчётов на неструктурированных сетках. М. ФИЗМАТЛИТ, 2014. — С. 75-255. — 535 с. — ISBN 978-5-9221-1542-1.

2. K. Stuben. A review of algebraic multigrid. Journal of Computational and Applied Mathematics 128 (2001) 281—309. https://doi.org/10.1016/S0377-0427(00)00516-1

3. Сидельников К. А., Васильев А. В. Решение матричных уравнений алгебраическим многосеточным методом при моделировании течения жидкости в нефтяных пластовых системах. // Надежность и качество. Труды международного симпозиума / Под ред. Н. К. Юркова. — Пенза: Изд-во Пенз. гос. ун-та, 2005. — C. 224—226.