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

Авторы

  • С.А. Соловьев

Ключевые слова:

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

Аннотация

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

Новые вычислительные технологии

Загрузки

Опубликован

2014-07-29

Выпуск

Том 15 (2014): Выпуск 3.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

С.А. Соловьев

Институт нефтегазовой геологии и геофизики имени А.А. Трофимука СО РАН
проспект Академика Коптюга, 3, 630090, Новосибирск
• научный сотрудник

Библиографические ссылки

  1. Бахвалов Н.С. О сходимости одного релаксационного метода при естественных ограничениях на эллиптический оператор // Ж. вычисл. матем. и матем. физ. 1966. 6, № 5. 861-885.
  2. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. М.: Мир, 1984.
  3. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.: Мир, 1991.
  4. Федоренко Р.П. Релаксационный метод решения разностных эллиптических уравнений // Ж. вычисл. матем. и матем. физ. 1961. 1, № 5. 922-927.
  5. Bebendorf M. Approximation of boundary element matrices // Numer. Mathem. 2000. 86, N 4. 565-589.
  6. Chandrasekaran S., Dewilde P., Gu M., Somasunderam N. On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs // Siam Journal on Matrix Analysis and Applications. 2010. 31, N 5. 2261-2290.
  7. Chandrasekaran S., Gu M., Li X.S., Xia J. Some fast algorithms for hierarchically semiseparable matrices. Report LBNL-62897. Berkeley: Lawrence Berkeley Nat. Lab., 2007.
  8. Chandrasekaran S., Dewilde P., Gu M., Pals T. A fast ULV decomposition solver for hierarchically semiseparable representations // SIAM J. Matrix Anal. Appl. 2006. 28, N 3. 603-622.
  9. Ernst O.G., Gander M.J. Why it is difficult to solve Helmholtz problems with classical iterative methods // Numerical Analysis of Multiscale Problems. Heidelberg: Springer, 2012. 325-363.
  10. George A. Nested dissection of a regular finite element mesh // SIAM Journal on Numerical Analysis 1973. 10, N 2. 345-363.
  11. Lipton R., Rose D., Tarjan R. Generalized nested dissection // SIAM J. Numer. Anal. 1979. 16, N 2. 346-358.
  12. Hackbusch W. A sparse matrix arithmetic based on H-matrices. Part I: Introduction to H-matrices // Computing. 1999. 62, N 2. 89-108.
  13. Bebendorf M., Hackbusch W. Existence of H-matrix approximants to the inverse FE-matrix of elliptic operators with L^infty-coefficients // Numer. Mathem. 2003. 95, N 1. 1-28.
  14. Karypis G., Kumar V. METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices. Version 4.0. Minneapolis: University of Minnesota, 1998.
  15. Le Borne S., Grasedyck L., Kriemann R. Domain-decomposition based H-LU preconditioners // Lecture Notes in Computational Science and Engineering. Vol. 55. Heidelberg: Springer, 2007. 667-674.
  16. Lipton R., Rose D., Tarjan R. Generalized nested dissection // SIAM J. Numer. Anal. 1979. 16, N 2. 346-358.
  17. Ortega J.M. Повторяет ссылку [3]: Introduction to Parallel and Vector Solution of Linear Systems. Frontiers in Computer Science, Springer. 1988.
  18. Rjasanow S. Adaptive cross approximation of dense matrices // Proc. Int. Association for Boundary Element Methods. Austin: Univ. Texas at Austin, 2002. 1-12.
  19. Saad Y. Iterative methods for sparse linear systems. Philadelphia: SIAM, 2003.
  20. Saad Y., Vorst H. Iterative solution of linear systems in the 20th century // Journal of Computational and Applied Mathematics. 2000. 123, N 1. 1-33.
  21. Goreinov S.A., Tyrtyshnikov E.E., Zamarashkin N.L. A theory of pseudo-skeleton approximations // Linear Algebra Appl. 1997. 261, N 1-3. 1-21.
  22. Tyrtyshnikov E.E. Mosaic-skeleton approximations // Calcolo. 1996. 33, N 1. 47-57.
  23. Tyrtyshnikov E.E. Incomplete cross approximation in the mosaic-skeleton method // Computing. 2000. 64, N 4. 367-380.
  24. Wang S., de Hoop M.V., Xia J., Li X.S. Massively parallel structured multifrontal solver for time-harmonic elastic waves in 3-D anisotropic media // Geophys. J. Int. 2012. 191, N 1, 346-366.
  25. Wang S., Li X.S., Xia J., de Hoop M.V., Situ Y. Efficient scalable algorithms for hierarchically semiseparable matrices // SIAM J. Sci. Comput. 2013. 35, N 6. 519-544.
  26. Xia J. A robust inner-outer hierarchically semi-separable preconditioner // Numer. Linear Algebra Appl. 2012. 19, N 6. 992-1016.
  27. Xia J. Efficient structured multifrontal factorization for general large sparse matrices // SIAM J. Scientific Computing. 2013. 35, N 2. 832-860.
  28. Xia J. Robust and efficient multifrontal solver for large discretized PDEs // High-Performance Scientific Computing. London: Springer, 2012. 199-217.
  29. Xia J., Chandrasekaran S., Gu M., Li X.S. Superfast multifrontal method for large structured linear systems of equations // SIAM J. Matrix Anal. Appl. 2009. 31, N 3. 1382-1411.