Abstract
The tridiagonal solver nowadays appears as a fundamental component in scientific and engi-neering problems, such as Alternating Direction Implicit methods (ADI), fluid Simulation, and Poisson’s equation. Due to the particular sparse format of tridiagonal matrix, many algorithms of solving the system are conceived. Previously, the main stream of solving the system is by using Diagonal Pivoting to reduce the accuracy issue. But, Diagonal Pivoting has its limits and will lead to error solution while the condition number increases. Augmented Block Cimmino Distributed (ABCD) algorithm serves as another option when trying to resolve the problem accurately. In this thesis, we study and implement the ABCD algorithm on GPU. Because of the spe-cial structure of tridiagonal matrices, we investigate the boundary padding technique to eliminate the execution branches on GPU for better performance. In addition, our implementation incorpo-rates various performance optimization techniques, such as memory coalesce, to further enhance the performance. In the experiments, we evaluate the accuracy and performance of our GPU im-plementation against CPU implementation, and analyze the effectiveness of each performance op-timization technique. The performance of GPU version is about 15 times faster than that of the CPU version.