In this report, we summarize existing parallel algorithms for tridiagonal solvers and propose a novel tridiagonal solver algorithm, called LUL-UBD algorithm. We point out all existing algorithms can be viewed as linear recurrences or extension of linear recurrences. We further indicate necessary optimization strategies for high-performance implementation of each algorithm in SIMD architectures. We also analyze the performance of existing algorithms, using computation complexity, the required number of parallel steps, the required number of division operations, and the number of memory access requests. Our proposed algorithm has the minimal number of memory access requests, the minimal number of division operations, and linear computational complexity.