HyperLink   Mapping Tridiagonal Solvers to Linear Recurrences
Publication Year:
  Li-Wen Chang, Wen-mei Hwu
  IMPACT Technical Report, IMPACT-13-01, University of Illinois at Urbana-Champaign, Center for Reliable and High-Performance Computing, Sept. 8, 2013

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.