Анализ и реализация последовательных и параллельных алгоритмов решения СЛАУ на подпространствах Крылова

Решение систем линейных алгебраических уравнений (СЛАУ) является одним из основных этапов численного решения задач математической физикинаряду с точностью дискретизации задачи точность решения СЛАУ является важнейшим фактором, влияющим на качество найденного решения [13], [10], [25], [26].

Наряду с задачами математической физики, к необходимости решения СЛАУ приводят и многие другие задачи, например, проблемы распознавания образов, проблемы финансовой и страховой математики и т. д. [40], [42], [59]. Различные подходы к их решению могут приводить к формированию плохо обусловленных и вырожденных систем, включая недоопреде-ленные, решение которых обычно ищется в смысле наименьшей нормы и переопределенные (в случае несовместности последних как правило требуется поиск решения в смысле наименьших квадратов) [1], [57].

Развитие вычислительной техники сделало необходимым создание программных комплексов для данного обязательного этапа численного решения задач. Начиная с 1960;х годов, появилось большое количество программ и программных пакетов для решения СЛАУ, некоторые из которых используются и в настоящее время [34], [35], [44], [52]. Часть таких программных средств является коммерческими продуктами [51], часть объявлена свободно распространяемымираспространению последних в значительной степени способствуют возможности международной компьютерной сети Internet [22], [25].

Исторически развитие вычислительной техники оказывало значительное влияние на развитие численных методов, используемых для решения реальных задач. Небольшие объемы оперативной памяти первых компьютеров и их низкоскоростные устройства внешней памяти позволяли решать задачи лишь теми методами, которые приводили к СЛАУ с плотными матрицами небольшой размерности либо с разреженными матрицами регулярной структуры, допускающей экономичные способы хранения [13], [20], [10]. Подавляющее большинство программного обеспечения, ведущего свою историю с 1960;х годов, ориентировано на работу именно с такими данными [25]- средства, позволяющие работать с более сложными данными 6 и реализующие более сложные методы, весьма немногочисленны и в большинстве своем носят коммерческий характер.

Быстрое улучшение технических характеристик компьютеров привело к возможности работать с данными гораздо большего объема [40], что в свою очередь, привело к росту популярности методов дискретизации, оперирующих более сложными понятиями. Наряду с методами конечных разностей, получили распространение методы конечных элементов и контрольных объемов [13], [26], [33], [45], [48]- кроме того, все эти методы стали применяться для поиска решений на неструктурированных сетках с локальными сгущениями узлов [26]. Применительно к строящимся в данных методах СЛАУ это означало отказ от регулярной структуры матриц, переход к специальным методам их хранения [32] и итерационным методам решения, не требующим пересчета матрицы (в частности, методам проектирования на подпространствах Крылова [45], [57]).

Однако в силу закрытости и коммерческого характера решаемых такими методами задач, разработанное отдельными коллективами исследователей программное обеспечение не стало общедоступным и в основной массе также осталось закрытым. Стоимость отдельных современных коммерческих пакетов линейной алгебры доходит до сотен тысяч долларов.

Появление отдельных монографий по вычислительным методам для работы с разреженными матрицами [17] не могло изменить ситуацию вплоть до появления многопроцессорных вычислительных комплексов [40]. Резкий роет вычислительных возможностей в сочетании с отсутствием программных средств привел к появлению большого количества работ, посвященных разработке параллельных алгоритмов линейной алгебры, а также адаптации уже существующего программного обеспечения [16], [28], [34], [48], [49], [54], [55].

В 1990;ые годы начали появляться средства, ориентированные на использование современных методов, и реализующие современные алгоритмы. Их количество и качество имеют устойчивую тенденцию к росту, однако распространение подобного программного обеспечения несколько сдерживается отсутствием устоявшихся стандартов на реализацию некоторых деталей, характерных для параллельного программирования (например, синхронизацию и обмен сообщениями) [25]. Кроме того, задачи адаптации существующего и разработки нового программного обеспечения 7 поставили перед разработчиками ряд проблем, многие из которых до настоящего времени не решены [49].

Целью данной работы является исследование ряда методов решения СЛАУ с плотными (включая прямоугольные) и разреженными матрицами, их реализация в виде программного инструмента, удобного для применения в методах конечных элементов и контрольных объемовобъектом исследования в частности является возможность параллельной реализации и изучение ее эффективности.

Научная новизна работы заключается в исследовании малоизученного класса методов решения плотных СЛАУ, предложенного А. А. Абрамовым, детальном анализе входящих в него методов и их связи с другими методами и классами (в частности, с некоторыми методами решения разреженных СЛАУ). Для методов решения разреженных СЛАУ исследуется 1Ш-предобуеловливание и проводится анализ сложности соответствующего алгоритма в зависимости от используемого способа хранения разреженных матриц, что позволяет сделать выводы о целесообразности использования тех или иных форматов представления данных. Для созданных параллельных алгоритмов проводится теоретический анализ эффективности, проверенный серией вычислительных экспериментов.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения, приложения, списка литературы и содержит 156 страниц, включая 5 таблиц и 14 иллюстраций.

Список литературы

содержит 61 наименование.

Заключение

.

В работе получены следующие основные результаты:

• На основе сформулированных А. А. Абрамовым теорем разработаны вычислительные схемы, эффективные для решения плотных плохо обусловленных и вырожденных (включая прямоугольные) СЛАУ. В рамках данного класса исследованы и реализованы методы ABR и ABRIORT. Для метода ABRIORT получена оценка точности, достигаемой в конечной арифметике и сформулированы условия, позволяющие повысить точность. Показана связь класса методов А. А. Абрамова с ABS-классом, доказана эквивалентность методов Ху-анга и ABR в точной арифметике.

• Исследованы и реализованы методы решения СЛАУ с разреженными несимметричных матрицами BiCG и GMRES (m), принадлежащие к классу методов на подпространствах Крылова. Для GMRES (m) исследованы экстремальные случаи выбора размерности подпространства Крылова т.

• Для методов BiCG и GMRES реализовано ILU-предобусловливание, позволяющее значительно ускорить процесс решения. Предобуслов-ливание реализовано для нескольких различных форматов хранения разреженных матриц произвольной структурыполучены соответствующие оценки вычислительной сложности алгоритмов, что позволило сформулировать рекомендации для выбора форматов МКО и МКЭ СЛАУ.

• Разработан программный пакет LinPar, предназначенный для использования в качестве внешнего модуля в программах решения задач математической физики. Пакет включает методы ABR, ABRIORT, CG, BiCG, GMRES (m) с возможностью использования в методах CG, BiCG, GMRES (m) ILU-предобусловливания. Реализована работа с большим количеством форматов представления пользовательских данных. Пакет использован при решении реальных физических задач.

• Для методов ABR, ABRIORT, BiCG, GMRES (m) разработаны и реализованы параллельные алгоритмы. Проведены исследования их эф.

107 фективности и получены теоретические оценки асимптотического ускоренияпроведен ряд вычислительных экспериментов, показавших хорошее согласование результатов с теоретическими оценками.

I0?5.