The problems of high performance technologies for solving large sparse linear systems

Authors

  • V.P. Il'in

Keywords:

systems of linear algebraic equations
sparse symmetric and nonsymmetric matrices
direct
iterative and combined methods
parallelization
computer architecture

Abstract

The technological problems of implementation of the parallel algorithms for solving the systems of linear algebraic equations with sparse matrices of high order that arise in grid approximations in the large problems of mathematical modeling are considered. Classification of algebraic systems and comparative analysis of complexity of the direct, iterative and, combined methods of their solution are given with consideration of different matrix data structures and access formats. The bottle necks and basic approaches to develop the high-performance mathematical software for multi-processor computing systems with shared and distributed memory are described on the basis of using MPI, OpenMP, and hybrid programming. The paper was prepared on the basis of the authors' report at the International Conference on Parallel Computing Technologies (PaVT-2009; http://agora.guru.ru/pavt).

New computational technologies

Downloads

Published

2009-05-06

Issue

Vol. 10 (2009): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biography

V.P. Il'in

The Institute of Computational Mathematics and Mathematical Geophysics of SB RAS (ICM&MG SB RAS)

• Chief Researcher

References

  1. Самарский А.А., Николаев Е.С. Методы решения сеточных зфавнений. М.: Наука, 1978.
  2. Ильин В.П. Методы конечных разностей и конечных объемов для эллиптических уравнений. Новосибирск: Изд-во ИВМ СО РАН, 2000.
  3. Ильин В.П. Методы и технологии конечных элементов. Новосибирск: Изд-во ИВМиМГ СО РАН, 2007.
  4. Богачев К.Ю. Основы параллельного программирования. М.: БИНОМ, 2003.
  5. Ильин В.П. Параллельные алгоритмы для больших прикладных задач: проблемы и технологии // Автометрия. 2007. 43, № 2. 3-21.
  6. Ильин В.И., Кныш Д.В. Параллельные алгоритмы решения разделяющихся краевых задач // Санкт-Петербург: Изд-во Политехи, ун-та (СПбПГУ), 2008. 107-118.
  7. Ильин В.И., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука, 1985.
  8. Andreeva M.Yu., II’in V.P., Itskovich E.A. Two solvers for nonsymmetric SLAE // Bull. NCC. Ser. Num. Anal., 2003. Iss. 12. 1-16.
  9. Saad Y. Iterative methods for sparse linear systems. NY: PWS Publish., 1996.
  10. Ильин В.П. О методах сопряженных и полусопряженных направлений с предобуславливающими проекторами // ДАН. 2008. 419, № 3. 303-306.
  11. Benzi М., Golub G., Leisen J. Numerical solution of saddle point problems // Acta Numer. 2005. 14. 1-137.