Tridiagonal linear systems are of importance to many problems in numerical analysis and computational fluid dynamics, as well as to computer graphics applications in video games and computer-animated films. Typical applications require solving hundreds or thousands of tridiagonal systems, which takes a majority part of total computation time. Fast parallel solutions are critical to larger scientific simulations, interactive computations of special effects in films, and real-time applications in video games. In this chapter, we study the performance of multiple tridiagonal algorithms on a GPU. We design a novel hybrid algorithm that combines a work efficient algorithm with a step-efficient algorithm in a way well-suited for a GPU architecture. Our hybrid solver achieves 8x and 2x speedup respectively in single precision and double precision over a multi-threaded highly-optimized CPU solver, and a 2x-2.3x speedup over a basic GPU solver.