Tridiagonal linear systems arise from discretizations of differential equations. The associated matrices have non-zero elements only on the main diagonal and on the two diagonals directly above and below the main diagonal. In practice, very large systems are needed and parallel methods are often used in solving these large systems.

This paper takes a known parallel algorithm and develops a method, called g-Spike, for use with graphics processing units (GPUs). This algorithm has three stages. The first stage is to partition the matrix, and each processing element is given a portion of the matrix. The second stage has three parts, including Givens-based QR decomposition of each diagonal block, singularity detection and modification, and Spike system formation. The third stage is to solve the Spike system and to restore the final solution. Optimization techniques for GPUs are also studied, such as overlapping memory access latency with computation, and data marshaling.

Many matrices are employed to test performance and accuracy. Numerical results show the performance of g-Spike is similar to solvers from cuSPARSE and IMPACT, and its accuracy is also good. As claimed by the authors, their solver can provide acceptable results when other methods cannot be applied or fail. However, there is no comparison between GPU-version solvers and central processing unit (CPU)-version solvers.