A parallel and scalable algorithm for ADI method with pre-propagation and message vectorization

It is hard to implement the ADI method in an efficient way on distributed-memory parallel computers. We propose “P-scheme” which parallelizes a tridiagonal linear system of equations for the ADI method, but its effectiveness is limited to the cases where the problem size is large enough mainly because of the communication cost of the propagation phase of the scheme.

In order to overcome this difficulty, we propose an improved version of the P-scheme with “message vectorization” which aggregates several communication messages into one and alleviates the communication cost. Also we evaluate the effectiveness of message vectorization for the ADI method and show that the improved version of the P-scheme works well even for smaller problems and linear and super-linear speedups can be achieved for 8194 × 8194 and 16,386 × 16,386 problems, respectively.