Hybrid Algorithms for Solving the Algebraic Eigenvalue Problem with Sparse Matrices
- PDF / 347,392 Bytes
- 13 Pages / 594 x 792 pts Page_size
- 2 Downloads / 215 Views
SOFTWARE–HARDWARE SYSTEMS HYBRID ALGORITHMS FOR SOLVING THE ALGEBRAIC EIGENVALUE PROBLEM WITH SPARSE MATRICES A. N. Khimich,1† A. V. Popov,1‡ and O. V. Chistyakov1††
UDC 519.6
Abstract. Hybrid algorithms for solving the partial generalized eigenvalue problem for symmetric positive definite sparse matrices of different structures by hybrid computers with graphic processors are proposed, coefficients for the efficiency of the algorithms are obtained, and approbation of the developed algorithms for test and practical problems is carried out. Keywords: algebraic eigenvalue problem, computer of hybrid architecture, hybrid algorithm, subspace iteration method, conjugate gradient methods, efficiency of parallel algorithms. INTRODUCTION A great number of practical problems, such as structural stability analysis, dynamic analysis of stress–strain state of objects of various nature, etc., reduce to the partial algebraic eigenvalue problem (AEP) with sparse symmetric positive definite matrices [1]. Development of parallel algorithms of AEP solution is based on well-known, well-behaved sequential algorithms. The papers [2, 3] present explicit and implicit one-step iterative methods to solve the partial eigenvalue problem, among which are the method of steepest descent, inverse iteration method, power method, and alternate triangular method. The paper [4] considers the generalized conjugate gradient method on the basis of the symmetric upper relaxation method to solve systems of linear algebraic equations. The study [5] outlines theoretical aspects of the subspace iteration method, the Lanczos algorithm for finding several minimum eigenvalues. The requirements for high-performance computing are much more ahead of the capabilities of traditional parallel computers, even despite multi-core processors. This problem is being solved by using hybrid computers that combine MIMD and SIMD architecture, which use computers with multi-core processors (CPU) and graphics accelerators (GPU). The fullest use of the potential of such computers is only possible if algorithms and software are available that take into account not only properties of the problem but the features of hybrid architecture as well. The most well-known algorithms and programs to solve problems of linear algebra for various types of parallel computers were developed under the guidance of Prof. J. Dongarra [6, 7]. To solve AEP with large sparse matrices, parallel software library SLEPc (Scalable Library for Eigenvalue Problem Computations) is available [8]. LIS (Library of Iterative Solvers) [9] allows solving linear algebra problems, in particular, systems of linear algebraic equations and AEP, with matrices of various formats by parallel computers with the use of floating-point arithmetic. The study [10] considers some special features of developing parallel algorithms of the subspace iteration method for computers of different architectures. In [11], parallel algorithms are developed for alternate triangular method. 1
V. M. Glushkov Institute of Cybernetics, National
Data Loading...
