A direct tridiagonal solver based on Givens rotations for GPU architectures
| Autor: | Alexandros Kouris, Ioannis E. Venetis, Alexandros Sobczyk, Ahmed H. Sameh, Efstratios Gallopoulos |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Tridiagonal matrix
Computer Networks and Communications Computer science Diagonal Parallel algorithm Tridiagonal matrix algorithm Block matrix Parallel computing Solver Computer Science::Numerical Analysis Computer Graphics and Computer-Aided Design Theoretical Computer Science QR decomposition CUDA Artificial Intelligence Hardware and Architecture Computer Science::Mathematical Software Spike (software development) Software |
| Zdroj: | Parallel Computing. 49:101-116 |
| ISSN: | 0167-8191 |
| DOI: | 10.1016/j.parco.2015.03.008 |
| Popis: | A parallel solver for general tridiagonal irreducible systems is described.Solver based on Spike framework and Givens-QR with occasional low-rank modification.Modifications handle singularities exposed by QR in blocks of the parallel partition.The GPU implementation has similar performance to existing methods.Method returns accurate results when current GPU tridiagonal solvers fail. g-Spike, a parallel algorithm for solving general nonsymmetric tridiagonal systems for the GPU, and its CUDA implementation are described. The solver is based on the Spike framework, applying Givens rotations and QR factorization without pivoting. It also implements a low-rank modification strategy to compute the Spike DS decomposition even when the partitioning defines singular submatrices along the diagonal. The method is also used to solve the reduced system resulting from the Spike partitioning. Numerical experiments with problems of high order indicate that g-Spike is competitive in runtime with existing GPU methods, and can provide acceptable results when other methods cannot be applied or fail. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect