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 81948194 and 16,38616,386 problems, respectively.
scalable algorithm adi message vectorization super-linear speedup tridiagonal matrix