I am solving a physical problem using implicit numerical scheme. This leads me to solving a linear equation with tridiagonal matrix. I've coded this algorithm from Wikipedia. I wonder if there is an efficient library which allows to solve this type of equation in optimised way. An important note is that matrix itself changes only when system parameters are changing, so I had an opportunity to precalculate some algorithm steps for a nice peformance bonus. I am using C++.
You should probably start with the LAPACK implementation, ?gtsv, e.g., dgtsv. If you want a distributed-memory version, then you might want to start with ScaLAPACK's p?gtsv.
EDIT: Since your matrix does not change very often, you can avoid redundantly factoring the tridiagonal matrix by breaking up the LAPACK routine ?gtsv into the factorization step, ?gttrf, and the solve stage, ?gttrs. Similarly named routines exist in ScaLAPACK that serve the same purpose.
For distributed parallel systems: I have not tried ScaLAPACK, which has a parallel tridiagonal solver, for which there are examples available online. I have tried with some success a method proposed by David Moulton in a LANL publication. Coding this up might be more than you want to do, but by using LAPACK, it is strait forward.
I found an interesting recursive algorithm here at page 975. It looks promising, I wonder what more experienced people say about it.