SCALABLE PARALLEL TRIDIAGONAL ALGORITHMS WITH DIAGONAL PIVOTING AND THEIR OPTIMIZATION FOR MANY-CORE ARCHITECTURES BY

Tridiagonal solvers are important building blocks for a wide range of scientific applications that are commonly performance-sensitive. Recently, many-core architectures, such as GPUs, have become ubiquitous targets for these ap-plications. Therefore, a high-performance general-purpose GPU tridiagonal solver becomes critical. However, no existing GPU tridiagonal solver provides comparable quality of solutions to most common, general-purpose CPU tridi-agonal solvers, like Matlab or Intel MKL, due to no pivoting. Meanwhile, conventional pivoting algorithms are sequential and not applicable to GPUs. In this thesis, we propose three scalable tridiagonal algorithms with diag-onal pivoting for better quality of solutions than the state-of-the-art GPU tridiagonal solvers. A SPIKE-Diagonal Pivoting algorithm efficiently par-titions the workloads of a tridiagonal solver and provides pivoting in each partition. A Parallel Diagonal Pivoting algorithm transforms the conven-tional diagonal pivoting algorithm into a parallelizable form which can b