Об эффективности параллельных итерационных методов для линейных алгебраических систем

Е.В. Довольнов, С.В. Шешенин (Москва)

При решении систем линейных уравнений на параллельных компьютерах возникает проблема выбора предобуславливателя и собственно итерационного метода. Цель данного исследования состояла в оценке практической эффективности ряда методов, которые обеспечивали бы, во-первых, достаточно быструю сходимость, и, во-вторых, были бы достаточно универсальными. В качестве матриц систем линейных уравнений мы брали матрицы, возникающие при решении методом конечных элементов задачи моделирования напряженно - деформированного состояния пневматической шины. Такие матрицы имеют разреженную ленточную структуру. Решались системы с числом уравнений 30000, 50000, 70000 и 90000 на 2-х, 3-х и т.д. до 12 процессорах. Для вычислений использовалась кластерная система МВС 1000М. Система МВС 1000М состоит из 384 двухпроцессорных модулей с процессорами Alpha 21264, объединенных сетью Myrinet 2000. Объем оперативной памяти на каждом модуле составляет 2 Гбайта. Исследовались следующие итерационные методы: Ричардсона, Чебышевского, сопряженных градиентов и его модификации в сочетании с предобуславливателем Якоби, блочным предобуславливателем Якоби и аддитивным предобуславливателем Шварца. В программе, решающей систему линейных уравнений, используется MPI в качестве платформы для коммуникаций и библиотека PETSc (http://www.mcs.anl.gov/petsc).

В результате экспериментов можно сделать следующие выводы. Наиболее надежным сочетанием предобуславливателя и итерационного метода оказалось сочетание стабилизированного метода бисопряженных градиентов (BiCGSTAB) и самого простого предобуславливателя Якоби. При таком сочетании итерации сходятся для всех наборов процессоров от 2-х до 12-ти и для матриц размером 30000, 50000 и 70000. Правда, для матрицы размером 90000 лучшим оказалось сочетание метода квазиминимальных невязок и блочного предобуславливателя Якоби. Основной вывод, который можно сделать из проведенных экспериментов, состоит в том, что для достаточно большого числа процессоров время решения системы для различных методов примерно одинаково, и, следовательно, надежность метода является наиболее важным показателем эффективности метода.