1. [Publications](/index.php/publications)
2. A Hybrid Method for Solving Tridiagonal Systems on the GPU
 
 # A Hybrid Method for Solving Tridiagonal Systems on the GPU

  ![](/sites/default/files/styles/wide/public/pubs/2011-09_A-Hybrid-Method/default.jpg?itok=QEkKyEk-)

 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.



 ## Authors



Yao Zhang (UC Davis)

Jonathan Cohen (NVIDIA)

Andrew A. Davidson (UC Davis)

John Owens (UC Davis)

 

 

 ## Publication Date



Thursday, September 1, 2011

 

 ## Published in



[GPU Computing Gems, Jade Edition, Edited by Wen-mei W. Hwu](http://mkp.com/news/3405)

 

 ## Research Area



[Algorithms and Numerical Methods](/index.php/research-area/algorithms)