A New Method for Solving Triangular Systems on Distributed-Memory Message-Passing Multiprocessors
Guangye Li, Thomas F. Coleman · SIAM Journal on Scientific and Statistical Computing · 1989
Efficient triangular solvers for use on message-passing multiprocessors are required, in several contexts, under the assumption that the matrix is distributed by columns (or rows) in a wrap fashion. In this paper a new efficient parallel triangular solver for these problems is described. This new algorithm is based on the previous method of Li and Coleman [1988] but is considerably more efficient when ${n / p}$ is relatively modest, where p is the number of processors, and n is the problem dimension. A useful theoretical analysis is provided as well as extensive numerical results obtained on an Intel iPSC with $p \leqq 128$.