tridiagonal matrix

Martin Siegert siegert at
Fri Jul 28 14:26:15 PDT 2000

On Fri, 28 Jul 2000, Peter Jay Salzman wrote:

> i have a series of linear equations which are represented by a tridiagonal
> matrix.  the order of the matrix is between 1000 and 10000.  this is thfe
> major bottleneck in my code, so i'd like to know if solving a tridiagonal
> matrix is a parallelizable operation.
> the only tridiagonal matrix algorithm i know of is the thomas algorithm.
> the algorithm has a structure like:
> get a result for a[i]
> use a[i] to obtain a[i+1]
> use a[i+1] to obtain a[i+2]
> ...
> this looks decidedly non-parallelizable to me.  i was wondering if anyone
> knew of another algorithm which i could implement using MPI to get past this
> bottleneck.
> (drop in code for fortran or C++ would be fantabulous!).

ScaLAPACK seems to have all that you need. I haven't used those routines
myself yet, but it has specific routines for tridiagonal matrices.
I can't say anything about the performance (although my impression is that
this may be hard to beat), all these matrix routines require substantial

You get ScaLAPACK from,

ScaLAPACK relies on several other libraries (blas, blacs, lapack, etc.).
I strongly recommend to install ATLAS as well and use it instead of the
standard blas library.

All these libraries you find at the netlib site.


Martin Siegert
Academic Computing Services                        phone: (604) 291-4691
Simon Fraser University                            fax:   (604) 291-4242
Burnaby, British Columbia                          email: siegert at
Canada  V5A 1S6

More information about the Beowulf mailing list