Введение к работе
Актуальность темы. Решение систем линейных алгебраических уравнений с разреженной матрицей является одним из наиболее актуальных вопросов в современной вычислительной математике. Это связано с тем, что системы такого вида обычно возникают при численном решении дифференциальных уравнений с помощью сеточных методов. Поэтому нас интересуют здесь не произвольные матрицы, а только такие, которые могут возникать при указанном подходе. Во-первых, это зачастую симметричные положительно определенные матрицы. Во-вторых, расположение ненулевых элементов в них является не произвольным, а подчиняется некоторой закономерности, связанной со способом нумерации сеточных узлов; иногда, в частности, возможно получать ленточные и другие матрицы специального вида с компактным размещением ненулевых элементов. В-третьих, эти матрицы обладают очень высоким разрежением: для матриц порядка нескольких десятков п сотен тысяч количество ненулевых элементов в одной строке составляет около нескольких десятков.
Настоящая работа посвящена изучению алгоритмических и связанных с ними структурных вопросов, возникающих при численном решении разреженных систем линейных алгебраических уравнений
Ах = Ь, (1)
где А - разреженная симметричная положительно определенная матрица, прямыми и итерационными методами.
Цель работы. 1. Построение схемы хранения разреженного множителя Холесского, соответствующей выбранному способу нумерации неизвестных и обеспечивающей быстрый доступ как к отдельным элементам матрицы, так и целым блокам. 2. Разработка алгоритма Холесского, позволяющего эффективно реализовывать процесс разложения на выбранной схеме хранения. 3. Исследование применимости и эффективности метода неполной факторизации с ускорением по ме-
тоду сопряженных градиентов при численном решении разностных уравнений Гельмгольца на сфере. 4. Изучение применимости многоуровневых итерационных методов для решения линейных систем уравнений, возникающих при конечно-элементных аппроксимациях. Отыскание теоретических оценок скорости сходимости и вычислительных затрат метода. 5. Исследование эффективности применения метода неполной факторизации при определении аппроксимации дополнения Шура на новом уровне. Отыскание теоретических оценок скорости сходимости и вычислительных затрат метода.
Методы исследования. Методы линейной алгебры, вычислительной математики и математического анализа.
Научная новизна. Предложен кросс-метод решения разреженной системы линейных алгебраических уравнений и соответствующая древовидная структура данных для хранения разреженного множителя Холесского. Исследованы различные варианты, порождаемые данным подходом: многофронтальный, параллельный, асимметричный и экономичные варианты кросс-метода. Разработан высокоэффективный алгоритм метода неполной факторизации с ускорением по методу сопряженных градиентов при численном решении разностных уравнений Гельмгольца на сфере со специальной нумерацией узлов сетки. Приведена экономичная реализация методов циклической и блочно-цпклической редукции. Предложен и исследован многоуров-ненвый итерационный метод для решения линейных систем уравнений, возникающих при конечно-элементных аппроксимациях. Предложен и исследован многоуровневый итерационный метод неполной факторизации на основе рекурсивной четно-нечетной редукции с ускорением сопряженными градиентами для решения пятиточечных систем уравнений с симметричными положительно определенными матрицами.
Практическая ценность. Результаты диссертации находят приме-
нение при решении систем линейных алгебраических уравнений, возникающих при конечно-разностных и конечно-элементных аппроксимациях дифференциальных задач математической физики.
Апробация работы. Основные результаты диссертации докладывались на Всероссийской конференции по комплексам программ математической физики (Новосибирск, 1992), 8-ой Всесибир-ской школе по методам вычислительной математики (Шушенское, 1993), международном семинаре "Numerical Linear Algebra with Applications" ("Численные методы линейной алгебры и приложения") (Неймеген, Нидерланды, 1993), конференции молодых ученых ВЦ СО РАН (Новосибирск, Россия, 1995), международной конференции "Advanced Mathematics, Computations and Applications" ("Современные проблемы прикладной и вычислительной математики") (Новосибирск, Россия, 1995), на научных семинарах ВЦ СО РАН.
Публикации. По теме диссертации опубликовано десять работ.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав и списка литературы. Объем работы - 168 машинописных страниц. Список литературы содержит 90 наименований.
