A Parallel and Scalable Algorithm for Calculating Linear and Non-linear Recurrence Equations

A. Wakatani (Japan)


tridiagonal matrix, recurrence equation, scalable algo rithm, ADI


A tridiagonal linear system of equations for ADI can be solved by "Gaussian elimination" which consists of cal culating two types of recurrence equations, both of which need to be carefully parallelized in order to achieve high performance. We propose a parallel and scalable scheme for calculating these recurrence equations and our exper iment shows that it provides an exact solution with good accuracy and achieves P 2 1 speedup without any startup de lay required for the cell-partitioned methods. Our scheme is suitable for PC cluster system since the communication overhead can be ignored when the size of the dimension of arrays to be distributed is sufficiently large.

Important Links:

Go Back