In my project I have to solve a couple of tridiagonal matrices at every time step, so it is crucial to have a good solver for those. I did my own implementation, just the classical way to do it described on Wikipedia. I then tried using Lapack instead, and to my surprise it was slower!
Now, inside Lapack it seems like it does the solving by LU factorization and I wonder why, isn't it more complex than it could be?
Additionally, I found an algorithm in the "Numerical Recipes" book from nr.com which recursively divides the system into smaller tridiagonal problems. It looked promising. Are there any other goodies out there?
Update: the problem size is about 1000x1000. I used GotoBLAS, it gives you a Lapack 3.1.1 library also. The problem is not symmetric. I used the Lapack routine for general tridiagonal matrices.