tridiagonal matrix
Martin Siegert
siegert at sfu.ca
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
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
========================================================================
More information about the Beowulf
mailing list