APPLICATION AND ACCURACY OF THE PARALLEL DIAGONAL DOMINANT ALGORITHM

The Parallel Diagonal Dominant (PDD) algorithm is an efficient tridiag onal solver. In this paper, a detailed study of the PDD algorithm is g iven. First the PDD algorithm is extended to solve periodic tridiagona l systems and its scalability is studied. Then the reduced PDD algorit hm, which has a smaller operation count than that of the conventional sequential algorithm for many applications, is proposed. Accuracy anal ysis is provided for a class of tridiagonal systems, the symmetric and skew-symmetric Toeplitz tridiagonal systems. Implementation results s how that the analysis gives a good bound on the relative error, and th e PDD and reduced PDD algorithms are good candidates for emerging mass ively parallel machines.