Решение разреженных систем линейных уравнений методом Гаусса с использованием техники аппроксимации матрицами малого ранга
Соловьев С.А.

Предложен алгоритм решения систем линейных алгебраических уравнений (СЛАУ), получаемых в результате дискретизации трехмерных уравнений математической физики. Алгоритм основан на методе исключения Гаусса с использованием вложенных сечений и аппроксимации матрицами малого ранга. Без ограничения общности алгоритм описан для случая симметричных положительно определенных матриц. Для хранения матрицы L в LU-разложении исходной матрицы используется крупноблочное представление, а также иерархический формат HSS (Hierarchically Semiseparable Structure). Для построения малоранговой аппроксимации предложено использование адаптивной крестовой аппроксимации, что более эффективно по сравнению с известными SVD- и QR-методами. Для повышения эффективности программной реализации алгоритма используются подпрограммы библиотек Intel MKL BLAS и LAPACK. На основе предлагаемого алгоритма и использования Intel MKL BLAS/LAPACK создана научно-исследовательская версия программного обеспечения для вычислительных систем с общей памятью. Приведены результаты тестирования, которые показали высокое качество предложенного алгоритма малоранговой/HSS-аппроксимации. Тестирование производительности и примененные способы использования памяти показывают более чем трехкратное превосходство предложенного подхода по сравнению с программным пакетом PARDISO библиотеки Intel MKL PARDISO.

Ключевые слова: трехмерные задачи математической физики, алгоритмы решения разреженных линейных систем, метод Гаусса, аппроксимация матрицами малого ранга, HSS-формат матриц, итерационное уточнение.

Название статьи, аннотация и ключевые слова на английском языке

  • Соловьев С.А. – Институт нефтегазовой геологии и геофизики им. А.А. Трофимука СО РАН, просп. Академика Коптюга, 3, 630090, г. Новосибирск; науч. сотр., e-mail: 511ssa@mail.ru