ROW ORIENTED GAUSS ELIMINATION ON DISTRIBUTED MEMORY MULTIPROCESSORS
This paper deals with the Gauss elimination for solving general dense linear systems on distributed memory multiprocessors. A row oriented parallel algorithm is proposed and implemented on the NCUBE distributed memory multiprocessor. We study in some detail various implementation choices which are important factors affecting the algorithm's performance. These factors include: mapping of rows into processors, pivoting implementation, message passing, communication granularity and pipelining. Experiments with these on the NCUBE are reported which illustrate the algorithms performance characteristics. Both standard and memory scaled speed up are measured which show that the algorithm is very efficient. Comparisons with previous approaches which mix row and column operations show an obvious gain in efficiency.