A ROW BASED PARALLEL GAUSSIAN-ELIMINATION ALGORITHM FOR THE CONNECTION MACHINE CM-2

This paper presents an algorithm for the Gaussian elimination problem that reduces the length of the critical path compared to the algorithm of Lord et al. This is done by redefining the notion of a task. For a ll practical purposes, the issues of communication overhead and pivoti ng cannot be overlooked. We consider these issues for the new algorith m as well. Timing results of this algorithm as executed on the CM-2 mo del of the Connection Machine are presented. Another contribution of t his paper is the use of logical pivoting for stable computation of the Gaussian elimination algorithm. Pivoting is essential is producing st able results. When pivoting occurs, an interchange of two rows is requ ired. A physical interchange of the values can be avoided by providing a permutation vector in a globally accessible location. We show exper imental results that substantiate the use of logical pivoting.