Fastest parallel solver for tridiagonal system

Arpiruk

Hello everyone,

I have been searching for parallel algorithm for compact scheme, i.e. Lele1993 (J.Comp.Phy) and Kobayashi1999 (J.Comp.Phy). This means I have to solve Ax=Bf where x is the desired value(interpolation/differentiation/second-order differentiation).

The matrix A i have to deal with is a tridiagonal matrix. I this A are always positive definite on ordinary smooth grid.(still don't know how to prove it though)

I did some research and believe that fine-grained parallelism such as Recursive doubling (Stone1975 TOMS) and Cyclic reduction(Hockney1965 J.ACM ) are not suited for current supercomputers which are now very large grain ( A cluster with multi-core node ). Family of pipelining algorithm also requires too much communications.

It seems that the reduced parallel diagonal dominant of SUN (http://mack.ittc.ku.edu/sun95application.html) are the most efficient for this problem. The complexity is 5n/p+4J (p=#of proc, J = truncated bandwidth) which almost matches the best serial code ( Thomas algo. with prefactored LU ~ 5n-3) .

Is this algorithm already the best (at the moment ?) Are there any algorithm more efficient than this one ? Are there any particular problem in this algorithm that I should be aware of ?

Any suggestions are appreciated.

Regards, Arpiruk