Matrix-Vector Multiplication and Triangular Linear Solver Using GPGPU for Symmetric Positive Definite Matrices Derived from Elliptic Equations

Author(s)

Martins, Thiago de Castro ; Kian, Jacqueline de Miranda ; Sato, Andre Kubagawa ; Guerra Tsuzuki, Marcos de Sales ; IEEE

• Document type: Journal article
• Source: 6TH INTERNATIONAL CONFERENCE ON SOFT COMPUTING AND INTELLIGENT SYSTEMS, AND THE 13TH INTERNATIONAL SYMPOSIUM ON ADVANCED INTELLIGENT SYSTEMS; v. N/A, p. 6-pg., 2012-01-01.

Abstract

The modern GPUs are well suited for intensive computational tasks and massive parallel computation. Sparse matrix multiplication and linear triangular solver are the most important and heavily used kernels in scientific computation, and several challenges in developing a high performance kernel with the two modules is investigated. The main interest it to solve linear systems derived from the elliptic equations with triangular elements. The resulting linear system has a symmetric positive definite matrix. The sparse matrix is stored in the compressed sparse row (CSR) format. It is proposed a CUDA algorithm to execute the matrix vector multiplication using directly the CSR format. A dependence tree algorithm is used to determine which variables the linear triangular solver can determine in parallel. To increase the number of the parallel threads, a coloring graph algorithm is implemented to reorder the mesh numbering in a pre-processing phase. The proposed method is compared with parallel and serial available libraries. The results show that the proposed method improves the computation cost of the matrix vector multiplication. The pre-processing associated with the triangular solver needs to be executed just once in the proposed method. The conjugate gradient method was implemented and showed similar convergence rate for all the compared methods. The proposed method showed significant smaller execution time. (AU)

• FAPESP's process: 11/01194-8 - Massive Parallelization of the Conjugated Gradients Algorithm applied to the reconstruction of Electrical Impedance Tomography Images
• Grantee: Jacqueline de Miranda Kian
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• FAPESP's process: 10/19646-0 - Translating No-Fit Polygons to Create Degenerated Collision Free Region Using Non-Regulerized Boolean Operations
• Grantee: André Kubagawa Sato
• Support Opportunities: Scholarships in Brazil - Doctorate
• FAPESP's process: 09/07173-2 - Applying the simulated annealing to the electrical impedance tomography aiming the determination of absolute images
• Grantee: Marcos de Sales Guerra Tsuzuki
• Support Opportunities: Regular Research Grants