Optimal Parallel Triangulation of a Sparse Matrix

Abstract

We consider the problem of triangulating a sparse matrix in a parallel processing system and attempt to answer the following questions: 1) How should the rows and columns of the matrix be reordered in order to minimize the completion time of the parallel triangulation process if an unrestricted number of processors are used? 2) if the number of processors is fixed, what is the minimum completion time and how should the parallel Operations be scheduled? Implementation of the parallel algorithm is discussed and experimental results are given. © 1979 IEEE