tridiagonal matrix

[Martin Siegert]

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
communication.

You get ScaLAPACK from www.netlib.org,
http://www.netlib.org/scalapack

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.

Cheers,
Martin

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