A PARALLEL AND SCALABLE ALGORITHM FOR CALCULATING LINEAR AND NON-LINEAR RECURRENCE EQUATIONS

摘要

A tridiagonal linear system of equations for ADI can be solved by "Gaussian elimination" which consists of calculating 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 experiment shows that it provides an exact solution with good accuracy and achieves P/2.1 speedup without any startup delay 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.